Primal beats dual on online packing LPs in the random-order model. (English) Zbl 1315.68291
Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 303-312 (2014).
MSC:
| 68W27 | Online algorithms; streaming algorithms |
| 68W20 | Randomized algorithms |
| 90C05 | Linear programming |
Software:
SuLQReferences:
| [1] | S. Agrawal, Z. Wang, and Y. Ye. A dynamic near-optimal algorithm for online linear programming. CoRR, abs/0911.2974, 2009. |
| [2] | M. Babaioff, N. Immorlica, D. Kempe, and R. Kleinberg. A knapsack secretary problem with applications. In APPROX, pages 16-28, 2007. 10.1007/978-3-540-74208-1_2 · Zbl 1171.90417 |
| [3] | N. Bansal, N. Korula, V. Nagarajan, and A. Srinivasan. Solving packing integer programs via randomized rounding with alterations. Theory of Computing, 8(1):533-565, 2012. · Zbl 1297.68259 |
| [4] | N. Buchbinder and J. Naor. Online primal-dual algorithms for covering and packing. Math. Oper. Res., 34(2):270-286, 2009. 10.1287/moor.1080.0363 · Zbl 1216.68335 |
| [5] | N. R. Devanur and T. P. Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In ACM Conference on Electronic Commerce, pages 71-78, 2009. 10.1145/1566374.1566384 |
| [6] | N. R. Devanur, K. Jain, B. Sivan, and C. A. Wilkens. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. In ACM Conference on Electronic Commerce, pages 29-38, 2011. 10.1145/1993574.1993581 |
| [7] | E. B. Dynkin. The optimum choice of the instant for stopping a markov process. In Sov. Math. Dokl, volume 4, pages 627-629, 1963. · Zbl 0242.60018 |
| [8] | J. Feldman, M. Henzinger, N. Korula, V. S. Mirrokni, and C. Stein. Online stochastic packing applied to display ad allocation. In ESA (1), pages 182-194, 2010. · Zbl 1287.68186 |
| [9] | G. Goel and A. Mehta. Online budgeted matching in random input models with applications to adwords. In SODA, pages 982-991, 2008. · Zbl 1192.68482 |
| [10] | C. Karande, A. Mehta, and P. Tripathi. Online bipartite matching with unknown distributions. In STOC, pages 587-596, 2011. 10.1145/1993636.1993715 · Zbl 1288.68287 |
| [11] | R. M. Karp, U. V. Vazirani, and V. V. Vazirani. An optimal algorithm for on-line bipartite matching. In STOC, pages 352-358, 1990. 10.1145/100216.100262 |
| [12] | T. Kesselheim, K. Radke, A. Tönnis, and B. Vöcking. An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In ESA, pages 589-600, 2013. · Zbl 1394.68448 |
| [13] | R. D. Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In SODA, pages 630-631, 2005. · Zbl 1297.68268 |
| [14] | N. Korula and M. Pál. Algorithms for secretary problems on graphs and hypergraphs. In ICALP (2), pages 508-520, 2009. 10.1007/978-3-642-02930-1_42 · Zbl 1248.68573 |
| [15] | R. Lavi and C. Swamy. Truthful and near-optimal mechanism design via linear programming. J. ACM, 58(6):25, 2011. 10.1145/2049697.2049699 · Zbl 1281.91091 |
| [16] | D. V. Lindley. Dynamic programming and decision theory. Applied Statistics, pages 39-51, 1961. · Zbl 0114.34904 |
| [17] | M. Mahdian and Q. Yan. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. In STOC, pages 597-606, 2011. 10.1145/1993636.1993716 · Zbl 1288.68288 |
| [18] | A. Mehta, A. Saberi, U. V. Vazirani, and V. V. Vazirani. Adwords and generalized online matching. J. ACM, 54(5), 2007. 10.1145/1284320.1284321 · Zbl 1312.68239 |
| [19] | M. Molinaro and R. Ravi. Geometry of online packing linear programs. In ICALP (1), pages 701-713, 2012. 10.1007/978-3-642-31594-7_59 · Zbl 1272.68473 |
| [20] | A. Panconesi and A. Srinivasan. Randomized distributed edge coloring via an extension of the chernoff-hoeffding bounds. SIAM J. Comput., 26(2):350-368, 1997. 10.1137/S0097539793250767 · Zbl 0867.05063 |
| [21] | D. Pritchard and D. Chakrabarty. Approximability of sparse integer programs. Algorithmica, 61(1):75-93, 2011. 10.1007/s00453-010-9431-z · Zbl 1218.68198 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
