{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:47:05Z","timestamp":1740109625281,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,3,14]],"date-time":"2018-03-14T00:00:00Z","timestamp":1520985600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["MU 3501\/1","MU 3501\/2"],"award-info":[{"award-number":["MU 3501\/1","MU 3501\/2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["research training group \u2019Methods for Discrete Structures\u2019 (GRK 1408)"],"award-info":[{"award-number":["research training group \u2019Methods for Discrete Structures\u2019 (GRK 1408)"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"publisher","award":["1161"],"award-info":[{"award-number":["1161"]}],"id":[{"id":"10.13039\/501100001736","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["757609"],"award-info":[{"award-number":["757609"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1007\/s00454-018-9979-y","type":"journal-article","created":{"date-parts":[[2018,3,14]],"date-time":"2018-03-14T14:06:13Z","timestamp":1521036373000},"page":"720-755","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Computational Aspects of the Colorful Carath\u00e9odory Theorem"],"prefix":"10.1007","volume":"60","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1948-5840","authenticated-orcid":false,"given":"Wolfgang","family":"Mulzer","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2062-7594","authenticated-orcid":false,"given":"Yannik","family":"Stein","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,14]]},"reference":[{"volume-title":"Local Search in Combinatorial Optimization","year":"2003","key":"9979_CR1","unstructured":"Aarts, E., Lenstra, J.K. (eds.): Local Search in Combinatorial Optimization. Princeton University Press, Princeton (2003)"},{"issue":"2","key":"9979_CR2","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/s00454-009-9180-4","volume":"42","author":"JL Arocha","year":"2009","unstructured":"Arocha, J.L., B\u00e1r\u00e1ny, I., Bracho, J., Fabila, R., Montejano, L.: Very colorful theorems. Discrete Comput. Geom. 42(2), 142\u2013154 (2009)","journal-title":"Discrete Comput. Geom."},{"issue":"2\u20133","key":"9979_CR3","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0012-365X(82)90115-7","volume":"40","author":"I B\u00e1r\u00e1ny","year":"1982","unstructured":"B\u00e1r\u00e1ny, I.: A generalization of Carath\u00e9odory\u2019s theorem. Discrete Math. 40(2\u20133), 141\u2013152 (1982)","journal-title":"Discrete Math."},{"issue":"3","key":"9979_CR4","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1287\/moor.22.3.550","volume":"22","author":"I B\u00e1r\u00e1ny","year":"1997","unstructured":"B\u00e1r\u00e1ny, I., Onn, S.: Colourful linear programming and its relatives. Math. Oper. Res. 22(3), 550\u2013567 (1997)","journal-title":"Math. Oper. Res."},{"key":"9979_CR5","doi-asserted-by":"crossref","unstructured":"Barman, S.: Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carath\u00e9odory\u2019s theorem. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC\u201915), pp. 361\u2013369. ACM, New York (2015)","DOI":"10.1145\/2746539.2746566"},{"issue":"4","key":"9979_CR6","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum, M., Pratt, V., Tarjan, R.E., Floyd, R.W., Rivest, R.L.: Time bounds for selection. J. Comput. Syst. Sci. 7(4), 448\u2013461 (1973)","journal-title":"J. Comput. Syst. Sci."},{"key":"9979_CR7","unstructured":"Chan, T.M.: An optimal randomized algorithm for maximum Tukey depth. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904), pp. 430\u2013436. ACM, New York (2004)"},{"key":"9979_CR8","doi-asserted-by":"crossref","unstructured":"Fabrikant, A., Papadimitriou, C., Talwar, K.: The complexity of pure Nash equilibria. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC\u201904), pp. 604\u2013612. ACM, New York (2004)","DOI":"10.1145\/1007352.1007445"},{"issue":"3","key":"9979_CR9","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF02574382","volume":"12","author":"S Jadhav","year":"1994","unstructured":"Jadhav, S., Mukhopadhyay, A.: Computing a centerpoint of a finite planar set of points in linear time. Discrete Comput. Geom. 12(3), 291\u2013312 (1994)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9979_CR10","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"DS Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comput. System Sci. 37(1), 79\u2013100 (1988)","journal-title":"J. Comput. System Sci."},{"key":"9979_CR11","doi-asserted-by":"crossref","unstructured":"Kapoor, S., Vaidya, P.M.: Fast algorithms for convex quadratic programming and multicommodity flows. In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC\u201986), pp. 147\u2013159. ACM, New York (1986)","DOI":"10.1145\/12130.12145"},{"issue":"4","key":"9979_CR12","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/BF01445182","volume":"57","author":"P Kirchberger","year":"1903","unstructured":"Kirchberger, P.: \u00dcber Tchebychefsche Ann\u00e4herungsmethoden. Math. Ann. 57(4), 509\u2013540 (1903)","journal-title":"Math. Ann."},{"issue":"5","key":"9979_CR13","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0041-5553(80)90098-1","volume":"20","author":"MK Kozlov","year":"1980","unstructured":"Kozlov, M.K., Tarasov, S.P., Khachiyan, L.G.: The polynomial solvability of convex quadratic programming. USSR Comput. Math. Math. Phys. 20(5), 223\u2013228 (1980)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"9979_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry. Graduate Texts in Mathematics","author":"J Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, New York (2002)"},{"issue":"2","key":"9979_CR15","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(91)90200-L","volume":"81","author":"N Megiddo","year":"1991","unstructured":"Megiddo, N., Papadimitriou, C.H.: On total functions, existence theorems and computational complexity. Theor. Comput. Sci. 81(2), 317\u2013324 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"9979_CR16","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/978-3-319-00200-2_11","volume-title":"Discrete Geometry and Optimization. Fields Institute Communications","author":"F Meunier","year":"2013","unstructured":"Meunier, F., Deza, A.: A further generalization of the colourful Carath\u00e9odory theorem. In: Bezdek, K., Deza, A., Ye, Y. (eds.) Discrete Geometry and Optimization. Fields Institute Communications, vol. 69, pp. 179\u2013190. Springer, Berlin (2013)"},{"key":"9979_CR17","doi-asserted-by":"crossref","unstructured":"Meunier, F., Mulzer, W., Sarrabezolles, P., Stein, Y.: The rainbow at the end of the line\u2014a PPAD formulation of the colorful Carath\u00e9odory theorem with applications. In: Proceedings of the 28th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201917), pp. 1342\u20131351. SIAM, Philadelphia (2017)","DOI":"10.1137\/1.9781611974782.87"},{"key":"9979_CR18","unstructured":"Meunier, F., Sarrabezolles, P.: Colorful linear programming, Nash equilibrium, and pivots (2014). \n                    arXiv:1409.3436"},{"key":"9979_CR19","series-title":"Monographs in Theoretical Computer Science","volume-title":"Theoretical Aspects of Local Search","author":"W Michiels","year":"2007","unstructured":"Michiels, W., Aarts, E., Korst, J.: Theoretical Aspects of Local Search. Monographs in Theoretical Computer Science. Springer, Berlin (2007)"},{"issue":"8","key":"9979_CR20","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1016\/j.comgeo.2010.04.006","volume":"43","author":"GL Miller","year":"2010","unstructured":"Miller, G.L., Sheehy, D.R.: Approximate centerpoints with proofs. Comput. Geom. 43(8), 647\u2013654 (2010)","journal-title":"Comput. Geom."},{"issue":"2","key":"9979_CR21","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1007\/s00454-013-9528-7","volume":"50","author":"W Mulzer","year":"2013","unstructured":"Mulzer, W., Werner, D.: Approximating Tverberg points in linear time for any fixed dimension. Discrete Comput. Geom. 50(2), 520\u2013535 (2013)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"9979_CR22","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1137\/0221030","volume":"21","author":"CH Papadimitriou","year":"1992","unstructured":"Papadimitriou, C.H.: The complexity of the Lin-Kernighan heuristic for the traveling salesman problem. SIAM J. Comput. 21(3), 450\u2013465 (1992)","journal-title":"SIAM J. Comput."},{"key":"9979_CR23","series-title":"Texts and Monographs in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"FP Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry. Texts and Monographs in Computer Science. Springer, New York (1985)"},{"key":"9979_CR24","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1112\/jlms\/s1-21.4.291","volume":"21","author":"R Rado","year":"1946","unstructured":"Rado, R.: A theorem on general measure. J. Lond. Math. Soc. 21, 291\u2013300 (1946)","journal-title":"J. Lond. Math. Soc."},{"issue":"5","key":"9979_CR25","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1006\/eujc.2000.0493","volume":"22","author":"JP Roudneff","year":"2001","unstructured":"Roudneff, J.P.: Partitions of points into simplices with \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -dimensional intersection. I. The conic Tverberg\u2019s theorem. Eur. J. Comb. 22(5), 733\u2013743 (2001)","journal-title":"Eur. J. Comb."},{"issue":"2\u20133","key":"9979_CR26","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/BF02808223","volume":"79","author":"KS Sarkaria","year":"1992","unstructured":"Sarkaria, K.S.: Tverberg\u2019s theorem via number fields. Israel J. Math. 79(2\u20133), 317\u2013320 (1992)","journal-title":"Israel J. Math."},{"issue":"1","key":"9979_CR27","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1137\/0220004","volume":"20","author":"AA Sch\u00e4ffer","year":"1991","unstructured":"Sch\u00e4ffer, A.A., Yannakakis, M.: Simple local search problems that are hard to solve. SIAM J. Comput. 20(1), 56\u201387 (1991)","journal-title":"SIAM J. Comput."},{"key":"9979_CR28","unstructured":"Teng, S.-H.: Points, Spheres, and Separators: A Unified Geometric Approach to Graph Partitioning. Ph.D. thesis, Carnegie Mellon University (1991)"},{"issue":"1","key":"9979_CR29","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1112\/jlms\/s1-41.1.123","volume":"41","author":"H Tverberg","year":"1966","unstructured":"Tverberg, H.: A generalization of Radon\u2019s theorem. J. Lond. Math. Soc. 41(1), 123\u2013128 (1966)","journal-title":"J. Lond. Math. Soc."},{"issue":"3","key":"9979_CR30","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1017\/S0004972700004858","volume":"24","author":"H Tverberg","year":"1981","unstructured":"Tverberg, H.: A generalization of Radon\u2019s theorem II. Bull. Aust. Math. Soc. 24(3), 321\u2013325 (1981)","journal-title":"Bull. Aust. Math. Soc."},{"issue":"3","key":"9979_CR31","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1006\/eujc.1993.1029","volume":"14","author":"H Tverberg","year":"1993","unstructured":"Tverberg, H., Vre\u0107ica, S.: On generalizations of Radon\u2019s theorem and the ham sandwich theorem. Eur. J. Comb. 14(3), 259\u2013264 (1993)","journal-title":"Eur. J. Comb."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-018-9979-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-018-9979-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-018-9979-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,13]],"date-time":"2019-03-13T20:16:25Z","timestamp":1552508185000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-018-9979-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,14]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["9979"],"URL":"https:\/\/doi.org\/10.1007\/s00454-018-9979-y","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2018,3,14]]},"assertion":[{"value":"22 January 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 February 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 March 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}