A hardness of approximation result in metric geometry
Abstract We show that it is $${\mathsf {NP}}$$ NP -hard to approximate the hyperspherical radius of a triangulated manifold up to an almost-polynomial factor.
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer International Publishing
2021
|
| Online Access: | https://hdl.handle.net/1721.1/131412 |
| _version_ | 1811085631951994880 |
|---|---|
| author | Brady, Zarathustra Guth, Larry Manin, Fedor |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Brady, Zarathustra Guth, Larry Manin, Fedor |
| author_sort | Brady, Zarathustra |
| collection | MIT |
| description | Abstract
We show that it is
$${\mathsf {NP}}$$
NP
-hard to approximate the hyperspherical radius of a triangulated manifold up to an almost-polynomial factor. |
| first_indexed | 2024-09-23T13:12:43Z |
| format | Article |
| id | mit-1721.1/131412 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:12:43Z |
| publishDate | 2021 |
| publisher | Springer International Publishing |
| record_format | dspace |
| spelling | mit-1721.1/1314122023-03-15T20:32:40Z A hardness of approximation result in metric geometry Brady, Zarathustra Guth, Larry Manin, Fedor Massachusetts Institute of Technology. Department of Mathematics Abstract We show that it is $${\mathsf {NP}}$$ NP -hard to approximate the hyperspherical radius of a triangulated manifold up to an almost-polynomial factor. 2021-09-20T17:16:57Z 2021-09-20T17:16:57Z 2020-07-20 2020-09-24T21:11:50Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/131412 Selecta Mathematica. 2020 Jul 20;26(4):54 en https://doi.org/10.1007/s00029-020-00585-3 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer Nature Switzerland AG application/pdf Springer International Publishing Springer International Publishing |
| spellingShingle | Brady, Zarathustra Guth, Larry Manin, Fedor A hardness of approximation result in metric geometry |
| title | A hardness of approximation result in metric geometry |
| title_full | A hardness of approximation result in metric geometry |
| title_fullStr | A hardness of approximation result in metric geometry |
| title_full_unstemmed | A hardness of approximation result in metric geometry |
| title_short | A hardness of approximation result in metric geometry |
| title_sort | hardness of approximation result in metric geometry |
| url | https://hdl.handle.net/1721.1/131412 |
| work_keys_str_mv | AT bradyzarathustra ahardnessofapproximationresultinmetricgeometry AT guthlarry ahardnessofapproximationresultinmetricgeometry AT maninfedor ahardnessofapproximationresultinmetricgeometry AT bradyzarathustra hardnessofapproximationresultinmetricgeometry AT guthlarry hardnessofapproximationresultinmetricgeometry AT maninfedor hardnessofapproximationresultinmetricgeometry |