Login
Document type:
Konferenzbeitrag / Conference Paper
Title:
Approximation of Diameters: Randomization doesn't help
Conference title:
Annual Symposium of the Foundation of Computer Science (39., 1998, Palo Alto, CA)
Conference title:
39th Annual Symposium of the Foundation of Computer Science
Venue:
Palo Alto, CA
Year of conference:
1998
Date of conference beginning:
08.11.1998
Date of conference ending:
11.11.1998
Place of publication:
Piscataway, NJ
Publisher:
IEEE Press
Year:
1998
Pages from - to:
244-251
Language:
Englisch
Subject:
Polynomials, Concurrent computing, Computer science, Mathematics, Approximation algorithms, Tellurium, Cyclic redundancy check
Abstract:
We describe a deterministic polynomial-time algorithm which, for a convex body K in Euclidean n-space, finds upper and lower bounds on K's diameter which differ by a factor of O(/spl radic/n/logn). We show that this is, within a constant factor, the best approximation to the diameter that a polynomial-time algorithm can produce even if randomization is allowed. We also show that the above results hold for other quantities similar to the diameter-namely; inradius, circumradius, width, and maximi... »
ISBN:
0-8186-9172-7
Department:
Fakultät für Wirtschafts- und Organisationswissenschaften
Institute:
WOW 1 - Institut für Controlling, Finanz- und Risikomanagement
Chair:
Brieden, Andreas
Open Access yes or no?:
Nein / No
BibTeX