File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids

TitleOnline Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids
Authors
Issue Date2017
PublisherSociety for Industrial and Applied Mathematics.
Citation
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16-19 January 2017, p. 1204-1223 How to Cite?
AbstractWe 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 1/α∞ ≈ 0.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 1/α∞ ≈ 0.3178. Finally, our techniques can be extended to a more general problem that generalizes both the online sub-modular maximization problem and the online bipartite matching problem with free disposal. Using the techniques developed in this paper, we give constant-competitive algorithms for the submodular online bipartite matching problem.
Persistent Identifierhttp://hdl.handle.net/10722/241683
ISBN

 

DC FieldValueLanguage
dc.contributor.authorChan, HTH-
dc.contributor.authorHuang, Z-
dc.contributor.authorJiang, S-
dc.contributor.authorKang, N-
dc.contributor.authorTang, Z-
dc.date.accessioned2017-06-20T01:47:07Z-
dc.date.available2017-06-20T01:47:07Z-
dc.date.issued2017-
dc.identifier.citationProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16-19 January 2017, p. 1204-1223-
dc.identifier.isbn978-1-61197-478-2-
dc.identifier.urihttp://hdl.handle.net/10722/241683-
dc.description.abstractWe 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 1/α∞ ≈ 0.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 1/α∞ ≈ 0.3178. Finally, our techniques can be extended to a more general problem that generalizes both the online sub-modular maximization problem and the online bipartite matching problem with free disposal. Using the techniques developed in this paper, we give constant-competitive algorithms for the submodular online bipartite matching problem.-
dc.languageeng-
dc.publisherSociety for Industrial and Applied Mathematics.-
dc.relation.ispartofProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms-
dc.rightsProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Copyright © Society for Industrial and Applied Mathematics.-
dc.titleOnline Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids-
dc.typeConference_Paper-
dc.identifier.emailChan, HTH: hubert@cs.hku.hk-
dc.identifier.emailHuang, Z: hzhiyi@hku.hk-
dc.identifier.authorityChan, HTH=rp01312-
dc.identifier.authorityHuang, Z=rp01804-
dc.identifier.doi10.1137/1.9781611974782.78-
dc.identifier.hkuros272617-
dc.identifier.spage1204-
dc.identifier.epage1223-
dc.publisher.placePhiladelphia, PA-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats