Invited Session Thu.3.H 3013

Thursday, 15:15 - 16:45 h, Room: H 3013

Cluster 2: Combinatorial optimization [...]

Scheduling and network flows over time


Chair: Martin Skutella



Thursday, 15:15 - 15:40 h, Room: H 3013, Talk 1

Alberto Marchetti-Spaccamela
Universal sequencing on an unreliable machine

Coauthors: Leah Epstein, Asaf Levin, Nicole Megow, Julian Mestre, Martin Skutella, Leen Stougie


We consider scheduling on an unreliable machine that may experience unexpected changes in processing speed or even full breakdowns. Our objective is to minimize
the sum of weighted completion times for any non-decreasing, non-negative, differentiable cost function f(Cj).
We aim for a universal solution that performs well without adaptation for all cost functions for any possible machine behavior.
We design a deterministic algorithm that finds
a universal scheduling sequence with a solution value within four times the value of an optimal
clairvoyant algorithm that knows the machine behavior in advance. A randomized version of this algorithm attains in expectation a ratio of e. We show that both performance
guarantees are best possible for any unbounded cost function.
When jobs have individual release dates, the situation changes drastically. Even if all weights are equal, there are instances for which any universal solution is a factor of O(log n/ log log n) worse than an optimal sequence for any unbounded cost function. If the processing time of each job is proportional to its weight we present a non-trivial algorithm with a worst case of 5.



Thursday, 15:45 - 16:10 h, Room: H 3013, Talk 2

Martin GroƟ
Approximating earliest arrival flows in arbitrary networks

Coauthors: Jan-Philipp W. Kappmeier, Daniel R. Schmidt, Melanie Schmidt


The earliest arrival flow problem is motivated by evacuation planning. It consists of computing a flow over time in a network with supplies and demands, such that the satisfied demands are maximum at every point in time. For a single source and sink, the existence of such flows has been shown by Gale [1959]. For multiple sources and a single sink the existence follows from work of Minieka [1973] and an exact algorithm has been presented by Baumann and Skutella [FOCS~'06]. If multiple sinks exist, it is known that earliest arrival flows do not exist in general.
We address the open question of approximating earliest arrival flows by time or flow-value in arbitrary networks and show the first constructive results for them. We give tight bounds for the best possible approximation factor in most cases. In particular, we show that there is always a 2-flow-value approximation of earliest arrival flows and that no better approximation factor is possible in general. Furthermore, we describe an FPTAS for computing the best possible approximation factor along with the corresponding flow for any given instance (which might be better than 2).



Thursday, 16:15 - 16:40 h, Room: H 3013, Talk 3

Jan-Philipp W. Kappmeier
Flows over time with negative transit times and arc release dates

Coauthors: Sandro Bosio, Jannik Matuschke, Britta Peis, Martin Skutella


A common generalization of the classical network flow setting are network flows over time. In contrast to the classical model, here a notion of time is incorporated that represents the time needed to travel over an arc. We present two generalizations of the maximum flow over time problem, one which allows to use negative transit times on arcs, and the other with arc release dates. In contrast to the standard maximum flow over time problem, the computational tractability of either of the generalizations depends on the possibility of flow storage at intermediate nodes. Both problems can be solved in polynomial time by reduction to the quickest transshipment problem if storage at intermediate nodes is allowed. However, if storage is forbidden, both problems are weakly NP-hard. The generalizations can both be used to answer questions on a bipartite matching over time problem, which is a generalization of the classical matching problem also incorporating a notion of time.


  The system of instant Virginia Loans Online allows any adult U.S. citizen. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.