Computing the volume is difficult
Author(s) -
Zoltán Füredi,
Imre Bárány
Publication year - 1986
Publication title -
citeseer x (the pennsylvania state university)
Language(s) - English
Resource type - Conference proceedings
DOI - 10.1145/12130.12176
Subject(s) - computer science , volume (thermodynamics) , physics , quantum mechanics
For every polynomial time algorithm which gives an upper bound\(\overline {vol}\)(K) and a lower boundvol(K) for the volume of a convex setK⊂Rd, the ratio\(\overline {vol}\)(K)/vol(K) is at least (cd/logd)d for some convex setK⊂Rd.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom