×

zbMATH — the first resource for mathematics

Submodular stochastic probing on matroids. (English) Zbl 1342.90112
Summary: In a stochastic probing problem we are given a universe \(E\), and a probability that each element \(e\) in \(E\) is active. We determine if an element is active by probing it, and whenever a probed element is active, we must permanently include it in our solution. Moreover, throughout the process we need to obey inner constraints on the set of elements taken into the solution, and outer constraints on the set of all probed elements. All previous algorithmic results in this framework have considered only the problem of maximizing a linear function of the active elements. Here, we consider submodular objectives.
We provide new, constant-factor approximations for maximizing a monotone submodular function subject to multiple matroid constraints on both the elements that may be taken and the elements that may be probed. We also obtain an improved approximation for linear objective functions, and show how our approach may be generalized to handle \(k\)-matchoid constraints.

MSC:
90C15 Stochastic programming
68W25 Approximation algorithms
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adamczyk M (2011) Improved analysis of the greedy algorithm for stochastic matching. Inform. Processing Lett. 111:731-737. CrossRef · Zbl 1260.68493
[2] Ageev AA, Sviridenko M (2004) Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Comb. Optim. 8(3):307-328. CrossRef · Zbl 1084.90029
[3] Agrawal S, Ding Y, Saberi A, Ye Y (2010) Correlation robust stochastic optimization. Charikar M, ed. Proc. 21st Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’10 (SIAM, Philadelphia), 1087-1096. CrossRef · Zbl 1288.90056
[4] Agrawal S, Ding Y, Saberi A, Ye Y (2012) Price of correlations in stochastic optimization. Oper. Res. 60(1):150-162. Link · Zbl 1242.90140
[5] Asadpour A, Nazerzadeh H (2014) Maximizing stochastic monotone submodular functions. arXiv preprint. http://arxiv.org/abs/0908.2788.
[6] Asadpour A, Nazerzadeh H, Saberi A (2008) Stochastic submodular maximization. Papadimitriou C, Zhang S, eds. Proc. 4th Internat. Workshop Internet Network Econom., WINE ’08 (Springer, Berlin), 477-489. CrossRef
[7] Bansal N, Gupta A, Li J, Mestre J, Nagarajan V, Rudra A (2012) When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica 63(4):733-762. CrossRef · Zbl 1254.05145
[8] Beale EML (1955) Linear programming under uncertainty. J. Roy. Statist. Soc., Ser. B 17:173-184.
[9] Călinescu G, Chekuri C, Pál M, Vondrák J (2007) Maximizing a submodular set function subject to a matroid constraint (extended abstract). Fischetti M, Williamson DP, eds. Proc. 12th Internat. Conf. Integer Programming Combinatorial Optim., IPCO (Springer, Berlin), 182-196. CrossRef · Zbl 1136.90449
[10] Chatzigeorgiou I (2013) Bounds on the Lambert function and their application to the outage analysis of user cooperation. IEEE Comm. Lett. 17(8):1505-1508. CrossRef
[11] Chawla S, Hartline JD, Malec DL, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Schulman LJ, ed. Proc. 42nd ACM Sympos. Theory Comput., STOC ’10 (ACM, New York), 311-320. CrossRef · Zbl 1293.91078
[12] Chekuri C, Vondrák J, Zenklusen R (2010) Dependent randomized rounding via exchange properties of combinatorial structures. Proc. 51st Annual IEEE Sympos. Foundations Comput. Sci., FOCS ’10 (IEEE Computer Society, Washington, DC), 575-584. CrossRef
[13] Chekuri C, Vondrák J, Zenklusen R (2011) Multi-budgeted matchings and matroid intersection via dependent rounding. Randall D, ed. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’11 (SIAM, Philadelphia), 1080-1097. CrossRef · Zbl 1377.90071
[14] Chekuri C, Vondrák J, Zenklusen R (2014) Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43(6):1831-1879. CrossRef · Zbl 1288.90081
[15] Chen N, Immorlica N, Karlin AR, Mahdian M, Rudra A (2009) Approximating matches made in heaven. Albers S, Marchetti-Spaccamela A, Matias Y, Nikoletseas S, Thomas W, eds. Proc. 36th Internat. Colloquium Automata, Languages and Programming, ICALP ’09 (Springer, Berlin), 266-278. CrossRef · Zbl 1247.05237
[16] Corless RM, Gonnet GH, Hare DEG, Jeffrey DJ, Knuth DE (1996) On the Lambert W function. Adv. Comput. Math. 5(1):329-359. CrossRef · Zbl 0863.65008
[17] Călinescu G, Chekuri C, Pál M, Vondrák J (2011) Maximizing a submodular set function subject to a matroid constraint. SIAM J. Comput. 40(6):1740-1766. CrossRef · Zbl 1234.68459
[18] Cunningham WH (1984) Testing membership in matroid polyhedra. J. Comb. Theory, Ser. B 36(2):161-188. CrossRef · Zbl 0522.90067
[19] Dantzig GB (1955) Linear programming under uncertainty. Management Sci. 1:197-206. Link · Zbl 0995.90589
[20] Dean BC, Goemans MX, Vondrák J (2005) Adaptivity and approximation for stochastic packing problems. Proc. 15th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’05 (SIAM, Philadelphia), 395-404. · Zbl 1297.90135
[21] Dean BC, Goemans MX, Vondrák J (2008) Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res. 33(4):945-964. Link · Zbl 1218.90169
[22] Feige U (1998) A threshold of ln n for approximating set cover. J. ACM 45:634-652. CrossRef · Zbl 1065.68573
[23] Feldman M, Naor J, Schwartz R (2011) A unified continuous greedy algorithm for submodular maximization. Ostrovsky R ed. Proc. 52nd Annual IEEE Sympos. Foundations Comput. Sci., FOCS ’11 (IEEE Computer Society, Washington, DC), 570-579. CrossRef · Zbl 1292.90248
[24] Fisher ML, Nemhauser GL, Wolsey LA (1978) An analysis of approximations for maximizing submodular set functions–ii. Math. Programming Stud. 8:73-87. CrossRef
[25] Goemans MX, Vondrák J (2006) Stochastic covering and adaptivity. Correa J, Hevia A, Kiwi M, eds. Proc. 7th Latin Amer. Sympos. Theoret. Informatics (Springer, Berlin), 532-543. CrossRef · Zbl 1145.90427
[26] Golovin D, Krause A (2011a) Adaptive submodular optimization under matroid constraints. arXiv preprint. http://arxiv.org/abs/1101.4450.
[27] Golovin D, Krause A (2011b) Adaptive submodularity: Theory and applications in active learning and stochastic optimization. J. Artificial Intelligence Res. 42:427-486. · Zbl 1230.90141
[28] Guha S, Munagala K (2007a) Approximation algorithms for budgeted learning problems. Johnson DS, Feige U, eds. Proc. 39th Annual ACM Sympos. Theory Comput., STOC ’07 (ACM, New York), 104-113. CrossRef · Zbl 1232.68180
[29] Guha S, Munagala K (2007b) Model-driven optimization using adaptive probes. Bansal N, Pruhs K, Stein C, eds. Proc. 18th Ann. ACM-SIAM Sympos. Discrete Algorithms, SODA ’07 (SIAM, Philadelphia), 308-317. · Zbl 1302.90179
[30] Gupta A, Krishnaswamy R, Molinaro M, Ravi R (2011) Approximation algorithms for correlated knapsacks and non-martingale bandits. Ostrovsky R, ed. Proc. 52nd Annual IEEE Sympos. Foundations Comput. Sci., FOCS ’11 (IEEE Computer Society, Washington, DC), 827-836. CrossRef · Zbl 1292.90216
[31] Gupta A, Nagarajan V (2013) A stochastic probing problem with applications. Goemans MX, Correa J, eds. Proc. 16th Internat. Conf. Integer Programming and Combinatorial Optim., IPCO ’13 (Springer, Berlin), 205-216. CrossRef · Zbl 1372.90091
[32] Hazan E, Safra S, Schwartz O (2006) On the complexity of approximating k-set packing. Comput. Complexity 15:20-39. CrossRef · Zbl 1103.90105
[33] Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. Karloff HJ, Pitassi T, eds. Proc. 44th ACM Sympos. Theory Comput., STOC ’12 (ACM, New York), 123-136. CrossRef · Zbl 1286.60037
[34] Lee J, Sviridenko M, Vondrák J (2010a) Matroid matching: The power of local search. Schulman LJ, ed. Proc. 42nd ACM Sympos. Theory Comput., STOC ’10 (ACM, New York), 369-378. CrossRef · Zbl 1293.05035
[35] Lee J, Sviridenko M, Vondrák J (2010b) Submodular maximization over multiple matroids via generalized exchange properties. Math. Oper. Res. 35(4):795-806. Link · Zbl 1216.68342
[36] Nemhauser GL, Wolsey LA (1978) Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3):177-188. Link · Zbl 0395.90072
[37] Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions–i. Math. Programming 14(1):265-294. CrossRef · Zbl 0374.90045
[38] Radlinski F, Kleinberg R, Joachims T (2008) Learning diverse rankings with multi-armed bandits. Cohen WW, McCallum A, Roweis ST, eds. Proc. Twenty-Fifth Internat. Conf. Machine Learn., ICML ’08 (ACM, New York), 784-791. CrossRef
[39] Schrijver A (2003) Combinatorial Optimization–Polyhedra and Efficiency (Springer, Berlin).
[40] Streeter M, Golovin D (2008) An online algorithm for maximizing submodular functions. Koller D, Schuurmans D, Bengio Y, Bottou L, eds. Adv. Neural Inf. Processing Systems 21 (NIPS, La Jolla, CA), 1577-1584.
[41] Vondrák J (2008) Optimal approximation for the submodular welfare problem in the value oracle model. Dwork C, ed. Proc. 40th Annual ACM Sympos. Theory Comput., STOC ’08 (ACM, New York), 67-74. CrossRef
[42] Vondrák J (2013) Personal correspondence.
[43] Williams D (1991) Probability with Martingales, Cambridge mathematical textbooks (Cambridge University Press, Cambridge, UK). CrossRef
[44] Yan Q (2011) Mechanism design via correlation gap. Randall D, ed. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’11 (SIAM, Philadelphia), 710-719. CrossRef · Zbl 1377.91108
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.