15. 5., 22. 5. 2014 (čtvtek [Thursday], 14:00, MFF UK Malá Strana S8)
Nikhil Bansal and Arindam Khan: Improved
Approximation Algorithm for Two-Dimensional Bin Packing. SODA
2014.
(referuje Jan Voborník)
Abstract: We study the two-dimensional bin packing problem with and without rotations. Here we are given a set of two-dimensional rectangular items I and the goal is to pack these into a minimum number of unit square bins. We consider the orthogonal packing case where the edges of the items must be aligned parallel to the edges of the bin. Our main result is a 1.405-approximation for two-dimensional bin packing with and without rotation, which improves upon a recent 1.5 approximation due to Jansen and Pradel. We also show that a wide class of rounding based algorithms cannot improve upon the factor of 1.5.
24. 4. 2014 (čtvtek [Thursday], 14:00, MFF UK Malá Strana S8)
Lukasz Jez: Mechanism design for aggregating energy
consumption and quality of service in speed scaling scheduling
(joint work with Christoph Durr and Oscar C. Vasque)
Abstract: We consider a strategic game, where players submit jobs to a machine that executes all jobs in a way that minimizes energy while respecting the jobs' deadlines. The energy consumption is then charged to the players in some way. Each player wants to minimize the sum of that charge and of their job's deadline multiplied by a priority weight. Two charging schemes are studied, the proportional cost share which does not always admit pure Nash equilibria, and the marginal cost share, which does always admit pure Nash equilibria, at the price of overcharging by a constant factor.
10. 4., 17. 4. 2014 (čtvtek [Thursday], 14:00, MFF UK Malá Strana S8)
Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S.
Ramanujan, Saket Saurabh: Faster Parameterized
Algorithms using Linear Programming. arXiv:1203.0833
(referuje Martin Koutecký)
Abstract: We investigate the parameterized complexity
of Vertex Cover parameterized by the difference between the size
of the optimal solution and the value of the linear programming
(LP) relaxation of the problem. By carefully analyzing the change
in the LP value in the branching steps, we argue that combining
previously known preprocessing rules with the most straightforward
branching algorithm yields an
Following this, using known and new reductions, we give
27. 3., 3. 4. 2014 (čtvtek [Thursday], 14:00, MFF UK Malá Strana S8)
Anupam Gupta, Amit Kumar and Clifford Stein: Maintaining
Assignments Online: Matching, Scheduling, and Flows. SODA
2014.
(referuje Pavel Veselý)
Abstract: Consider the following edge-orientation
problem: edges of a graph appear online one-by-one and they to be
directed - given an "orientation". We want to ensure that the
indegree of each vertex remains low. (This is a simple case of
scheduling unit-sized jobs on machines, where each job can only go
on one of two machines.) If the edge-orientations we assign are
irrevocable, we suffer a signicant loss in quality due to online
decision-making (as compared to the offline performance). For
instance the best online competitive ratio achievable is
Theta(log m) for even this toy problem. But what if the decisions
are not irrevocable - what if we allow a limited number of
reassignments? Can we do much better? We show that indeed we can.
For instance, for edge-orientation, we can achieve a
constant-competitive load while doing only a constant number of
re-orientations per edge (in an amortized sense). For more
substantial problems, our results are as follows:
13. 3., 20. 3. 2014 (čtvtek [Thursday], 14:00, MFF UK Malá Strana S8)
René Sitters: Polynomial
time approximation schemes for the traveling repairman and
other minimum latency problems. SODA 2014.
(referuje Dušan Knop)
27. 2., 6. 3. 2014 (čtvtek [Thursday], 14:00, MFF UK Malá Strana S8)
Marek Cygan: Improved
Approximation for 3-Dimensional Matching via Bounded
Pathwidth Local Search. FOCS 2013. Also arXiv:1304.1424.
(referuje Martin Böhm)
Abstract: One of the most natural optimization problems
is the k-Set Packing problem, where given a family of sets of size
at most k one should select a maximum size subfamily of pairwise
disjoint sets. A special case of 3-Set Packing is the well known
3-Dimensional Matching problem. Both problems belong to the Karp`s
list of 21 NP-complete problems. The best known polynomial time
approximation ratio for k-Set Packing is (k + eps)/2 and goes back
to the work of Hurkens and Schrijver [SIDMA`89], which gives (1.5
+ eps)-approximation for 3-Dimensional Matching. Those results are
obtained by a simple local search algorithm, that uses constant
size swaps.
The main result of the paper is a new approach to local search for
k-Set Packing where only a special type of swaps is considered,
which we call swaps of bounded pathwidth. We show that for a fixed
value of k one can search the space of r-size swaps of constant
pathwidth in c^r poly(|F|) time. Moreover we present an analysis
proving that a local search maximum with respect to O(log
|F|)-size swaps of constant pathwidth yields a polynomial time (k
+ 1 + eps)/3-approximation algorithm, improving the best known
approximation ratio for k-Set Packing. In particular we improve
the approximation ratio for 3-Dimensional Matching from 3/2 + eps
to 4/3 + eps.