13. 12. 2016, 3. 1. 2017 (úterý [Tuesday], 10:40, MFF UK Malá Strana S8)
Yossi Azar, Amir Epstein, Lukasz Jez, Adi Vardi: Make-to-order
integrated scheduling and distribution. SODA 2016.
Also http://www.ii.uni.wroc.pl/~mbi/grants/ncn_2014/papers/2016-soda-mto-scheduling.pdf.
(referuje Martin Böhm)
Abstract: Production and distribution are fundamental operational functions in supply chains. The main challenge is to design algorithms that optimize operational performance by jointly scheduling production and delivery of customer orders. In this paper we study a model of scheduling customer orders on multiple identical machines and their distribution to customers afterwards. The goal is to minimize the total time from release to distribution plus total distribution cost to the customers. We design the first poly-logarithmic competitive algorithm for the problem, improving upon previous algorithms with linear competitive ratios. Our model generalizes two fundamental problems: scheduling of jobs on multiple identical machines (where the goal function is to minimize the total flow time) as well as the TCP Acknowledgment problem.
29. 11., 6. 12. 2016 (úterý [Tuesday], 10:40, MFF UK Malá Strana S8)
Chidambaram Annamalai, Christos Kalaitzis and Ola Svensson: Combinatorial
Algorithm for Restricted Max-Min Fair Allocation. SODA
2015. Also http://arxiv.org/abs/1409.0607.
(referuje Štěpán Šimsa)
Abstract: We study the basic allocation problem of
assigning resources to players so as
to maximize fairness. This is one of the few natural problems that
enjoys the
intriguing status of having a better estimation algorithm than
approximation
algorithm. Indeed, a certain Configuration-LP can be used to
estimate the value
of the optimal allocation to within a factor of
In this paper we significantly narrow this gap by giving a
22. 11. 2016 (úterý [Tuesday], 10:40, MFF UK Malá Strana S8)
Yossi Azar, Ilan Reuven Cohen, Alan Roytman: Online
Lower Bounds via Duality, SODA 2017. Also https://arxiv.org/abs/1604.01697.
(referuje Pavel Veselý)
Abstract: In this paper, we exploit linear programming
duality in the online setting (i.e., where input arrives on the
fly) from the unique perspective of designing lower bounds on the
competitive ratio. In particular, we provide a general technique
for obtaining online deterministic and randomized lower bounds
(i.e., hardness results) on the competitive ratio for a wide
variety of problems. We show the usefulness of our approach by
providing new, tight lower bounds for three diverse online
problems. The three problems we show tight lower bounds for are
the Vector Bin Packing problem, Ad-auctions (and various online
matching problems), and the Capital Investment problem. Our
methods are sufficiently general that they can also be used to
reconstruct existing lower bounds.
Our techniques are in stark contrast to previous works, which
exploit linear programming duality to obtain positive results,
often via the useful primal-dual scheme. We design a general
recipe with the opposite aim of obtaining negative results via
duality. The general idea behind our approach is to construct a
primal linear program based on a collection of input sequences,
where the objective function corresponds to optimizing the
competitive ratio. We then obtain the corresponding dual linear
program and provide a feasible solution, where the objective
function yields a lower bound on the competitive ratio. Online
lower bounds are often achieved by adapting the input sequence
according to an online algorithm's behavior and doing an
appropriate ad hoc case analysis. Using our unifying techniques,
we simultaneously combine these cases into one linear program and
achieve online lower bounds via a more robust analysis. We are
confident that our framework can be successfully applied to
produce many more lower bounds for a wide array of online
problems.
15. 11. 2016 (úterý [Tuesday], 10:40, MFF UK Malá Strana S8)
Alina Ene, Matthias Mnich, Marcin Pilipczuk, and Andrej
Risteski: On
routing disjoint paths in bounded treewidth graphs,
SWAT 2016. Also https://arxiv.org/abs/1512.01829.
(referuje Filip Šedivý)
Abstract: We study the problem of routing on disjoint
paths in bounded treewidth graphs with both edge and node
capacities. The input consists of a capacitated graph G
and a collection of k source-destination pairs
M={(s_1,t_1),...(s_k,t_k)}. The goal is to maximize the number of
pairs that can be routed subject to the capacities in the graph. A
routing of a subset M' of the pairs is a collection P of paths
such that, for each pair (s_i,t_i) in M', there is a path in P
connecting s_i to t_i. In the Maximum Edge Disjoint Paths (MaxEDP)
problem, the graph G has capacities cap(e) on the
edges and a routing P is feasible if each edge e is in at
most cap(e) of the paths of P. The Maximum Node Disjoint
Paths (MaxNDP) problem is the node-capacitated counterpart of
MaxEDP.
In this paper we obtain an O(r^3) approximation for MaxEDP
on graphs of treewidth at most r and a matching
approximation for MaxNDP on graphs of pathwidth at most r.
Our results build on and significantly improve the work by Chekuri
et al. [ICALP 2013] who obtained an O(r3^r) approximation
for MaxEDP.
25. 10., 1. 11. 2016 (úterý [Tuesday], 10:40, MFF UK Malá Strana S8)
Nikhil Bansal, Daniel Dadush, Shashwat Garg: An Algorithm
for Komlós Conjecture Matching Banaszczyk's bound.
FOCS 2016, also https://arxiv.org/abs/1605.02882.
(referuje Martin Böhm)
Abstract: We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most t sets. We give an efficient algorithm that finds a coloring with discrepancy O((t log n)^{1/2}), matching the best known non-constructive bound for the problem due to Banaszczyk. The previous algorithms only achieved an O(t^{1/2} log n) bound. The result also extends to the more general Komlós setting and gives an algorithmic O(log^{1/2} n) bound.
Notes: The presented algorithm is similar to the other cube-walk algorithms for discrepancy of recent years (Bansal's or Lovett and Meka's) but adds some ingenious "energy" constraints that improve the behaviour of the SDP. We will assume basic knowledge of semidefinite programming and its duality (see Gärtner, Bernd, Matoušek, Jiří: Approximation Algorithms and Semidefinite Programming, Springer, 2012.) - but mostly just the fact that (some) semidefinite programs can be closely approximated in polynomial time and that each semidefinite program has a dual which plays a similar role to the linear programming dual (under some conditions).18. 10. 2016 (úterý [Tuesday], 10:40, MFF UK Malá Strana S8)
Jon Lee, Viswanath Nagarajan, and Xiangkun Shen: Max-Cut under
Graph Constraints
http://arxiv.org/abs/1511.08152.
Abstract: An instance of the graph-constrained max-cut
(GCMC) problem consists of (i) an undirected graph G and (ii)
edge-weights on a complete undirected graph on the same vertex
set. The objective is to find a subset of vertices satisfying some
graph-based constraint in G that maximizes the total weight of
edges in the cut. The types of graph constraints we can handle
include independent set, vertex cover, dominating set and
connectivity. Our main results are for the case when G is a graph
with bounded treewidth, where we obtain a 0.5-approximation
algorithm. Our algorithm uses an LP relaxation based on the
Sherali-Adams hierarchy. It can handle any graph constraint for
which there is a (certain type of) dynamic program that exactly
optimizes linear objectives. Using known decomposition results,
these imply essentially the same approximation ratio for GCMC
under constraints such as independent set, dominating set and
connectivity on a planar graph G (more generally for bounded-genus
or excluded-minor graphs).
11. 10. 2016 (úterý [Tuesday], 10:40, MFF UK Malá Strana S8)
Pavel Vesely: Online Chromatic Number is PSPACE-Complete