{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,14]],"date-time":"2026-09-14T03:02:03Z","timestamp":1789354923563,"version":"build-2803163510"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540287025","type":"print"},{"value":"9783540318675","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11549345_53","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T10:05:47Z","timestamp":1127815547000},"page":"615-627","source":"Crossref","is-referenced-by-count":20,"title":["Greedy Approximation via Duality for Packing, Combinatorial Auctions and Routing"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Krysta","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"53_CR1","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF02122549","volume":"8","author":"R. Aharoni","year":"1988","unstructured":"Aharoni, R., Erd\u00f6s, P., Linial, N.: Optima of dual linear programs. Combinatorica\u00a08, 13\u201320 (1988)","journal-title":"Combinatorica"},{"key":"53_CR2","unstructured":"Archer, A., Papadimitriou, C.H., Talwar, K., Tardos, \u00c9.: An approximate truthful mechanism for combinatorial auctions with single parameter agents. In: Proc.\u00a014th ACM-SIAM Symposium on Discrete Algorithms, SODA (2003)"},{"key":"53_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/3-540-45535-3_2","volume-title":"Integer Programming and Combinatorial Optimization","author":"Y. Azar","year":"2001","unstructured":"Azar, Y., Regev, O.: Strongly polynomial algorithms for the unsplittable flow problem. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol.\u00a02081, p. 15. Springer, Heidelberg (2001)"},{"key":"53_CR4","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Gonen, R., Nisan, N.: Incentive Compatible Multi-Unit Combinatorial Auctions. In: Proc.\u00a09th conference on Theoretical Aspects of Rationality and Knowledge (TARK), Bloomington, IN, USA (June 2003)","DOI":"10.1145\/846241.846250"},{"key":"53_CR5","unstructured":"Berman, P., Krysta, P.: Optimizing misdirection. In: Proc.\u00a014th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 192\u2013201 (2003)"},{"key":"53_CR6","doi-asserted-by":"crossref","unstructured":"Briest, P., Krysta, P., V\u00f6cking, B.: Approximation Techniques for Utilitarian Mechanism Design. In: Proc.\u00a037th ACM Symposium on Theory of Computing, STOC (2005)","DOI":"10.1145\/1060590.1060597"},{"key":"53_CR7","unstructured":"Chekuri, C., Khanna, S.: Edge-disjoint paths revisited. In: Proc.\u00a014th ACM-SIAM Symposium on Discrete Algorithms, SODA (2003)"},{"key":"53_CR8","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: A greedy heuristic for the set-covering problem. Mathematics of Operations Research\u00a04, 233\u2013235 (1979)","journal-title":"Mathematics of Operations Research"},{"key":"53_CR9","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1287\/moor.7.4.515","volume":"7","author":"G. Dobson","year":"1982","unstructured":"Dobson, G.: Worst-case analysis of greedy heuristics for integer programming with non-negative data. Mathematics of Operations Research\u00a07, 515\u2013531 (1982)","journal-title":"Mathematics of Operations Research"},{"key":"53_CR10","doi-asserted-by":"crossref","unstructured":"Gonen, R., Lehmann, D.J.: Optimal solutions for multi-unit combinatorial auctions: branch and bound heuristics. In: Proc.\u00a02nd ACM Conference on Electronic Commerce, EC (2000)","DOI":"10.1145\/352871.352873"},{"key":"53_CR11","doi-asserted-by":"crossref","unstructured":"Gonen, R., Lehmann, D.J.: Linear Programming Helps Solve Large Multi-Unit Combinatorial Auctions. In: Proceedings of INFORMS 2001 (November 2001)","DOI":"10.1145\/352871.352873"},{"key":"53_CR12","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Khanna, S., Rajagopalan, R., Shepherd, B., Yannakakis, M.: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. In: Proc.\u00a031st ACM Symposium on Theory of Computing, STOC (1999)","DOI":"10.1145\/301250.301262"},{"key":"53_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/BFb0055051","volume-title":"Automata, Languages and Programming","author":"M.M. Halld\u00f3rsson","year":"1998","unstructured":"Halld\u00f3rsson, M.M., Kratochv\u00edl, J., Telle, J.A.: Independent sets with domination constraints. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, p. 176. Springer, Heidelberg (1998)"},{"key":"53_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BFb0053959","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"M.M. Halld\u00f3rsson","year":"1998","unstructured":"Halld\u00f3rsson, M.M.: A survey on independent set approximations. In: Jansen, K., Rolim, J.D.P. (eds.) APPROX 1998. LNCS, vol.\u00a01444, pp. 1\u201314. Springer, Heidelberg (1998)"},{"issue":"1","key":"53_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00020","volume":"4","author":"M.M. Halld\u00f3rsson","year":"2000","unstructured":"Halld\u00f3rsson, M.M.: Approximations of Weighted Independent Set and Hereditary Subset Problems. Journal of Graph Algorithms and Applications\u00a04(1), 1\u201316 (2000)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"53_CR16","volume-title":"Inequalities","author":"G. Hardy","year":"1997","unstructured":"Hardy, G., Littlewood, J.E., Polya, G.: Inequalities, 2nd edn. Cambridge Univ.\u00a0Press, Cambridge (1997)","edition":"2"},{"key":"53_CR17","doi-asserted-by":"crossref","unstructured":"Hastad, J.: Clique is hard to approximate within n 1\u2009\u2212\u2009\u03b5 . In: Proc.\u00a0IEEE FOCS (1996)","DOI":"10.1109\/SFCS.1996.548522"},{"key":"53_CR18","series-title":"Lecture Notes in Computer Science","volume-title":"Proc.\u00a0APPROX","author":"E. Hazan","year":"2003","unstructured":"Hazan, E., Safra, S., Schwartz, O.: On the hardness of approximating k-dimensional matching. In: Proc.\u00a0APPROX. LNCS, Springer, Heidelberg (2003)"},{"key":"53_CR19","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"D.S. Hochbaum","year":"1983","unstructured":"Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover, and set packing problems. Discrete Applied Mathematics\u00a06, 243\u2013254 (1983)","journal-title":"Discrete Applied Mathematics"},{"key":"53_CR20","unstructured":"Kleinberg, J.: Approximation algorithms for disjoint paths problems. PhD thesis, MIT (1996)"},{"key":"53_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/3-540-69346-7_12","volume-title":"Integer Programming and Combinatorial Optimization","author":"S.G. Kolliopoulos","year":"1998","unstructured":"Kolliopoulos, S.G., Stein, C.: Approximating disjoint-path problems using greedy algorithms and packing integer programs. In: Bixby, R.E., Boyd, E.A., R\u00edos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol.\u00a01412, pp. 153\u2013162. Springer, Heidelberg (1998)"},{"issue":"3","key":"53_CR22","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/S0020-0190(03)00351-X","volume":"88","author":"P. Kolman","year":"2003","unstructured":"Kolman, P.: A note on the greedy algorithm for the unsplittable flow problem. Information Processing Letters\u00a088(3), 101\u2013105 (2003)","journal-title":"Information Processing Letters"},{"key":"53_CR23","unstructured":"Kolman, P., Scheideler, C.: Improved bounds for the unsplittable flow problem. In: Proc.\u00a013th ACM-SIAM Symposium on Discrete Algorithms, SODA (2002)"},{"key":"#cr-split#-53_CR24.1","doi-asserted-by":"crossref","unstructured":"Lehmann, D., Ita O\u2019Callaghan, L., Shoham, Y.: Truth revelation in rapid, approximately efficient combinatorial auctions. In: Proc.\u00a01st ACM Conference on Electronic Commerce, EC (1999);","DOI":"10.1145\/336992.337016"},{"key":"#cr-split#-53_CR24.2","doi-asserted-by":"crossref","unstructured":"Journal version. Journal of the ACM\u00a049(5), 577\u2013602 (2002)","DOI":"10.1145\/585265.585266"},{"key":"53_CR25","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers. Discrete Mathematics\u00a013, 383\u2013390 (1975)","journal-title":"Discrete Mathematics"},{"key":"53_CR26","unstructured":"Mu\u2019alem, A., Nisan, N.: Truthful Approximation Mechanisms for Restricted Combinatorial Auctions. In: Proc.\u00a018th National AAAI Conference on Artificial Intelligence (2002)"},{"key":"53_CR27","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"Raghavan, P.: Probabilistic construction of deterministic algorithms: Approximating packing integer programs. Journal of Computer and System Sciences\u00a037, 130\u2013143 (1988)","journal-title":"Journal of Computer and System Sciences"},{"key":"53_CR28","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"Raghavan, P., Thompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica\u00a07, 365\u2013374 (1987)","journal-title":"Combinatorica"},{"key":"53_CR29","doi-asserted-by":"crossref","unstructured":"Rajagopalan, S., Vazirani, V.V.: Primal-dual RNC approximation algorithms for set cover and covering integer programs. SIAM Journal on Computing\u00a028(2) (1998)","DOI":"10.1137\/S0097539793260763"},{"key":"53_CR30","unstructured":"Srinivasan, A.: A extension of the Lov\u00e1sz Local Lemma and its applications to integer programming. In: Proc.\u00a07th ACM-SIAM Symposium on Discrete Algorithms, SODA (1996)"},{"key":"53_CR31","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1137\/S0097539796314240","volume":"29","author":"A. Srinivasan","year":"1999","unstructured":"Srinivasan, A.: Improved Approximation Guarantees for Packing and Covering Integer Programs. SIAM Journal on Computing\u00a029, 648\u2013670 (1999)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11549345_53.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,4]],"date-time":"2023-05-04T15:42:15Z","timestamp":1683214935000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11549345_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540287025","9783540318675"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/11549345_53","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}