Online submodular maximization with free disposal: randomization beats 14 for partition matroids

DOI10.1137/1.9781611974782.78MaRDI QIDQ4575820zbMATH OpenOpenAlexFDO

Authors

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.07770

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27) Combinatorial optimization (90C27)

Abstract: We study the online submodular maximization problem with free disposal under a matroid constraint. Elements from some ground set arrive one by one in rounds, and the algorithm maintains a feasible set that is independent in the underlying matroid. In each round when a new element arrives, the algorithm may accept the new element into its feasible set and possibly remove elements from it, provided that the resulting set is still independent. The goal is to maximize the value of the final feasible set under some monotone submodular function, to which the algorithm has oracle access. For $k$-uniform matroids, we give a deterministic algorithm with competitive ratio at least $0.2959$, and the ratio approaches $frac1alph{a}_{i}nftyapprox0.3178$ as $k$ approaches infinity, improving the previous best ratio of $0.25$ by Chakrabarti and Kale (IPCO 2014), Buchbinder et al. (SODA 2015) and Chekuri et al. (ICALP 2015). We also show that our algorithm is optimal among a class of deterministic monotone algorithms that accept a new arriving element only if the objective is strictly increased. Further, we prove that no deterministic monotone algorithm can be strictly better than $0.25$-competitive even for partition matroids, the most modest generalization of $k$-uniform matroids, matching the competitive ratio by Chakrabarti and Kale (IPCO 2014) and Chekuri et al. (ICALP 2015). Interestingly, we show that randomized algorithms are strictly more powerful by giving a (non-monotone) randomized algorithm for partition matroids with ratio $frac1alph{a}_{i}nftyapprox0.3178$.

Recommendations

• Online Submodular Maximization with Free Disposal
• Submodular secretary problems: cardinality, matching, and linear constraints
• Approximation algorithms for online weighted rank function maximization under matroid constraints

Cited in

(16)

• Non-submodular streaming maximization with minimum memory and low adaptive complexity
• Multi-pass streaming algorithms for monotone submodular function maximization
• Online algorithms for BP functions maximization
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Approximation algorithms for online weighted rank function maximization under matroid constraints
• Online Submodular Maximization with Free Disposal
• Online submodular maximization with preemption
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• General bounds for incremental maximization
• Online Submodular Maximization Problem with Vector Packing Constraint.
• Online submodular maximization with preemption
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Two-sided capacitated submodular maximization in gig platforms
• Fair maximization of monotone submodular functions in data streams
• Streaming algorithms for maximizing k-submodular functions under a partition matroid constraint
• Streaming submodular maximization with fairness constraints for massive data summarization

This page was built for publication: Online submodular maximization with free disposal: randomization beats \(\frac{1}{4}\) for partition matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575820)