Colloquium of Research Area KL - achtes Kolloquium
Colloquium of Research Area KL - achtes Kolloquium

8th Colloquium of Research Area KL

Date: July 21, 2017

Venue:  Seminar room 1st floor, Arithmeum, Lennéstr. 2, Bonn

Homepage: Research Institute for Discrete Mathematics


15:45 Coffee and Tee
16:15 Jens Vygen: On the Integrality Gap of the Prize-Collecting Steiner Forest LP
17:00 Coffee break
17:30 Andreas Tönnis: Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints
  After the Colloquium there will be the opportunity to have dinner together


Jens Vygen: On the Integrality Gap of the Prize-Collecting Steiner Forest LP

In the prize-collecting Steiner forest (PCSF) problem, we are given an undirected graph G=(V,E), edge costs c, and terminal pairs with penalties; the goal is to find a forest F to minimize c(F) plus the sum of the penalties of disconnected terminal pairs. The Steiner forest problem can be viewed as the special case where penalties are infinite.

It was widely believed that the integrality gap of the natural (and well-studied) linear-programming (LP) relaxation for PCSF is at most 2. We dispel this belief by showing that the integrality gap of this LP is at least 9/4. This holds even for planar graphs.

We also show that using this LP, one cannot devise a Lagrangian-multiplier-preserving (LMP) algorithm with approximation guarantee better than 4. Our results thus show a separation between the integrality gaps of the LP-relaxations for prize-collecting and non-prize-collecting (i.e., standard) Steiner forest, as well as the approximation ratios achievable relative to the optimal LP solution by LMP- and non-LMP- approximation algorithms for PCSF. For the special case of prize-collecting Steiner tree (PCST), we prove that the natural LP relaxation admits basic feasible solutions with all coordinates of value at most 1/3 and all edge variables positive. Thus, we rule out the possibility of approximating PCST with guarantee better than 3 using a direct iterative rounding method.

This is joint work with Jochen Könemann, Neil Olver, Kanstantsin Pashkovich, R. Ravi, and Chaitanya Swamy,


Andreas Tönnis: Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints

We study various generalizations of the secretary problem with submodular objective functions. Generally, a set of requests is revealed step-by-step to an algorithm in random order. For each request, one option has to be selected so as to maximize a monotone submodular function while ensuring feasibility. For our results, we assume that we are given an offline algorithm computing an \alpha-approximation for the respective problem. This way, we separate computational limitations from the ones due to the online nature. When only focusing on the online aspect, we can assume \alpha = 1

In the submodular secretary problem, feasibility constraints are cardinality constraints, or equivalently, sets are feasible if and only if they are independent sets of a k-uniform matroid. That is, out of a randomly ordered stream of entities, one has to select a subset of size k. For this problem, we present a 0.31\alpha-competitive algorithm for all k, which asymptotically reaches competitive ratio \alpha/e for large k. In submodular secretary matching, one side of a bipartite graph is revealed online. Upon arrival, each node has to be matched permanently to an offline node or discarded irrevocably. We give a 0.207\alpha-competitive algorithm. This also covers the problem, in which sets of entities are feasible if and only if they are independent with respect to a transversal matroid. In both cases, we improve over previously best known competitive ratios, using a generalization of the algorithm for the classic secretary problem.

Furthermore, we give an ;O(\alpha d^{-2/(B-1)})-competitive algorithm for submodular function maximization subject to linear packing constraints. Here, d is the column sparsity, that is the maximal number of none-zero entries in a column of the constraint matrix, and B is the minimal capacity of the constraints. Notably, this bound is independent of the total number of constraints. We improve the algorithm to be ;O(\alpha d^{-2/(B-1)})-competitive if both d and B are known to the algorithm beforehand.