{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:25:41Z","timestamp":1725470741081},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540388753"},{"type":"electronic","value":"9783540388760"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841036_36","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T13:20:54Z","timestamp":1157980854000},"page":"387-398","source":"Crossref","is-referenced-by-count":1,"title":["Violator Spaces: Structure and Algorithms"],"prefix":"10.1007","author":[{"given":"Bernd","family":"G\u00e4rtner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ji\u0159\u00ed","family":"Matou\u0161ek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leo","family":"R\u00fcst","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr","family":"\u0160kovro\u0148","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"36_CR1","doi-asserted-by":"crossref","unstructured":"G\u00e4rtner, B., Matou\u0161ek, J., R\u00fcst, L., \u0160kovro\u0148, P.: Violator spaces: Structure and algorithms. arXiv.org e-Print archive (2006)","DOI":"10.1007\/11841036_36"},{"key":"36_CR2","series-title":"Lecture Notes in Computer Science","first-page":"569","volume-title":"STACS 92","author":"M. Sharir","year":"1992","unstructured":"Sharir, M., Welzl, E.: A combinatorial bound for linear programming and related problems. In: Finkel, A., Jantzen, M. (eds.) STACS 1992. LNCS, vol.\u00a0577, pp. 569\u2013579. Springer, Heidelberg (1992)"},{"key":"36_CR3","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1007\/BF01940877","volume":"16","author":"J. Matou\u0161ek","year":"1996","unstructured":"Matou\u0161ek, J., Sharir, M., Welzl, E.: A subexponential bound for linear programming. Algorithmica\u00a016, 498\u2013516 (1996)","journal-title":"Algorithmica"},{"key":"36_CR4","doi-asserted-by":"crossref","unstructured":"Kalai, G.: A subexponential randomized simplex algorithm. In: Proc. 24th Annual ACM Symposium on Theory of Computing (STOC), pp. 475\u2013482 (1992)","DOI":"10.1145\/129712.129759"},{"key":"36_CR5","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1145\/177424.178064","volume-title":"Proc. 10th Annual Symposium on Computational Geometry (SCG)","author":"N. Amenta","year":"1994","unstructured":"Amenta, N.: Bounded boxes, Hausdorff distance, and a new proof of an interesting Helly-type theorem. In: Proc. 10th Annual Symposium on Computational Geometry (SCG), pp. 340\u2013347. ACM Press, New York (1994)"},{"key":"36_CR6","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF02574379","volume":"12","author":"N. Amenta","year":"1994","unstructured":"Amenta, N.: Helly theorems and generalized linear programming. Discrete and Computational Geometry\u00a012, 241\u2013261 (1994)","journal-title":"Discrete and Computational Geometry"},{"key":"36_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1007\/3-540-36494-3_58","volume-title":"STACS 2003","author":"H. Bj\u00f6rklund","year":"2003","unstructured":"Bj\u00f6rklund, H., Sandberg, S., Vorobyov, S.: A discrete subexponential algorithm for parity games. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 663\u2013674. Springer, Heidelberg (2003)"},{"key":"36_CR8","unstructured":"Halman, N.: Discrete and Lexicographic Helly Theorems and Their Relations to LP-type problems. PhD thesis, Tel-Aviv University (2004)"},{"key":"36_CR9","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1145\/201019.201036","volume":"42","author":"K.L. Clarkson","year":"1995","unstructured":"Clarkson, K.L.: Las Vegas algorithms for linear and integer programming. Journal of the ACM\u00a042, 488\u2013499 (1995)","journal-title":"Journal of the ACM"},{"key":"36_CR10","series-title":"Lecture Notes in Computer Science","first-page":"669","volume-title":"STACS 96","author":"B. G\u00e4rtner","year":"1996","unstructured":"G\u00e4rtner, B., Welzl, E.: Linear programming - randomization and abstract frameworks. In: Puech, C., Reischuk, R. (eds.) STACS 1996. LNCS, vol.\u00a01046, pp. 669\u2013687. Springer, Heidelberg (1996)"},{"key":"36_CR11","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1006\/jagm.1996.0060","volume":"21","author":"B. Chazelle","year":"1996","unstructured":"Chazelle, B., Matou\u0161ek, J.: On linear-time deterministic algorithms for optimization problems in fixed dimension. Journal of Algorithms\u00a021, 579\u2013597 (1996)","journal-title":"Journal of Algorithms"},{"key":"36_CR12","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02570713","volume":"14","author":"J. Matou\u0161ek","year":"1995","unstructured":"Matou\u0161ek, J.: On geometric optimization with few violated constraints. Discrete and Computational Geometry\u00a014, 365\u2013384 (1995)","journal-title":"Discrete and Computational Geometry"},{"issue":"4","key":"36_CR13","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1007\/s00454-001-0006-2","volume":"25","author":"B. G\u00e4rtner","year":"2001","unstructured":"G\u00e4rtner, B., Welzl, E.: A simple sampling lemma - analysis and applications in geometric optimization. Discrete and Computational Geometry\u00a025(4), 569\u2013590 (2001)","journal-title":"Discrete and Computational Geometry"},{"key":"36_CR14","unstructured":"Chan, T.: An optimal randomized algorithm for maximum Tukey depth. In: Proc. 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 423\u2013429 (2004)"},{"key":"36_CR15","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/BF02711517","volume":"15","author":"N. Amenta","year":"1996","unstructured":"Amenta, N.: A short proof of an interesting Helly-type theorem. Discrete and Computational Geometry\u00a015, 423\u2013427 (1996)","journal-title":"Discrete and Computational Geometry"},{"key":"36_CR16","doi-asserted-by":"crossref","unstructured":"Szab\u00f3, T., Welzl, E.: Unique sink orientations of cubes. In: Proc. 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 547\u2013555 (2000)","DOI":"10.1109\/SFCS.2001.959931"},{"key":"36_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/11496915_16","volume-title":"Integer Programming and Combinatorial Optimization","author":"B. G\u00e4rtner","year":"2005","unstructured":"G\u00e4rtner, B., Morris Jr., W.D., R\u00fcst, L.: Unique sink orientations of grids. In: J\u00fcnger, M., Kaibel, V. (eds.) IPCO 2005. LNCS, vol.\u00a03509, pp. 210\u2013224. Springer, Heidelberg (2005)"},{"key":"36_CR18","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/s101070100268","volume":"92","author":"W.D. Morris Jr.","year":"2002","unstructured":"Morris Jr., W.D.: Randomized principal pivot algorithms for P-matrix linear complementarity problems. Mathematical Programming, Series A\u00a092, 285\u2013296 (2002)","journal-title":"Mathematical Programming, Series A"},{"key":"36_CR19","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J.: The number of unique sink orientations of the hypercube. Combinatorica (to appear, 2006)","DOI":"10.1007\/s00493-006-0007-0"},{"key":"36_CR20","unstructured":"Morris Jr., W.D.: Distinguishing cube orientations arising from linear programs (manuscript, 2002)"},{"key":"36_CR21","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1515\/advg.2004.4.4.459","volume":"4","author":"M. Develin","year":"2004","unstructured":"Develin, M.: LP-orientations of cubes and crosspolytopes. Advances in Geometry\u00a04, 459\u2013468 (2004)","journal-title":"Advances in Geometry"},{"key":"36_CR22","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J., Szab\u00f3, T.: Random Edge can be exponential on abstract cubes. In: Proc. 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 92\u2013100 (2004)","DOI":"10.1109\/FOCS.2004.56"},{"key":"36_CR23","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1007\/s00454-003-0813-8","volume":"31","author":"I. Schurr","year":"2004","unstructured":"Schurr, I., Szab\u00f3, T.: Finding the sink takes some time. Discrete and Computational Geometry\u00a031, 627\u2013642 (2004)","journal-title":"Discrete and Computational Geometry"},{"key":"36_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/11496915_17","volume-title":"Integer Programming and Combinatorial Optimization","author":"I. Schurr","year":"2005","unstructured":"Schurr, I., Szab\u00f3, T.: Jumping doesn\u2019t help in abstract cubes. In: J\u00fcnger, M., Kaibel, V. (eds.) IPCO 2005. LNCS, vol.\u00a03509, pp. 225\u2013235. Springer, Heidelberg (2005)"},{"key":"36_CR25","doi-asserted-by":"crossref","unstructured":"G\u00e4rtner, B., Schurr, I.: Linear programming and unique sink orientations. In: Proc. 17th Annual Symposium on Discrete Algorithms (SODA), pp. 749\u2013757 (2006)","DOI":"10.1145\/1109557.1109639"},{"key":"36_CR26","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, H., Vorobyov, S.: Combinatorial structure and randomized subexponential algorithms for infinite games. Theoretical Computer Science (in press, 2005)","DOI":"10.1016\/j.tcs.2005.07.041"},{"key":"36_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/978-3-540-28629-5_52","volume-title":"Mathematical Foundations of Computer Science 2004","author":"H. Bj\u00f6rklund","year":"2004","unstructured":"Bj\u00f6rklund, H., Sandberg, S., Vorobyov, S.: A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. In: Fiala, J., Koubek, V., Kratochv\u00edl, J. (eds.) MFCS 2004. LNCS, vol.\u00a03153, pp. 673\u2013685. Springer, Heidelberg (2004)"},{"key":"36_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/11537311_19","volume-title":"Fundamentals of Computation Theory","author":"B. G\u00e4rtner","year":"2005","unstructured":"G\u00e4rtner, B., R\u00fcst, L.: Simple stochastic games and P-matrix generalized linear complementarity problems. In: Li\u015bkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol.\u00a03623, pp. 209\u2013220. Springer, Heidelberg (2005)"},{"key":"36_CR29","unstructured":"Megiddo, N.: A note on the complexity of P-matrix LCP and computing an equilibrium. Technical report, IBM Almaden Research Center, San Jose (1988)"},{"key":"36_CR30","unstructured":"\u0160kovro\u0148, P.: Generalized linear programming. Master\u2019s thesis, Charles University, Prague, Faculty of Mathematics and Physics (2002)"},{"key":"36_CR31","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0021-9800(70)80010-2","volume":"8","author":"R.W. Cottle","year":"1970","unstructured":"Cottle, R.W., Dantzig, G.B.: A generalization of the linear complementarity problem. Journal on Combinatorial Theory\u00a08, 79\u201390 (1970)","journal-title":"Journal on Combinatorial Theory"},{"key":"36_CR32","volume-title":"The Linear Complementarity Problem","author":"R.W. Cottle","year":"1992","unstructured":"Cottle, R.W., Pang, J., Stone, R.E.: The Linear Complementarity Problem. Academic Press, London (1992)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:40:31Z","timestamp":1605642031000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/11841036_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}