Kesselheim, Thomas ;
Tönnis, Andreas
Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints
Abstract
We study various generalizations of the secretary problem with submodular objective functions. Generally, a set of requests is revealed stepbystep 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 alphaapproximation 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 kuniform 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.31alphacompetitive 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.207alphacompetitive 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/(B1)))competitive algorithm for submodular function maximization subject to linear packing constraints. Here, d is the column sparsity, that is the maximal number of nonezero 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^(1/(B1)))competitive if both d and B are known to the algorithm beforehand.
BibTeX  Entry
@InProceedings{kesselheim_et_al:LIPIcs:2017:7565,
author = {Thomas Kesselheim and Andreas T{\"o}nnis},
title = {{Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
pages = {16:116:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770446},
ISSN = {18688969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7565},
URN = {urn:nbn:de:0030drops75657},
doi = {10.4230/LIPIcs.APPROXRANDOM.2017.16},
annote = {Keywords: Secretary Problem, Online Algorithms, Submodular Maximization}
}
11.08.2017
Keywords: 

Secretary Problem, Online Algorithms, Submodular Maximization 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Issue date: 

2017 
Date of publication: 

11.08.2017 