{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,22]],"date-time":"2026-03-22T03:05:09Z","timestamp":1774148709837,"version":"3.50.1"},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T00:00:00Z","timestamp":1731974400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T00:00:00Z","timestamp":1731974400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"NSF-BSF grant","award":["\u201cGlobal Geometry of Graphs\u201d"],"award-info":[{"award-number":["\u201cGlobal Geometry of Graphs\u201d"]}]},{"DOI":"10.13039\/501100003483","name":"Hebrew University of Jerusalem","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003483","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The collection of all <jats:italic>n<\/jats:italic>-point metric spaces of diameter <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\le 1$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> constitutes a polytope <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\mathcal {M}_n \\subset \\mathbb {R}^{\\left( {\\begin{array}{c}n\\\\ 2\\end{array}}\\right) }$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>M<\/mml:mi>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>\u2282<\/mml:mo>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mi>R<\/mml:mi>\n                      <\/mml:mrow>\n                      <mml:mfenced>\n                        <mml:mrow>\n                          <mml:mtable>\n                            <mml:mtr>\n                              <mml:mtd>\n                                <mml:mi>n<\/mml:mi>\n                              <\/mml:mtd>\n                            <\/mml:mtr>\n                            <mml:mtr>\n                              <mml:mtd>\n                                <mml:mrow>\n                                  <mml:mrow\/>\n                                  <mml:mn>2<\/mml:mn>\n                                <\/mml:mrow>\n                              <\/mml:mtd>\n                            <\/mml:mtr>\n                          <\/mml:mtable>\n                        <\/mml:mrow>\n                      <\/mml:mfenced>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, called the <jats:italic>Metric Polytope<\/jats:italic>. In this paper, we consider the best approximations of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\mathcal {M}_n$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>M<\/mml:mi>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> by ellipsoids. We give an exact explicit description of the largest volume ellipsoid contained in <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\mathcal {M}_n$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>M<\/mml:mi>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. When inflated by a factor of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Theta (n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, this ellipsoid contains <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\mathcal {M}_n$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>M<\/mml:mi>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. It also turns out that the least volume ellipsoid containing <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\mathcal {M}_n$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>M<\/mml:mi>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> is a ball. When shrunk by a factor of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Theta (n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, the resulting ball is contained in <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\mathcal {M}_n$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>M<\/mml:mi>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. We note that the general theorems on such ellipsoid posit only that the pertinent inflation\/shrinkage factors can be made as small as <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(n^2)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00454-024-00703-4","type":"journal-article","created":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T09:12:03Z","timestamp":1732007523000},"page":"271-285","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the L\u00f6wner-John Ellipsoids of the Metric Polytope"],"prefix":"10.1007","volume":"74","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-8372-5143","authenticated-orcid":false,"given":"Raziel","family":"Gartsman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nati","family":"Linial","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,11,19]]},"reference":[{"issue":"2","key":"703_CR1","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF00182424","volume":"41","author":"K Ball","year":"1992","unstructured":"Ball, K.: Ellipsoids of maximal volume in convex bodies. Geom. Dedic. 41(2), 241\u2013250 (1992). https:\/\/doi.org\/10.1007\/BF00182424","journal-title":"Geom. Dedic."},{"key":"703_CR2","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/978-94-011-0924-6_16","volume-title":"Polytopes: Abstract, Convex and Computational","author":"A Deza","year":"1994","unstructured":"Deza, A., Deza, M.: The ridge graph of the metric polytope and some relatives. In: Polytopes: Abstract, Convex and Computational, pp. 359\u2013372. Springer, Dordrecht (1994)"},{"key":"703_CR3","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/3-540-47738-1_10","volume-title":"Discrete and Computational Geometry","author":"A Deza","year":"2001","unstructured":"Deza, A., Fukuda, K., Pasechnik, D., Sato, M.: On the skeleton of the metric polytope. In: Akiyama, J., Kano, M., Urabe, M. (eds.) Discrete and Computational Geometry, pp. 125\u2013136. Springer, Berlin (2001)"},{"key":"703_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04295-9","volume-title":"Monique: Geometry of Cuts and Metrics. Algorithms and Combinatorics","author":"M Deza","year":"1997","unstructured":"Deza, M., Laurent, M.: Monique: Geometry of Cuts and Metrics. Algorithms and Combinatorics. Springer, Berlin (1997)"},{"issue":"2","key":"703_CR5","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s10107-005-0620-5","volume":"104","author":"A Frangioni","year":"2005","unstructured":"Frangioni, A., Lodi, A., Rinaldi, G.: New approaches for optimizing over the semimetric polytope. Math. Program. 104(2), 375\u2013388 (2005). https:\/\/doi.org\/10.1007\/s10107-005-0620-5","journal-title":"Math. Program."},{"issue":"106","key":"703_CR6","first-page":"4","volume":"95","author":"M Henk","year":"2012","unstructured":"Henk, M.: L\u00f6wner-John Ellipsoids. Doc. Math. Optim. Stories 95(106), 4 (2012)","journal-title":"Doc. Math. Optim. Stories"},{"key":"703_CR7","unstructured":"John, F.: Extremum problems with inequalities as subsidiary conditions, Studies and Essays Presented to R. Courant on his 60th Birthday (1948)"},{"key":"703_CR8","doi-asserted-by":"crossref","unstructured":"Kozma G, Meyerovitch T, Peled R, Samotij W.: What does a typical metric space look like? In: Annales de l\u2019Institut Henri Poincare (B) Probabilites et Statistiques, vol.\u00a060, pp. 11\u201353, Institut Henri Poincar\u00e9 (2024)","DOI":"10.1214\/22-AIHP1262"},{"issue":"1","key":"703_CR9","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0012-365X(94)00091-V","volume":"151","author":"M Laurent","year":"1996","unstructured":"Laurent, M.: Graphic vertices of the metric polytope. Discrete Math. 151(1), 131\u2013153 (1996). https:\/\/doi.org\/10.1016\/0012-365X(94)00091-V","journal-title":"Discrete Math."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00703-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-024-00703-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00703-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T15:04:28Z","timestamp":1758294268000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-024-00703-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,19]]},"references-count":9,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["703"],"URL":"https:\/\/doi.org\/10.1007\/s00454-024-00703-4","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,19]]},"assertion":[{"value":"19 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 October 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 November 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}