English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Point Containment in the Integer Hull of a Polyhedron

Althaus, E., Eisenbrand, F., Funke, S., & Mehlhorn, K. (2004). Point Containment in the Integer Hull of a Polyhedron. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04) (pp. 929-933). New York, NY: ACM.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2BA9-D Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0026-A188-7
Genre: Conference Paper

Files

show Files
hide Files
:
triangle.ps.gz (Publisher version), 78KB
 
File Permalink:
-
Name:
triangle.ps.gz
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/gzip
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Althaus, Ernst1, Author           
Eisenbrand, Friedrich2, Author           
Funke, Stefan1, Author           
Mehlhorn, Kurt1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2Discrete Optimization, MPI for Informatics, Max Planck Society, ou_1116548              

Content

show
hide
Free keywords: -
 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 $O(m+\varphi)$ in the two-dimensional case and in expected time $O(m+\varphi^2 \log m)$ in any fixed dimension. This improves on the algorithm which is based on the equivalence of separation and optimization in the general case and on a direct algorithm (SODA 97) for the two-dimensional case.

Details

show
hide
Language(s): eng - English
 Dates: 2005-05-312004
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 241594
Other: Local-ID: C1256BDD00205AD6-5A66A234AFD82E2DC1256E0C0040AD33-AEFM2004-NWG
 Degree: -

Event

show
hide
Title: Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Place of Event: New Orleans, USA
Start-/End Date: 2004-01-11

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04)
  Abbreviation : SODA 2004
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: New York, NY : ACM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 929 - 933 Identifier: ISBN: 0-89871-558-X