A random polynomial time algorithm for well-rounding convex bodies

U. Faigle; N. Gademann; W. Kern

doi:10.1016/0166-218X(93)E0123-G

A random polynomial time algorithm for well-rounding convex bodies

U. Faigle, N. Gademann, W. Kern

Discrete Mathematics and Mathematical Programming

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

1 Citation (Scopus)

124 Downloads (Pure)

Abstract

We present a random polynomial time algorithm for well-rounding convex bodies K in the following sense: Given K ⊆ ℜⁿand ε > 0, the algorithm, with probability at least 1 — ε , computes two simplices Δ* and Δ**, where Δ** is the blow up of Δ* from its center by a factor of n + 3, such that
Δ* ⊆ K and vol (K/Δ**) ≤ vol K.

The running time is polynomial in 1/ε and L, the size of the input K.

Original language	English
Pages (from-to)	117-144
Journal	Discrete applied mathematics
Volume	58
Issue number	2
DOIs	https://doi.org/10.1016/0166-218X(93)E0123-G
Publication status	Published - 1995

Access to Document

10.1016/0166-218X(93)E0123-GLicence: Other

Faigle95randomFinal published version, 1.5 MBLicence: Other

Cite this

@article{f15f667c85f54f0a8d6f40a50955dc9b,

title = "A random polynomial time algorithm for well-rounding convex bodies",

abstract = "We present a random polynomial time algorithm for well-rounding convex bodies K in the following sense: Given K ⊆ ℜn and ε > 0, the algorithm, with probability at least 1 — ε , computes two simplices Δ* and Δ**, where Δ** is the blow up of Δ* from its center by a factor of n + 3, such thatΔ* ⊆ K and vol (K/Δ**) ≤ vol K. The running time is polynomial in 1/ε and L, the size of the input K.",

author = "U. Faigle and N. Gademann and W. Kern",

year = "1995",

doi = "10.1016/0166-218X(93)E0123-G",

language = "English",

volume = "58",

pages = "117--144",

journal = "Discrete applied mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - A random polynomial time algorithm for well-rounding convex bodies

AU - Faigle, U.

AU - Gademann, N.

AU - Kern, W.

PY - 1995

Y1 - 1995

N2 - We present a random polynomial time algorithm for well-rounding convex bodies K in the following sense: Given K ⊆ ℜn and ε > 0, the algorithm, with probability at least 1 — ε , computes two simplices Δ* and Δ**, where Δ** is the blow up of Δ* from its center by a factor of n + 3, such thatΔ* ⊆ K and vol (K/Δ**) ≤ vol K. The running time is polynomial in 1/ε and L, the size of the input K.

AB - We present a random polynomial time algorithm for well-rounding convex bodies K in the following sense: Given K ⊆ ℜn and ε > 0, the algorithm, with probability at least 1 — ε , computes two simplices Δ* and Δ**, where Δ** is the blow up of Δ* from its center by a factor of n + 3, such thatΔ* ⊆ K and vol (K/Δ**) ≤ vol K. The running time is polynomial in 1/ε and L, the size of the input K.

U2 - 10.1016/0166-218X(93)E0123-G

DO - 10.1016/0166-218X(93)E0123-G

M3 - Article

VL - 58

SP - 117

EP - 144

JO - Discrete applied mathematics

JF - Discrete applied mathematics

SN - 0166-218X

IS - 2

ER -

A random polynomial time algorithm for well-rounding convex bodies

Abstract

Access to Document

Fingerprint

Cite this