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:








Author, Editor

Author(s):

Althaus, Ernst
Eisenbrand, Friedrich
Funke, Stefan
Mehlhorn, Kurt

dblp
dblp
dblp
dblp



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:




Note, Abstract, ©


(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},
ADDRESS = {New Orleans, USA},
ISBN = {0-89871-558-X},
}


Entry last modified by Anja Becker, 01/08/2008
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Stefan Funke
Created
01/20/2005 08:28:57 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Anja Becker
Christine Kiesel
Tamara Hausmann
Christine Kiesel
Christine Kiesel
Edit Dates
08.01.2008 08:28:08
29.09.2006 09:28:22
13.06.2006 12:44:00
23.05.2005 14:14:28
04/21/2005 11:24:33 AM