May 20, 2019 (pondělí [Monday], 14:00, MFF UK Malá Strana
S6)
Martin Koutecký: Near-linear time algorithm for 2-stage
stochastic IPs
(joint work with Fritz Eisenbrand, Christoph Hunkenschröder,
Kim-Manuel Klien, Asaf Levin, and Shmuel Onn)
Abstract: 2-stage stochastic integer programs model
optimization problems in which the revelation of data and
subsequent response happen in two stages, and the goal is to
optimize the expected cost. In 2001, Hemmecke and Schultz have
shown that 2-stage stochastic IPs with small blocks and small
coefficients are fixed-parameter tractable in cubic time. We bring
the polynomial dependency to almost linear by a combination of a
novel proximity-scaling algorithm, bounds on equivalent
objectives, and other techniques.
May 6, May 13, 2019 (pondělí [Monday], 14:00, MFF UK Malá
Strana S6)
Petr Kolman: The length bounded cut problem: Towards better
approximations?
(joint work with Eden Chlamtáč)
Abstract: Given a graph G=(V,E) with two
distinguished vertices s and t in V and an
integer parameter L, an $L$-bounded cut is a
subset F of edges such that the every path between s
and t in (V,E-F) has length at least L.
The minimum L-bounded cut problem is to find an L-bounded
cut of minimum cardinality; the problem is known also under the
name the short paths interdiction problem.
Though the problem is very simple to state and has been studied
since the beginning of the 70's, it is not much understood yet.
The best known
approximation, in terms of n (number of vertices), is Theta(n^{2/3})
while the best lower bounds on it are only constant, even if we
assume UGC.
In the talk I'll present a few new partial results, inculding a
new LP relaxation of the problem.
Apr 15, Apr 29 2019 (pondělí [Monday], 14:00, MFF UK Malá Strana
S6)
Klaus Jansen, Lars Rohwedder: Local search breaks
1.75 for Graph Balancing.
https://arxiv.org/abs/1811.00955
(presented by Jiří Sgall)
Abstract: Graph Balancing is the problem of orienting the edges of a weighted multigraph so as to minimize the maximum weighted in-degree. Since the introduction of the problem the best algorithm known achieves an approximation ratio of 1.75 and it is based on rounding a linear program with this exact integrality gap. It is also known that there is no (1.5-eps)-approximation algorithm, unless P=NP. Can we do better than 1.75? We prove that a different LP formulation, the configuration LP, has a strictly smaller integrality gap. Graph Balancing was the last one in a group of related problems from literature, for which it was open whether the configuration LP is stronger than previous, simple LP relaxations. We base our proof on a local search approach that has been applied successfully to the more general Restricted Assignment problem, which in turn is a prominent special case of makespan minimization on unrelated machines. With a number of technical novelties we are able to obtain a bound of 1.749 for the case of Graph Balancing. It is not clear whether the local search algorithm we present terminates in polynomial time, which means that the bound is non-constructive. However, it is a strong evidence that a better approximation algorithm is possible using the configuration LP and it allows the optimum to be estimated within a factor better than1.75. A particularly interesting aspect of our techniques is the way we handle small edges in the local search. We manage to exploit the configuration constraints enforced on small edges in the LP. This may be of interest to other problems such as Restricted Assignment as well.
Apr 1, Apr 8, 2019 (pondělí [Monday], 14:00, MFF UK Malá
Strana S6)
Eyal Amir, Robert Krauthgamer, Satish Rao: Constant
factor approximation of vertex-cuts in planar graphs.
STOC 2013.
(presented by Michal Berg)
Abstract: We devise the first constant factor
approximation algorithm for minimum quotient vertex-cuts in planar
graphs. Our algorithm achieves approximation ratio 1+4/3(1+ε)
with running time O(W• n3+2/ε), where W
is the total weight of the vertices. The approximation ratio
improves to 4/3(1+ε+o(1)) if there is an optimal quotient
vertex-cut (A*,B*,C*)
where the weight of C* is of low order compared
to those of A* and B*; this
holds, for example, when the input graph has uniform weights and
costs. The ratio further improves to 1+ε+o(1) if, in
addition, min[w(A*),w(B*)] ≤ 1/3 W.We
use our algorithm for quotient vertex-cuts to achieve the first
constant-factor pseudo-approximation for vertex separators in
planar graphs.Our technical contribution is two-fold. First, we
prove a structural theorem for planar graphs, showing the
existence of a near-optimal quotient vertex-cut whose high-level
structure is that of a bounded-depth tree. Second, we develop an
algorithm that optimizes over such complex structures in running
time that depends (exponentially) not on the size of the
structure, but rather only on its depth. These techniques may be
applicable in other problems.
Mar 25, 2019 (pondělí [Monday], 14:00, MFF UK Malá Strana S6)
Pavel Veselý: Streaming Algorithms for Bin Packing and Vector
Scheduling
Abstract: In the streaming model, input data arrive
gradually, item by item, and the algorithm maintains a small
summary of the input stream, i.e., runs in a limited space.
However, unlike in the online scenario, it does not need to make
decisions on the fly. Instead, after receiving the whole input, it
computes an estimate of the optimum value from the summary. The
goal is to design algorithms that produce small input summaries
with good approximation guarantees.
We show a 1-pass streaming algorithm for the Bin Packing problem
that computes a 1+ε-approximation of the optimum number of bins
using space O(1/ε · log 1/ε · log OPT). We then discuss streaming
algorithms for Vector Scheduling, where jobs are d-dimensional
vectors that need to be assigned to a set of identical machines in
a way that minimizes the maximum load over all machines and
dimensions.
Mar 18, 2019 (pondělí [Monday], 14:00, MFF UK Malá Strana S6)
Chandra Chekuri, Mark Idleman: Congestion
Minimization for Multipath Routing via Multiroute Flows.
SOSA 2018.
(presented by Ashutosh Rai)
Abstract: Congestion minimization is a well-known routing problem for which there is an O(log n/loglog n)-approximation via randomized rounding due to Raghavan and Thompson. Srinivasan formally introduced the low-congestion multi-path routing problem as a generalization of the (single-path) congestion minimization problem. The goal is to route multiple disjoint paths for each pair, for the sake of fault tolerance. Srinivasan developed a dependent randomized scheme for a special case of the multi-path problem when the input consists of a given set of disjoint paths for each pair and the goal is to select a given subset of them. Subsequently Doerr gave a different dependentrounding scheme and derandomization. Doerr et al. considered the problem where the paths have to be chosen, and applied the dependent rounding technique and evaluated it experimentally. However, their algorithm does not maintain the required disjointness property without which the problem easily reduces to the standard congestion minimization problem. In this note we show a simple algorithm that solves the problem correctly without the need for dependent rounding --- standard independent rounding suffices. This is made possible via the notion of multiroute flows originally suggested by Kishimoto et al. One advantage of the simpler rounding is an improved bound on the congestion when the path lengths are short.
Mar 11, 2019 (pondělí [Monday], 14:00, MFF UK Malá Strana S6)
Yicheng Xu, Yong Zhang, Yifei Zou: A constant
parameterized approximation for hard-capacitated k-means.
https://arxiv.org/abs/1901.04628
(presented by Tung Anh Vu)
Abstract: Hard-capacitated k-means (HCKM) is one of the remaining fundamental problems for which if there exist polynomial time constant factor approximation is not clear. But what we know is that it is at least APX-hard. Most of the existing as well as the state-of-the-art constant-factor results for hard-capacitated min-sum k-clusterings are pseudo-approximations that violate either the capacity or the cardinality constraints. In this paper, we propose an FPT approximation for HCKM without violating any hard constraints whose running time is 2^{k\log(k)}*n^{O(1)} and performance guarantee is 69+eps.
Mar 4, 2019 (pondělí [Monday], 14:00, MFF UK Malá Strana S6)
Hans Raj Tiwary: Extension
complexity of Scheduling. https://arxiv.org/abs/1902.10271
Abstract: Linear programming is a powerful method in combinatorial optimization with many applications in theory and practice. For solving a linear program quickly it is desirable to have a formulation of small size for the given problem. A useful approach for this is the construction of an {\it extended formulation}, which is a linear program in a higher dimensional space whose projection yields the original linear program. For many problems it is known that a small extended formulation cannot exist. However, most of these problems are either $\mathsf{NP}$-hard (like TSP), or only quite complicated polynomial time algorithms are known for them (like for the matching problem). We study the {\it minimum makespan problem} on identical machines in which we want to assign a set of $n$ given jobs to $m$ machines in order to minimize the maximum load over the machines. We prove that the canonical formulation for this problem has extension complexity $2^{\Omega(n/\log n)}$, even if each job has size 1 or 2 and the optimal makespan is 2. This is a case that a trivial greedy algorithm can solve optimally! We also discuss more results related to other variations of the problem.
Feb 25, 2019 (pondělí [Monday], 14:00, MFF UK Malá Strana S6)
Chandra Chekuri, Sudipto Guha, and Joseph (Seffi) Naor: The Steiner
k-Cut Problem. SIAM J. Disc. Math. 20:261-271,
2006.
(presented by Andreas Feldmann)
Abstract: We consider the Steiner k-cut problem
which generalizes both the k-cut problem and the multiway
cut problem. The Steiner k-cut problem is defined as
follows. Given an edge-weighted undirected graph $G=(V, E)$, a
subset of vertices $X \subseteq V$ called terminals, and an
integer $k \le |X|$, the objective is to find a minimum weight set
of edges whose removal results in k disconnected
components, each of which contains at least one terminal. We give
two approximation algorithms for the problem: a greedy
$(2-2/k)$-approximation based on Gomory--Hu trees, and a
$(2-2/|X|)$-approximation based on rounding a linear program. We
use the insight from the rounding to develop an exact bidirected
formulation for the global minimum cut problem (the k-cut
problem with $k=2$).