English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Fast Integer Programming in Fixed Dimension

Eisenbrand, F. (2003). Fast Integer Programming in Fixed Dimension. In Algorithms - ESA 2003 (pp. 196-207). Berlin: Springer.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2CFF-3 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0026-A3D6-5
Genre: Conference Paper

Files

show Files
hide Files
:
ip_llncs.ps (Publisher version), 219KB
 
File Permalink:
-
Name:
ip_llncs.ps
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/postscript
Technical Metadata:
Copyright Date:
-
Copyright Info:
Copyright Springer Verlag
License:
-

Locators

show

Creators

show
hide
 Creators:
Eisenbrand, Friedrich1, Author           
Di Battista, Guiseppe2, Editor
Zwick, Uri2, Editor
Affiliations:
1Discrete Optimization, MPI for Informatics, Max Planck Society, ou_1116548              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 Abstract: It is shown that the optimum of an integer program in fixed dimension, which is defined by a fixed number of constraints, can be computed with $O(s)$ basic arithmetic operations, where $s$ is the binary encoding length of the input. This improves on the quadratic running time of previous algorithms which are based on Lenstra's algorithm and binary search. It follows that an integer program in fixed dimension, which is defined by $m$ constraints, each of binary encoding length at most $s$, can be solved with an expected number of $O(m + \log(m) \, s)$ arithmetic operations using Clarkson's random sampling algorithm.

Details

show
hide
Language(s): eng - English
 Dates: 2004-07-012003
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 201995
Other: Local-ID: C1256BDD00205AD6-95592AD78634B81EC1256E0C003C9CAA-Eisen2003
DOI: 10.1007/978-3-540-39658-1_20
 Degree: -

Event

show
hide
Title: 11th Annual European Symposium on Algorithms
Place of Event: Budapest, Hungary
Start-/End Date: 2003-09-16 - 2003-09-19

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms - ESA 2003
  Subtitle : 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings
  Abbreviation : ESA 2003
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 196 - 207 Identifier: ISBN: 3-540-20064-9

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 2832 Sequence Number: - Start / End Page: - Identifier: -