{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T19:54:17Z","timestamp":1769975657600,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540407706","type":"print"},{"value":"9783540451983","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45198-3_8","type":"book-chapter","created":{"date-parts":[[2011,1,7]],"date-time":"2011-01-07T22:32:30Z","timestamp":1294439550000},"page":"83-97","source":"Crossref","is-referenced-by-count":30,"title":["On the Complexity of Approximating k-Dimensional Matching"],"prefix":"10.1007","author":[{"given":"Elad","family":"Hazan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shmuel","family":"Safra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oded","family":"Schwartz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/BF01277956","volume":"5","author":"N. Alon","year":"1995","unstructured":"Alon, N., Fiege, U., Wigderson, A., Zuckerman, D.: Derandomized graph products. Computational Complexity\u00a05, 60\u201375 (1995)","journal-title":"Computational Complexity"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and intractability of approximation problems. In: Proc. 33rd IEEE Symp. on Foundations of Computer Science, pp. 13\u201322 (1992)","DOI":"10.1109\/SFCS.1992.267823"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: A new characterization of NP. In: Proc. 33rd IEEE Symp. on Foundations of Computer Science, pp. 2\u201313 (1992)","DOI":"10.1109\/SFCS.1992.267824"},{"key":"8_CR4","unstructured":"Berman, P., Furer, M.: Approximating maximum independent set in bounded degree graphs. In: SODA, pp. 365\u2013371 (1994)"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Berman, P., Fujito, T.: On the approximation properties of independent set problem in degree 3 graphs. In: WADS, pp. 449\u2013460 (1995)","DOI":"10.1007\/3-540-60220-8_84"},{"key":"8_CR6","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"R. Boppana","year":"1992","unstructured":"Boppana, R., Halldorsson, M.M.: Approximating maximum independent sets by excluding subgraphs. Bit\u00a032, 180\u2013196 (1992)","journal-title":"Bit"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M.: On some tighter inapproximability results. DIMACS Technical Report 99-23 (1999)","DOI":"10.1007\/3-540-48523-6_17"},{"key":"8_CR8","unstructured":"Berman, P., Karpinski, M.: Improved approximation lower bounds on small occurrence optimization. ECCC TR03-008 (2003)"},{"key":"8_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(84)90086-6","volume":"9","author":"R. Bar-Yehuda","year":"1984","unstructured":"Bar-Yehuda, R., Moran, S.: On approximation problems related to the independent set and vertex cover problems. Discrete Applied Mathematics\u00a09, 1\u201310 (1984)","journal-title":"Discrete Applied Mathematics"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Chlebik, M., Chlebikova, J.: Approximation hardness for small occurrence instances of NP-hard problems. ECCC TR02-073 (2002)","DOI":"10.1007\/3-540-44849-7_21"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Chlebik, M., Chlebikova, J.: Inapproximability results for bounded variants of optimization problems. ECCC TR03-026 (2003)","DOI":"10.1007\/978-3-540-45077-1_4"},{"key":"8_CR12","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees and flowers. Canadian Journal of Mathematics\u00a017, 449\u2013467 (1965)","journal-title":"Canadian Journal of Mathematics"},{"key":"8_CR13","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. Halldorsson","year":"1998","unstructured":"Halldorsson, M.M.: Approximations of independent sets in graphs. In: Jansen, K., Rolim, J.D.P. (eds.) APPROX 1998. LNCS, vol.\u00a01444, p. 1. Springer, Heidelberg (1998)"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, El Paso, Texas, May 4\u20136, pp. 1\u201310 (1997)","DOI":"10.1145\/258533.258536"},{"issue":"1","key":"8_CR15","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n 1\u2009\u2212\u2009\u03b5 . Acta Math.\u00a0182(1), 105\u2013142 (1999)","journal-title":"Acta Math."},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"C.A.J. Hurkens","year":"1989","unstructured":"Hurkens, C.A.J., Schrijver, A.: On the size of systems of sets every t of which have an sdr, with an application to the worst-case ratio of heuristics for packing problems. SIAM Journal Discrete Math.\u00a02, 68\u201372 (1989)","journal-title":"SIAM Journal Discrete Math."},{"key":"8_CR17","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"V. Kann","year":"1991","unstructured":"Kann, V.: Maximum bounded 3-dimensional matching is MAXSNP complete. Information Processing Letters\u00a037, 27\u201335 (1991)","journal-title":"Information Processing Letters"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. Complexity of Computer Computations, 83\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"8_CR19","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"8_CR20","doi-asserted-by":"crossref","unstructured":"Petrank, E.: The hardness of approximation - gap location. In: Israel Symposium on Theory of Computing Systems (1994)","DOI":"10.1007\/BF01202286"},{"key":"8_CR21","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1137\/S0895480197329508","volume":"13","author":"J. Radhakrishnan","year":"2000","unstructured":"Radhakrishnan, J., Ta-Shma, A.: Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM Journal on Discrete Mathematics\u00a013, 2\u201324 (2000)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: Proc. of the 33rd ACM STOC (2001)","DOI":"10.1145\/380752.380839"},{"key":"8_CR23","unstructured":"Vishwanathan, S.: Personal communication to m. halldorsson cited in [Hal 1998] (1996)"},{"issue":"4","key":"8_CR24","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1145\/2157.2158","volume":"30","author":"A. Wigderson","year":"1983","unstructured":"Wigderson, A.: Improving the performance guarantee for approximate graph coloring. Journal of the Association for Computing Machinery \u00a030(4), 729\u2013735 (1983)","journal-title":"Journal of the Association for Computing Machinery"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45198-3_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T14:05:15Z","timestamp":1559916315000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45198-3_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540407706","9783540451983"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45198-3_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003]]}}}