25. 5. 2018 (pátek [Friday], 10:40, MFF UK Malá Strana S10)
Václav Koubek, Antonín Ríha: The Maximum k-Flow in a Network. MFCS 1981, pp. 389-397, LNCS 118, Springer.
(presented by Petr Kolman)
Abstract: Given a graph $G=(V,E)$ with edge capacities, a source-sink pair $s,t \in V$
and an integer $L$, an $L$-bounded flow is a flow decomposable into flow
paths between $s$ and $t$ of length at most $L$. The maximum $L$-bounded
flow can be computed in polynomial time using linear programming. An
intersting problem is to find a polynomial time algorithm that is not based
on LP.
In 1981, at the conference Mathematical Foundations of Computer Science,
Koubek and Říha presented a paper "The maximum k-flow in a network" [1]
about such an algorithm. Unfortunately, the proceedings of the conference
contain only a sketch of the paper: the algorithm itself is not described,
none of the lemmas are proved, the key new definition is not correct, ...
With my bachelor student Kateřina Altmanová, we try to understand the paper
and fill in the missing proofs. In the seminar, I'll present our current
understanding of the paper.
18. 5. 2018 (pátek [Friday], 10:40, MFF UK Malá Strana S10)
Martijn van Ee, Leo van Iersel, Teun Janssen, René Sitters: A
priori TSP in the Scenario Model. WAOA 2016: 183-196.
(presented by Štěpán Šimsa)
Abstract: In this paper, we consider the a priori traveling salesman problem (TSP) in the scenario model. In this problem, we are given a list of subsets of the vertices, called scenarios, along with a probability for each scenario. Given a tour on all vertices, the resulting tour for a given scenario is obtained by restricting the solution to the vertices of the scenario. The goal is to find a tour on all vertices that minimizes the expected length of the resulting restricted tour. We show that this problem is already NP-hard and APX-hard when all scenarios have size four. On the positive side, we show that there exists a constant-factor approximation algorithm in three restricted cases: if the number of scenarios is fixed, if the number of missing vertices per scenario is bounded by a constant, and if the scenarios are nested. Finally, we discuss an elegant relation with an a priori minimum spanning tree problem.
4. 5., 11. 5. 2018 (pátek [Friday], 10:40, MFF UK Malá Strana S10)
Euiwoong Lee: Improved
Hardness
for Cut, Interdiction, and Firefighter Problems. ICALP
2017.
Best Student Paper. Also http://arxiv.org/abs/1607.05133.
(presented by Petr Kolman)
Abstract: We will focus on the Length-Bounded Cut part of the paper. From
its abstract:
We study variants of the classic s-t cut problem and prove the following
improved hardness results assuming the Unique Games Conjecture (UGC). For
Length-Bounded Cut and Shortest Path Interdiction, we show that both
problems are hard to approximate within any constant factor, even if we
allow bicriteria approximation. If we want to cut vertices or the graph is
directed, our hardness ratio for Length-Bounded Cut matches the best
approximation ratio up to a constant. Previously, the best hardness ratio
was 1.1377 for Length-Bounded Cut and 2 for Shortest Path Interdiction.
Our results are based on a general method of converting an integrality gap
instance to a length-control dictatorship test for variants of the s-t cut
problem, which may be useful for other problems.
27. 4. 2018 (pátek [Friday], 10:40, MFF UK Malá Strana S10)
Martin Skutella: A
Note on the Ring Loading Problem. SIAM J. Discrete
Math., 30(1), 327-342. 2016.
(presented by Lukáš Folwarczný)
Abstract: The Ring Loading Problem is an optimal routing problem arising in the planning of optical communication networks which use bidirectional SONET rings. In mathematical terms, it is an unsplittable multicommodity flow problem on undirected ring networks. We prove that any split routing solution to the Ring Loading Problem can be turned into an unsplittable solution while increasing the load on any edge of the ring by no more than $+\frac{19}{14} D$, where $D$ is the maximum demand value. This improves upon a classical result of Schrijver, Seymour, and Winkler (1998), who obtained a slightly larger bound of $+\frac32 D$. We also present an improved lower bound of $\frac{11}{10} D$ (previously $\frac{101}{100} D$) on the best possible bound and disprove a famous long-standing conjecture of Schrijver, Seymour, and Winker in this context.
13. 4., 20. 4. 2018 (pátek [Friday], 10:40, MFF UK Malá Strana S10)
Yossi Azar, Arun Ganesh, Rong Ge, Debmalya Panigrahi: Online service with delay. STOC 2017: 551-563. Also https://arxiv.org/abs/1708.05611.
(presented by Pavel Veselý)
Abstract: In this paper, we introduce the online service with delay problem. In this
problem, there are n points in a metric space that issue service requests
over time, and a server that serves these requests. The goal is to minimize
the sum of distance traveled by the server and the total delay in serving
the requests. This problem models the fundamental tradeoff between batching
requests to improve locality and reducing delay to improve response time,
that has many applications in operations management, operating systems,
logistics, supply chain management, and scheduling.
Our main result is to show a poly-logarithmic competitive ratio for the
online service with delay problem. This result is obtained by an algorithm
that we call the preemptive service algorithm. The salient feature of this
algorithm is a process called preemptive service, which uses a novel
combination of (recursive) time forwarding and spatial exploration on a
metric space. We hope this technique will be useful for related problems
such as reordering buffer management, online TSP, vehicle routing, etc. We
also generalize our results to k>1 servers.
6. 4. 2018 (pátek [Friday], 10:40, MFF UK Malá Strana S10)
Andreas Emil Feldmann: The Parameterized Hardness of the k-Center Problem in Transportation Networks. https://arxiv.org/abs/1802.08563.
(joint work with Daniel Marx)
Abstract: In this paper we study the hardness of the k-Center problem on
inputs that model transportation networks. For the problem, an edge-weighted
graph G=(V,E) and an integer k are given and a center set C\subseteq V needs
to be chosen such that |C|<=k. The aim is to minimize the maximum distance
of any vertex in the graph to the closest center. This problem arises in
many applications of logistics, and thus it is natural to consider inputs
that model transportation networks. Such inputs are often assumed to be
planar graphs, low doubling metrics, or bounded highway dimension graphs.
For each of these models, parameterized approximation algorithms have been
shown to exist. We complement these results by proving that the k-Center
problem is W[1]-hard on planar graphs of constant doubling dimension, where
the parameter is the combination of the number of centers k, the highway
dimension h, and even the treewidth t. Moreover, under the Exponential Time
Hypothesis there is no f(k,t,h)n^o(t+\sqrt{k+h}) time algorithm for any
computable function f. Thus it is unlikely that the optimum solution to
k-Center can be found efficiently, even when assuming that the input graph
abides to all of the above models for transportation networks at once!
Additionally we give a simple parameterized (1+ε)-approximation algorithm
for inputs of doubling dimension d with runtime (k/ε)^O(kd)n^O(1). This
generalizes a previous result, which considered inputs in d-dimensional Lq
metrics.
9. 3., 16. 3. 2018 (pátek [Friday], 10:40, MFF UK Malá Strana S10)
Vera Traub, Jens Vygen: Approaching 3/2 for the s-t-path TSP. Best paper of SODA 2018. https://arxiv.org/abs/1707.03992.
(presented by Martin Böhm)
Abstract: We show that there is a polynomial-time algorithm with approximation guarantee 3/2 + epsilon for the s-t-path TSP, for any fixed epsilon > 0. It is well known that Wolsey's analysis of Christofides' algorithm also works for the s-t-path TSP with its natural LP relaxation except for the narrow cuts (in which the LP solution has value less than two). A fixed optimum tour has either a single edge in a narrow cut (then call the edge and the cut lonely) or at least three (then call the cut busy). Our algorithm "guesses" (by dynamic programming) lonely cuts and edges. Then we partition the instance into smaller instances and strengthen the LP, requiring value at least three for busy cuts. By setting up a k-stage recursive dynamic program, we can compute a spanning tree (V,S) and an LP solution y such that y(12+O(2^(−k))) is in the T-join polyhedron, where T is the set of vertices whose degree in S has the wrong parity. Our new algorithm does not imply an upper bound on the integrality ratio. However, we also show a smaller upper bound (less than 1.52) on the integrality ratio by a new analysis of the previously best algorithm, due to Sebó and van Zuylen.
23. 2., 2. 3. 2018 (pátek [Friday], 10:40, MFF UK Malá Strana S10)
Nikhil Bansal, Marek Elias, Grigorios Koumoutsos, and Jesper Nederlof: Competitive Algorithms for Generalized k-Server in Uniform Metrics. SODA 2018. Also https://arxiv.org/abs/1707.04519.
(presented by Jakub Sosnovec)
Abstract: The generalized k-server problem is a far-reaching extension of the k-server problem with several applications. Here, each server si lies in its own metric space Mi. A request is a k-tuple r = (r1, r2, …, rk) and to serve it, we need to move some server si to the point ri ∊ Mi, and the goal is to minimize the total distance traveled by the servers. Despite much work, no f(k)-competitive algorithm is known for the problem for k>2 servers, even for special cases such as uniform metrics and lines.
Here, we consider the problem in uniform metrics and give the first f(k)-competitive algorithms for general k. In particular, we obtain deterministic and randomized algorithms with competitive ratio k·2k and O(k3 log k) respectively. Our deterministic bound is based on a novel application of the polynomial method to online algorithms, and essentially matches the long-known lower bound of 2k–1. We also give a 22O(k)-competitive deterministic algorithm for weighted uniform metrics, which also essentially matches the recent doubly exponential lower bound for the problem.