On linear-time deterministic algorithms for optimization problems in fixed dimension

Bernard Chazelle; Jiri Matousek

On linear-time deterministic algorithms for optimization problems in fixed dimension

Research output: Contribution to conference › Paper › peer-review

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 one. The constant of proportionality is d^O(d), which is better than for previously known such algorithms. We show that the algorithm works in a fairly general abstract setting, which allows us to solve various other problems (such as finding the maximum volume ellipsoid inscribed into the intersection of n halfspaces) in linear time.

Original language	English (US)
Pages	281-290
Number of pages	10
State	Published - 1993
Event	Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA Duration: Jan 25 1993 → Jan 27 1993

Other

Other	Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
City	Austin, TX, USA
Period	1/25/93 → 1/27/93

All Science Journal Classification (ASJC) codes

Engineering(all)

Cite this

@conference{63d09a1add8f415d8cfde8335117b002,

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 one. The constant of proportionality is dO(d), which is better than for previously known such algorithms. We show that the algorithm works in a fairly general abstract setting, which allows us to solve various other problems (such as finding the maximum volume ellipsoid inscribed into the intersection of n halfspaces) in linear time.",

author = "Bernard Chazelle and Jiri Matousek",

note = "Funding Information: * Supported in part by NSF Grant CCR-90-02352 and the Geometry Center. ²Supported in part by Humboldt Research Fellowship.; Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 25-01-1993 Through 27-01-1993",

year = "1993",

language = "English (US)",

pages = "281--290",

}

TY - CONF

T1 - On linear-time deterministic algorithms for optimization problems in fixed dimension

AU - Chazelle, Bernard

AU - Matousek, Jiri

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

PY - 1993

Y1 - 1993

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 one. The constant of proportionality is dO(d), which is better than for previously known such algorithms. We show that the algorithm works in a fairly general abstract setting, which allows us to solve various other problems (such as finding the maximum volume ellipsoid inscribed into the intersection of n halfspaces) in linear time.

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 one. The constant of proportionality is dO(d), which is better than for previously known such algorithms. We show that the algorithm works in a fairly general abstract setting, which allows us to solve various other problems (such as finding the maximum volume ellipsoid inscribed into the intersection of n halfspaces) in linear time.

UR - http://www.scopus.com/inward/record.url?scp=0027202916&partnerID=8YFLogxK

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

M3 - Paper

AN - SCOPUS:0027202916

SP - 281

EP - 290

T2 - Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 25 January 1993 through 27 January 1993

ER -

On linear-time deterministic algorithms for optimization problems in fixed dimension

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this