%% ToC#295.bib ToC 3/8 Matousek - Skovron 2007-09-26

@inproceedings{lptouso,
author = "B. G{\"a}rtner and I. Schurr",
title = "Linear Programming and Unique Sink Orientations",
booktitle = "Proc. 17th Ann. Symp. on Discrete Algorithms (SODA'06)",
year = "2006",
pages = "749--757",
publisher="ACM Press",
eprint="soda:1109557.1109639"}

@inproceedings{SS, 
author = "I. Schurr and T. Szab\'o", 
title = "Jumping doesn't help in abstract cubes", 
booktitle = "Proc. 11th Conf. on Integer Programming and Combinatorial Optimization (IPCO'05)", 
series = "Lecture Notes in Computer Science", 
publisher = "Springer-Verlag", 
volume="3509", 
year = "2005", 
pages ="225--235",
eprint="springer:jv4nn8d0qukbbnke"}

@inproceedings{MS, 
author = "J. Matou\v{s}ek and T. Szab\'o", 
title = "{R}andom {E}dge can be exponential on abstract cubes", 
booktitle = "Proc. 45th FOCS", 
year = "2004", 
publisher = "IEEE Comp. Soc. Press",
pages = "92--100",
eprint="focs:10.1109/FOCS.2004.56"}

@inproceedings{SW, 
author = "T. Szab\'o and E. Welzl", 
title = "Unique sink orientations of cubes", 
booktitle = "Proc. 42nd FOCS", 
publisher = "IEEE Comp. Soc. Press",
pages = "547--555", 
year = "2001",
eprint="focs:10.1109/SFCS.2001.959931"}

@inproceedings{grid_uso, 
author = "B. G{\"a}rtner and W.~D. Morris{, Jr.} and L. R{\"u}st", 
title =	"Unique Sink Orientations of Grids", 
booktitle = "Proc. 11th Conf. on Integer Programming and Combinatorial Optimization (IPCO'05)", 
series = "Lecture Notes in Computer Science",
publisher = "Springer-Verlag", 
volume = "3509",
pages = "210--224",
year = "2005",
eprint="springer:xv16bkejxpgqlcyv"}

@inproceedings{sw-cblpr-92,
author = "M. Sharir and E. Welzl",
title = "A combinatorial bound for linear programming and related problems",
booktitle = "Proc. 9th Symp. on Theoretical Aspects of Computer Science (STACS'92)",
series = "Lecture Notes in Computer Science",
publisher = "Springer-Verlag", 
volume = "577",
pages = "569--579",
year = "1992"}

@inproceedings{k-srsa-92, 
author = "G. Kalai", 
title =	"A subexponential randomized simplex algorithm", 
booktitle = "Proc. 24th STOC", 
publisher = "ACM Press",
year =	"1992", 
pages =	"475--482",
eprint="stoc:129712.129759"}

@inproceedings{a-bbhdn-94,
author = "N. Amenta",
title = "Bounded boxes, {H}ausdorff distance, and a new proof of an interesting {H}elly-type theorem",
booktitle = "Proc. 10th Ann. Symp. on Computational Geometry (SCG'94)",
year = "1994",
pages = "340--347",
publisher = "ACM Press",
eprint="acm:177424.178064"}

@inproceedings{ChanTukey,
author = "T. Chan",
title = "An optimal randomized algorithm for maximum {T}ukey depth",
booktitle = "Proc. 15th ACM-SIAM Symp. on Discrete Algorithms (SODA'04)",
year = "2004",
publisher = "SIAM",
pages = "430--436",
eprint="soda:982792.982853"}

@inproceedings{gw-lpraf-96,
author = "B. G{\"a}rtner and E. Welzl",
title = "Linear Programming - Randomization and Abstract Frameworks",
booktitle = "Proc. 13th Ann. Symp. on Theoretical Aspects of Computer Science (STACS'96)",
year = "1996",
pages = "669--687",
publisher = "Springer-Verlag",
address = "London, UK"}

@article{a-httgl-94,
author = "N. Amenta ",
title =	"{H}elly Theorems and Generalized Linear Programming",
journal	= "Discrete and Computational Geometry",
year = "1994",
pages =	"241--261",
volume = "12",
eprint="springer:bx1262r145x60505"}

@article{a-spiht-96,
author = "N. Amenta",
title = "A Short Proof of an Interesting {H}elly-Type Theorem",
journal = "Discrete and Computational Geometry",
volume = "15",
pages = "423--427",
year = "1996",
eprint="springer:1fdgptcx3qfd4vm4"}

@article{c-lvali-95, 
author = "K.~L. Clarkson", 
title =	"{L}as {V}egas algorithms for linear and integer programming", 
journal = "Journal of the ACM", 
volume = "42", 
year = "1995", 
pages =	"488--499",
eprint="jacm:201019.201036"}

@article{cm-ltdao-96, 
author = "B. Chazelle and J. Matou\v{s}ek", 
title =	"On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension", 
journal = "Journal of Algorithms", 
volume = "21", 
year = "1996", 
pages =	"579--597",
eprint="elsevier:10.1006/jagm.1996.0060"}

@article{m-gofvc-95,
author = "J. Matou\v{s}ek",
title = "On Geometric Optimization with Few Violated Constraints",
journal = "Discrete and Computational Geometry",
volume = "14",
pages = "365--384",
year = "1995",
eprint="springer:r750741557886767"}

@article{msw-sblp-92, 
author = "J. Matou\v{s}ek and M. Sharir and E. Welzl", 
title =	"A subexponential bound for linear programming", 
journal = "Algorithmica", 
volume = "16", 
year = "1996", 
pages =	"498--516", 
eprint="algorithmica:r378224736133416"}

@article{GWSampl01, 
author = "B. G{\"a}rtner and E. Welzl", 
title = "A simple sampling lemma: {A}nalysis and applications in geometric optimization", 
journal = "Discrete and Computational Geometry", 
volume = "25", 
number = "4", 
pages = "569--590", 
year = "2001",
eprint="springer:9flx12lr0mghtcc4"}

@inproceedings{halmanfocs,
author = "N. Halman", 
title = "On the Power of Discrete and of Lexicographic {H}elly-type Theorems", 
year = "2004",
booktitle="Proc. 46th FOCS",
publisher = "IEEE Comp. Soc. Press",
pages="463--472",
eprint="focs:10.1109/FOCS.2004.47"}

@article{gmrs06,
author = "B. G{\"a}rtner and J. Matou\v{s}ek and L. R{\"u}st and P. {\v{S}}kovro\v{n}",
title = "Violator Spaces: Structure and Algorithms",
journal="Discr. Appl. Math.",
year = "2007",
note ="In press. Also in arXiv cs.DM/0606087.  Extended abstract in \emph{Proc. 14th Europ. Symp. Algorithms (ESA'06)}",
eprint="arxiv:cs.DM/0606087"}

@inproceedings{wds06,
author = "P. {\v S}kovro{\v n}",
title = "Removing degeneracies in {LP}-type problems may need to increase dimension",
booktitle = "Proc.\ 15th Week of Doctoral Students (WDS)",
publisher = "Matfyzpress, Prague",
editor = "Jana {\v S}afr{\'a}nkov{\'a} and Ji{\v r}{\'\i} Pavl{\accent23 u}",
year = "2006",
pages = "I:196--207",
pdf="http://www.mff.cuni.cz/veda/konference/wds/contents/pdf06/WDS06_135_i4_Skovron.pdf"}

@phdthesis{SchurrThesis,
author="I. Schurr",
title="Unique sink orientations of cubes",
school="ETH Z{\"u}rich, Nr. 15747",
year=2004,
note="Nr. 15747.  Available at \url{http://e-collection.ethbib.ethz.ch}"}

@phdthesis{FischerThesis,
author="K. Fischer",
title="Smallest enclosing balls of balls",
school="ETH Z{\"u}rich,  Nr. 16168",
year=2005,
note="Available at \url{http://e-collection.ethbib.ethz.ch}"}

@inproceedings{bsv-dsapg-01,
author="H. Bj{\"o}rklund and S. Sandberg and S. Vorobyov",
title="A discrete subexponential algorithm for parity games",
booktitle="Proc. 20th Ann. Symp. on Theoretical Aspects of Computer Science (STACS'03),  Lect. Notes Comput. Sci. 2607",
publisher="Springer-Verlag",
pages="663--674",
year="2003",
eprint="springer:wpjqa08u8db47c3g"}

@inproceedings{bms-dgc-94,
author = "C. Burnikel and K. Mehlhorn and S. Schirra",
title = "On degeneracy in geometric computations",
booktitle = "Proc. 5th ACM-SIAM Symp. on Discrete Algorithms (SODA'94)",
year ="1994",
pages = "16--23",
publisher="SIAM",
eprint="soda:314464.314474"}

@article{em-sstcd-90,
author = "H. Edelsbrunner and E. P. M{\"u}cke",
title =  "Simulation of simplicity: {A} technique to cope with degenerate cases in geometric algorithms",
journal = "ACM Transactions on Graphics",
volume = "9",
number = "1",
year = "1990",
pages = "66--104",
eprint="acm:77635.77639"}

@article{y-gctsp-90,
author = "C. K. Yap",
title = "A geometric consistency theorem for a symbolic perturbation scheme",
journal = "Journal of Computer and System Sciences",
volume = "40",
number = "1",
year = "1990",
pages = "2--18",
eprint="jcss:10.1016/0022-0000(90)90016-E"}

@article{ec-gard-95,
author = "I. Emiris and J. Canny",
title = "A general approach to removing degeneracies",
journal = "SIAM J. Computing",
volume = "24",
year = "1995",
pages = "650--664",
eprint="sicomp:10.1137/S0097539792235918"}