The Online Delay Management on a Single Train Line (ODMP) deals with the question at which station a train should wait for delayed passengers, instead of forcing them to take the next train. Waiting at a station increases the delay of all passengers that are already on board, and the goal is to minimize the total passenger delay. An online algorithm learns about the number of delayed passengers at a station only when reaching this station. We study the ODMP with an additional prediction on the future input data, which an online algorithm can utilize. Two desired qualities for online algorithms with prediction are called consistency and robustness, denoting the competitive ratio in case of best and worst prediction respectively. We present a family of algorithms, which uses a hyperparameter λ ∈ ( 0 , 1 ) measuring the “doubt” about the given prediction. This allows to achieve ( 1 + λ ) -consistency and ( 1 + 1 / λ ) -robustness. Moreover, we provide a lower bound for the trade-off between consistency and robustness for two variously detailed prediction models, showing that our algorithm achieves an asymptotically optimal trade-off for small values of λ .

ABSTRACT In this paper we present a new covering problem, called Min Cost ‐Single Location Cover, where we are given a fixed positive integer , a finite ground set , an integral positive demand for each element , a collection of subsets of , an integral positive cost and an integral positive capacity value for each subset . The task is to choose sets from , with multiple choices being allowed, such that each element is covered at least times. However, if a given subset is chosen to cover an element, it must already cover the entire demand of the element. Moreover, each subset may only cover up to of its elements, where again multiple choices are allowed. Our problem is motivated by a healthcare application for placing emergency doctors into facilities such that all emergencies occurring in a shift can be handled in a satisfactory manner. We show that Min Cost ‐Single Location Cover can be solved in polynomial time for , but is strongly NP‐complete for . To handle the case where equals two, we introduce a new constrained ‐edge cover problem in an edge‐colored graph, called Minimum Weight ‐Edge Cover with Colors. We analyze the complexity of this problem for general graphs as well as for the special instances resulting from an instance of ‐Single Location Cover.

The Partial Scenario Set Cover problem (PSSC) generalizes the Partial Set Cover problem, which is itself a generalization of the classical Set Cover problem. We are given a finite ground set Q , a collection S of subsets of Q to choose from, each of which is associated with a nonnegative cost, and a second collection U of subsets of Q of which a given number l must be covered. The task is to choose a minimum cost sub-collection from S that covers at least l sets from U . PSSC is motivated by an application for locating emergency doctors. We present two approximation approaches. The first one combines LP-based rounding with a greedy consideration of the scenarios. The other is a variant of the greedy set cover algorithm, and in each iteration tries to minimize the ratio of cost to number of newly covered scenarios. We show that this subproblem, which we call Dense Scenario Set Cover (DSSC), is itself as hard to approximate as Set Cover and NP-hard, even when there is only a single scenario and all sets contain at most three elements. Furthermore, we consider a special case of DSSC where the sets are pairwise disjoint and show that in this case DSSC can be solved in polynomial time. We also provide an approximation for the general case, which we use as a subroutine in the greedy algorithm to obtain an approximation for PSSC.

Abstract In the equal maximum flow problem (EMFP), we aim for a maximum flow where we require the same flow value on all arcs in some given subsets of the arc set, so called homologous arc sets. In this article, we study the closely related almost equal maximum flow problems (AEMFP) where the flow values on arcs of one homologous arc set differ at most by the valuation of a so called deviation function . We prove that the integer AEMFP is in general ‐complete, and show that even the problem of finding a fractional maximum flow in the case of convex deviation functions is also ‐complete. This is in contrast to the EMFP, which is polynomial time solvable in the fractional case. Additionally, we provide inapproximability results for the integral AEMFP. For the (fractional) concave AEMFP we state a strongly polynomial algorithm for the linear and concave piecewise polynomial deviation function case for a fixed number of homologous sets using a parametric search approach.

We consider network design games with weighted players and uniform edge capacities and study their Nash equilibria. In these games, each player has to choose a path from her source to her sink through a network subject to the constraint that the total weight of all players using an edge within their chosen path does not exceed the capacity of the edge. The fixed cost of each edge that is used by some player is shared among the players using the edge by charging each player a fraction of the edge's cost equal to the ratio of her weight to the total weight of all players using the edge. We show that there exist instances of capacitated network design games with weighted players and uniform capacities that do not admit a Nash equilibrium even in the case that all players share the same source and sink. Moreover, we show that it is strongly ‐hard to decide whether a given instance admits a Nash equilibrium even if a feasible solution for the underlying network design problem is guaranteed to exist. In contrast, we prove that, for series‐parallel graphs, there always exists a Nash equilibrium whose total cost equals the cost of an optimal solution of the corresponding network design problem and provide an (exponential‐time) algorithm to compute this equilibrium. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(2), 141–158 2016

Network routing games have attracted a lot of attention over the last years. However, most of the work assumes that the users have complete knowledge about the data in the network, in particular, about the precise travel times over the links. In this article, we address the more realistic case that users only know lower and upper bounds for the travel times and learn about the actual realization later. Thus, users cannot expect to choose a strategy which is optimal for each realization (scenario). This situation leads to combining concepts from robust optimization with algorithmic game theory. Specifically, we study the case where each user wants to minimize her regret, which is defined to be the worst‐case difference of her bottleneck objective (the cost of her most expensive resource) to the optimum attainable value given a priori knowledge about the actual scenario. We show that in robust bottleneck routing games, equilibria do not always exist, but the existence can be guaranteed under the restriction that the problem is symmetric and the intervals of uncertainty have constant length. We prove that in general it is NP‐hard to decide whether a given instance has a robust equilibrium. In the case of constant‐length intervals of uncertainty, a robust equilibrium can be computed efficiently (in the symmetric case). We also investigate the Price of Robustness, which formally quantifies the lack of performance due to uncertainty and give a tight bound. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(1), 57–66 2015

In the online traveling salesman problem, requests for visits to cities (points in a metric space) arrive online while the salesman is traveling. The salesman moves at no more than unit speed and starts and ends his work at a designated origin. The objective is to find a routing for the salesman that finishes as early as possible. Performance of algorithms is measured through their competitive ratio, comparing the outcome of the algorithms with that of an adversary who provides the problem instance and therefore is able to achieve the optimal offline solution. Objections against such omnipotent adversaries have lead us to devise an adversary that is in a natural way, in the context of routing problems, more restricted in power. For the exposition we consider the online traveling salesman problem on the metric space given by ℝ0+, the non-negative part of the real line. We show that a very natural strategy is 3/2-competitive against the conventional adversary, which matches the lower-bound on competitive ratios achievable for algorithms for this problem. Against the more “fair adversary”, that we propose, we show that there exists an algorithm with competitive ratio (1 + √17)/4 ≈ 1.28 and provide a matching lower bound. We also show competitiveness results for a special class of algorithms (called zealous algorithms) that do not allow waiting time for the server as long as there are requests unserved.