File Download
There are no files associated with this item.
Supplementary

Citations:
 Appears in Collections:
Conference Paper: Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids
Title  Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids 

Authors  
Issue Date  2017 
Publisher  Society for Industrial and Applied Mathematics. 
Citation  Proceedings of the TwentyEighth Annual ACMSIAM Symposium on Discrete Algorithms, Barcelona, Spain, 1619 January 2017, p. 12041223 How to Cite? 
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 kuniform 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.25competitive even for partition matroids, the most modest generalization of kuniform 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 (nonmonotone) 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 submodular maximization problem and the online bipartite matching problem with free disposal. Using the techniques developed in this paper, we give constantcompetitive algorithms for the submodular online bipartite matching problem. 
Persistent Identifier  http://hdl.handle.net/10722/241683 
ISBN 
DC Field  Value  Language 

dc.contributor.author  Chan, HTH   
dc.contributor.author  Huang, Z   
dc.contributor.author  Jiang, S   
dc.contributor.author  Kang, N   
dc.contributor.author  Tang, Z   
dc.date.accessioned  20170620T01:47:07Z   
dc.date.available  20170620T01:47:07Z   
dc.date.issued  2017   
dc.identifier.citation  Proceedings of the TwentyEighth Annual ACMSIAM Symposium on Discrete Algorithms, Barcelona, Spain, 1619 January 2017, p. 12041223   
dc.identifier.isbn  9781611974782   
dc.identifier.uri  http://hdl.handle.net/10722/241683   
dc.description.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 kuniform 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.25competitive even for partition matroids, the most modest generalization of kuniform 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 (nonmonotone) 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 submodular maximization problem and the online bipartite matching problem with free disposal. Using the techniques developed in this paper, we give constantcompetitive algorithms for the submodular online bipartite matching problem.   
dc.language  eng   
dc.publisher  Society for Industrial and Applied Mathematics.   
dc.relation.ispartof  Proceedings of the TwentyEighth Annual ACMSIAM Symposium on Discrete Algorithms   
dc.rights  Proceedings of the TwentyEighth Annual ACMSIAM Symposium on Discrete Algorithms. Copyright © Society for Industrial and Applied Mathematics.   
dc.title  Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids   
dc.type  Conference_Paper   
dc.identifier.email  Chan, HTH: hubert@cs.hku.hk   
dc.identifier.email  Huang, Z: hzhiyi@hku.hk   
dc.identifier.authority  Chan, HTH=rp01312   
dc.identifier.authority  Huang, Z=rp01804   
dc.identifier.doi  10.1137/1.9781611974782.78   
dc.identifier.hkuros  272617   
dc.identifier.spage  1204   
dc.identifier.epage  1223   
dc.publisher.place  Philadelphia, PA   