{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T16:54:26Z","timestamp":1784220866630,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642139611","type":"print"},{"value":"9783642139628","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13962-8_20","type":"book-chapter","created":{"date-parts":[[2010,6,26]],"date-time":"2010-06-26T12:33:57Z","timestamp":1277555637000},"page":"180-189","source":"Crossref","is-referenced-by-count":13,"title":["Approximability and Hardness in Multi-objective Optimization"],"prefix":"10.1007","author":[{"given":"Christian","family":"Gla\u00dfer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Reitwie\u00dfner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Heinz","family":"Schmitz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maximilian","family":"Witek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0304-0208(08)73101-3","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda, R., Even, S.: A local ratio theorem for approximating the weighted vertex cover problem. Analysis and Design of Algorithms for Combinatorial Problems. Annals of Discrete Mathematics\u00a025, 27\u201346 (1985)","journal-title":"Analysis and Design of Algorithms for Combinatorial Problems. Annals of Discrete Mathematics"},{"key":"20_CR2","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Tech. Rep. 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA (1976)"},{"key":"20_CR3","volume-title":"Multicriteria Optimization","author":"M. Ehrgott","year":"2005","unstructured":"Ehrgott, M.: Multicriteria Optimization. Springer, Heidelberg (2005)"},{"issue":"4","key":"20_CR4","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s002910000046","volume":"22","author":"M. Ehrgott","year":"2000","unstructured":"Ehrgott, M., Gandibleux, X.: A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spectrum\u00a022(4), 425\u2013460 (2000)","journal-title":"OR Spectrum"},{"key":"20_CR5","series-title":"Kluwer\u2019s International Series in Operations Research and Management Science","volume-title":"Multiple Criteria Optimization: State of the Art Annotated Bibliographic Survey","year":"2002","unstructured":"Ehrgott, M., Gandibleux, X. (eds.): Multiple Criteria Optimization: State of the Art Annotated Bibliographic Survey. Kluwer\u2019s International Series in Operations Research and Management Science, vol.\u00a052. Kluwer Academic Publishers, Dordrecht (2002)"},{"key":"20_CR6","first-page":"302","volume-title":"37th Annual Symposium on Foundations of Computer Science","author":"N. Garg","year":"1996","unstructured":"Garg, N.: A 3-approximation for the minimum tree spanning k vertices. In: 37th Annual Symposium on Foundations of Computer Science, pp. 302\u2013309. IEEE Computer Society Press, Los Alamitos (1996)"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Gla\u00dfer, C., Reitwie\u00dfner, C., Schmitz, H., Witek, M.: Hardness and approximability in multi-objective optimization. Tech. Rep. TR10-031, Electronic Colloquium on Computational Complexity (2010)","DOI":"10.1007\/978-3-642-13962-8_20"},{"key":"20_CR8","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1142\/9789814354363_0013","volume-title":"Complexity in Numerical Optimization","author":"C.Y. Lee","year":"1993","unstructured":"Lee, C.Y., Vairaktarakis, G.L.: Complexity of single machine hierarchical scheduling: A survey. In: Pardalos, P.M. (ed.) Complexity in Numerical Optimization, pp. 269\u2013298. World Scientific, Singapore (1993)"},{"issue":"1","key":"20_CR9","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF00290149","volume":"22","author":"B. Monien","year":"1985","unstructured":"Monien, B., Speckenmeyer, E.: Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Informatica\u00a022(1), 115\u2013123 (1985)","journal-title":"Acta Informatica"},{"key":"20_CR10","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1109\/SFCS.2000.892068","volume-title":"FOCS 2000: Proceedings of the 41st Annual Symposium on Foundations of Computer Science","author":"C.H. Papadimitriou","year":"2000","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: FOCS 2000: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 86\u201395. IEEE Computer Society, Washington (2000)"},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1109\/SFCS.1991.185443","volume-title":"32nd Annual Symposium on Foundations of Computer Science","author":"H. Saran","year":"1991","unstructured":"Saran, H., Vazirani, V.V.: Finding k-cuts within twice the optimal. In: 32nd Annual Symposium on Foundations of Computer Science, pp. 743\u2013751. IEEE Computer Society Press, Los Alamitos (1991)"},{"key":"20_CR12","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/S0022-0000(05)80009-1","volume":"48","author":"A.L. Selman","year":"1994","unstructured":"Selman, A.L.: A taxonomy on complexity classes of functions. Journal of Computer and System Sciences\u00a048, 357\u2013381 (1994)","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Programs, Proofs, Processes"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13962-8_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:45:58Z","timestamp":1606185958000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13962-8_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642139611","9783642139628"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13962-8_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}