On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension

Bernard Chazelle; Jiří Matoušek

doi:10.1006/jagm.1996.0060

On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension

Bernard Chazelle, Jiří Matoušek

Research output: Contribution to journal › Article › peer-review

132 Scopus citations

Abstract

We show that with recently developed derandomization techniques, one can convert Clarkson's randomized algorithm for linear programming in fixed dimension into a linear-time deterministic algorithm. The constant of proportionality is d^O(d), which is better than those for previously known algorithms. We show that the algorithm works in a fairly general abstract setting, which allows us to solve various other problems, e.g., computing the minimum-volume ellipsoid enclosing a set of n points and finding the maximum volume ellipsoid in the intersection of n halfspaces.

Original language	English (US)
Pages (from-to)	579-597
Number of pages	19
Journal	Journal of Algorithms
Volume	21
Issue number	3
DOIs	https://doi.org/10.1006/jagm.1996.0060
State	Published - Nov 1996
Externally published	Yes

All Science Journal Classification (ASJC) codes

Control and Optimization
Computational Mathematics
Computational Theory and Mathematics

Access to Document

10.1006/jagm.1996.0060

Cite this

@article{3b11f03ca4744531ace5ad7063d97d1f,

title = "On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension",

abstract = "We show that with recently developed derandomization techniques, one can convert Clarkson's randomized algorithm for linear programming in fixed dimension into a linear-time deterministic algorithm. The constant of proportionality is dO(d), which is better than those for previously known algorithms. We show that the algorithm works in a fairly general abstract setting, which allows us to solve various other problems, e.g., computing the minimum-volume ellipsoid enclosing a set of n points and finding the maximum volume ellipsoid in the intersection of n halfspaces.",

author = "Bernard Chazelle and Ji{\v r}{\'i} Matou{\v s}ek",

note = "Funding Information: * Supported in part by NSF Grant CCR-90-02352 and the Geometry Center. ²Supported in part by Humboldt Research Fellowship.",

year = "1996",

month = nov,

doi = "10.1006/jagm.1996.0060",

language = "English (US)",

volume = "21",

pages = "579--597",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension

AU - Chazelle, Bernard

AU - Matoušek, Jiří

N1 - Funding Information: * Supported in part by NSF Grant CCR-90-02352 and the Geometry Center. ²Supported in part by Humboldt Research Fellowship.

PY - 1996/11

Y1 - 1996/11

N2 - We show that with recently developed derandomization techniques, one can convert Clarkson's randomized algorithm for linear programming in fixed dimension into a linear-time deterministic algorithm. The constant of proportionality is dO(d), which is better than those for previously known algorithms. We show that the algorithm works in a fairly general abstract setting, which allows us to solve various other problems, e.g., computing the minimum-volume ellipsoid enclosing a set of n points and finding the maximum volume ellipsoid in the intersection of n halfspaces.

AB - We show that with recently developed derandomization techniques, one can convert Clarkson's randomized algorithm for linear programming in fixed dimension into a linear-time deterministic algorithm. The constant of proportionality is dO(d), which is better than those for previously known algorithms. We show that the algorithm works in a fairly general abstract setting, which allows us to solve various other problems, e.g., computing the minimum-volume ellipsoid enclosing a set of n points and finding the maximum volume ellipsoid in the intersection of n halfspaces.

UR - https://www.scopus.com/pages/publications/13544265613

UR - https://www.scopus.com/inward/citedby.url?scp=13544265613&partnerID=8YFLogxK

U2 - 10.1006/jagm.1996.0060

DO - 10.1006/jagm.1996.0060

M3 - Article

AN - SCOPUS:13544265613

SN - 0196-6774

VL - 21

SP - 579

EP - 597

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 3

ER -

On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this