Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Editor(s):
 BibTeX cite key*: AEFM2004

 Title, Booktitle
 Title*: Point Containment in the Integer Hull of a Polyhedron Booktitle*: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04)

 Event, URLs
 URL of the conference: http://www.siam.org/meetings/da04/ URL for downloading the paper: http://doi.acm.org/10.1145/982792.982932 http://www.mpi-sb.mpg.de/%7Efunke/Papers/triangle04.ps.gz Event Address*: New Orleans, USA Language: English Event Date* (no longer used): Organization: Association of Computing Machinery (ACM) Event Start Date: 11 January 2004 Event End Date: 13 January 2004

 Publisher
 Name*: ACM URL: http://www.acm.org Address*: New York, USA Type:

 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: Pages: 929-933 Year*: 2004 VG Wort Pages: ISBN/ISSN: 0-89871-558-X Sequence Number: DOI:

 (LaTeX) Abstract: We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time $\bigO(m+\varphi)$ in the two-dimensional case and in expected time $\bigO(m+\varphi^2 \log m)$ in any fixed dimension. This improves on the algorithm which is based on the equivalence of separation and optimization and on a direct algorithm (SODA 97) for the two-dimensional case. HyperLinks / References / URLs: http://dblp.uni-trier.de/db/conf/soda/soda2004.html#AlthausEFM04 Download Access Level: Intranet

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{AEFM2004,
AUTHOR = {Althaus, Ernst and Eisenbrand, Friedrich and Funke, Stefan and Mehlhorn, Kurt},
TITLE = {Point Containment in the Integer Hull of a Polyhedron},
BOOKTITLE = {Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04)},
PUBLISHER = {ACM},
YEAR = {2004},
ORGANIZATION = {Association of Computing Machinery (ACM)},
PAGES = {929--933},