Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems
详细信息 查看全文
- 作者：Pierre Fraigniaud ; Magnús M. Halldórsson ; Boaz Patt-Shamir ; Dror Rawitz…
- 关键词：Competitive analysis ; Randomized algorithm ; Packing integer programs ; Online set packing ; Team formation ; Prize ; collecting multi ; covering
- 刊名：Algorithmica
- 出版年：2016
- 出版时间：April 2016
- 年：2016
- 卷：74
- 期：4
- 页码：1205-1223
- 全文大小：506 KB
- 参考文献：1.Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: The online set cover problem. SIAM J. Comput. 39(2), 361–370 (2009)MathSciNet CrossRef MATH
2.Awerbuch, B., Azar, Y., Plotkin, S.A.: Throughput-competitive on-line routing. In: 34th IEEE Annual Symposium on Foundations of Computer Science, pp. 32–40 (1993)
3.Bateni, M., Hajiaghayi, M., Zadimoghaddam, M.: Submodular secretary problem and extensions. In: 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, Volume 6302 of LNCS, pp. 39–52 (2010)
4.Berman, P.: A \(d/2\) approximation for maximum weight independent set in \(d\) -claw free graphs. Nord. J. Comput. 7(3), 178–184 (2000)MathSciNet MATH
5.Buchbinder, N., Naor, J.: Online primal-dual algorithms for covering and packing. Math. Oper. Res. 34(2), 270–286 (2009)MathSciNet CrossRef MATH
6.Chekuri, C., Khanna, S.: On multidimensional packing problems. SIAM J. Comput. 33(4), 837–851 (2004)MathSciNet CrossRef MATH
7.Cygan, M.: Improved approximation for 3-dimensional matching via bounded pathwidth local search. In: 54th IEEE Annual Symposium on Foundations of Computer Science, pp. 509–518 (2013)
8.Emek, Y., Halldórsson, M.M., Mansour, Y., Patt-Shamir, B., Radhakrishnan, J., Rawitz, D.: Online set packing. SIAM J. Comput. 41(4), 728–746 (2012)MathSciNet CrossRef MATH
9.Feldman, M., Naor, J.S., Schwartz, R.: Improved competitive ratios for submodular secretary problems. In: 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, Volume 6845 of LNCS, pp. 218–229 (2011)
10.Freeman, P.: The secretary problem and its extensions: a review. Int. Stat. Rev. 51(2), 189–206 (1983)MathSciNet CrossRef MATH
11.Frieze, A.M., Clarke, M.R.B.: Approximation algorithms for the \(m\) -dimensional 0–1 knapsack problem: worst-case and probabilistic analyses. Eur. J. Oper. Res. 15, 100–109 (1984)MathSciNet CrossRef MATH
12.Gilbert, J.P., Mosteller, F.: Recognizing the maximum of a sequence. J. Am. Stat. Assoc. 61(313), 35–73 (1966)MathSciNet CrossRef
13.Halldórsson, M.M., Kratochvíl, J., Telle, J.A.: Independent sets with domination constraints. Discrete Appl. Math. 99(1–3), 39–54 (2000)MathSciNet CrossRef MATH
14.Halldórsson, M.M., Patt-Shamir, B., Rawitz, D.: Online scheduling with interval conflicts. Theory Comput. Syst. 53(2), 300–317 (2013)MathSciNet CrossRef MATH
15.Håstad, J.: Clique is hard to approximate within \(n^{1-\epsilon }\) . Acta Math. 182(1), 105–142 (1999)MathSciNet CrossRef
16.Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating k-set packing. Comput. Complex. 15(1), 20–39 (2006)MathSciNet CrossRef MATH
17.Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4), 463–468 (1975)MathSciNet CrossRef MATH
18.Magazine, M.J., Chern, M.-S.: A note on approximation schemes for multidimensional knapsack problems. Math. Oper. Res. 9(2), 244–247 (1984)MathSciNet CrossRef MATH
19.Mansour, Y., Patt-Shamir, B., Rawitz, D.: Competitive router scheduling with structured data. Theor. Comput. Sci. 530, 12–22 (2014)MathSciNet CrossRef MATH
20.Raghavan, P., Thompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4), 365–374 (1987)MathSciNet CrossRef MATH
21.Sahni, S.: Approximate algorithms for the 0/1 knapsack problem. J. ACM 22(1), 115–124 (1975)MathSciNet CrossRef MATH
22.Srinivasan, A.: Improved approximations of packing and covering problems. In: 27th Annual ACM Symposium on the Theory of Computing, pp. 268–276 (1995) - 作者单位：Pierre Fraigniaud (1)
Magnús M. Halldórsson (2)
Boaz Patt-Shamir (3)
Dror Rawitz (4)
Adi Rosén (1)
1. LIAFA, CNRS, University Paris Diderot, Paris, France
2. ICE-TCS, School of Computer Science, Reykjavik University, 101, Reykjavík, Iceland
3. School of Electrical Engineering, Tel Aviv University, Tel Aviv, 69978, Israel
4. Faculty of Engineering, Bar-Ilan University, Ramat Gan, 52900, Israel - 刊物类别：Computer Science
- 刊物主题：Algorithm Analysis and Problem Complexity
Theory of Computation
Mathematics of Computing
Algorithms
Computer Systems Organization and Communication Networks
Data Structures, Cryptology and Information Theory - 出版者：Springer New York
- ISSN：1432-0541
文摘
We consider two new variants of online integer programs that are duals. In the packing problem we are given a set of items and a collection of knapsack constraints over these items that are revealed over time in an online fashion. Upon arrival of a constraint we may need to remove several items (irrevocably) so as to maintain feasibility of the solution. Hence, the set of packed items becomes smaller over time. The goal is to maximize the number, or value, of packed items. The problem originates from a buffer-overflow model in communication networks, where items represent information units broken into multiple packets. The other problem considered is online covering: there is a universe to be covered. Sets arrive online, and we must decide for each set whether we add it to the cover or give it up. The cost of a solution is the total cost of sets taken, plus a penalty for each uncovered element. The number of sets in the solution grows over time, but its cost goes down. This problem is motivated by team formation, where the universe consists of skills, and sets represent candidates we may hire. The packing problem was introduced in Emek et al. (SIAM J Comput 41(4):728–746, 2012) for the special case where the matrix is binary; in this paper we extend the solution to general matrices with non-negative integer entries. The covering problem is introduced in this paper; we present matching upper and lower bounds on its competitive ratio.