Invited Session Tue.1.H 3005

Tuesday, 10:30 - 12:00 h, Room: H 3005

Cluster 2: Combinatorial optimization [...]

Submodularity and covering


Chair: Jon Lee



Tuesday, 10:30 - 10:55 h, Room: H 3005, Talk 1

Maxim Sviridenko
New and improved bounds for the minimum set cover problem

Coauthor: Rishi Saket


We study the relationship between the approximation factor for the
set-cover problem and the parameters D, the maximum cardinality
of any subset, and k, the maximum number of subsets containing any
element of the ground set. We show an LP rounding based approximation
of (k-1)(1-e-ln D/(k-1)) +1, which is substantially
better than the classical algorithms when k is approximately ln D, and also
improves on related previous works. For the interesting case when k = θ(log D) we also exhibit an integrality gap which essentially matches our approximation algorithm.
We also prove a hardness of approximation factor of Ω (log
D/ (loglog D)2)
when k=θ(log D).
This is the first study of the hardness factor specifically for this range
of k and D, and improves on the only other
such result implicitly proved before.



Tuesday, 11:00 - 11:25 h, Room: H 3005, Talk 2

Andreas Krause
Adaptive submodularity: Theory and applications in active learning and stochastic optimization

Coauthor: Daniel Golovin


Solving stochastic optimization problems under partial observability, where one needs to adaptively make decisions with uncertain outcomes, is a fundamental but notoriously difficult challenge. In this talk, I will introduce a new concept called adaptive submodularity, which generalizes submodular set functions to adaptive policies.
In many respects adaptive submodularity plays the same role for adaptive problems as submodularity plays for nonadaptive problems. Specifically, just as many nonadaptive problems with submodular objectives have efficient algorithms with good approximation guarantees, so too do adaptive problems with adaptive submodular objectives. We use this fact to recover and generalize several previous results in adaptive optimization, including results for active learning and adaptive variants of maximum coverage and set cover. We show how to apply these results to several applications, including observation selection and sensor placement problems, sequential experimental design, and adaptive viral marketing.



Tuesday, 11:30 - 11:55 h, Room: H 3005, Talk 3

Rico Zenklusen
Matroids and integrality gaps for hypergraphic Steiner tree relaxations

Coauthors: Michel Goemans, Neil Olver, Thomas Rothvoss


Until recently, LP relaxations have only played a very limited role in the design of approximation algorithms for the Steiner tree problem. In particular, no (efficiently solvable) Steiner tree relaxation was known to have an integrality gap bounded away from 2. This changed when Byrka, Grandoni, Rothvoss and Sanità demonstrated in 2010 a ln (4)+ε≈1.39 approximation algorithm based on a so-called hypergraphic LP relaxation. Interestingly, even though their approach is LP based, they do not obtain a matching bound on the integrality gap, showing only a weaker 1.55 bound by other methods.
We show that indeed the integrality gap is bounded by ln(4). In the process, we obtain a much better structural understanding of hypergraphic LPs, as well as more efficient algorithms. Our approach is heavily based on techniques from the theory of matroids and submodular functions.


  personal loans. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.