arxiv: 2605.04183 · v1 · submitted 2026-05-05 · 💻 cs.DS · math.MG

Recognition: 3 theorem links

· Lean Theorem

Nearly-Tight Bounds for Zonotope Containment and Beyond

Friedrich Eisenbrand, Matteo Russo, Ruben Skorupinski, Thomas Rothvoss

Pith reviewed 2026-05-08 18:12 UTC · model grok-4.3

classification 💻 cs.DS math.MG

keywords zonotope containmentapproximation algorithmsmembership oracleTalagrand conjecturespectral sparsificationconvex geometryhigh-dimensional geometry

0 comments

The pith

A sampling-based algorithm approximates zonotope containment to within an O(√d) factor, nearly matching the Ω(√d/log d) lower bound in the oracle model.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper studies the problem of computing the largest scaling factor s such that a zonotope scaled by s fits inside an outer convex body Q, where Q is given only via a membership oracle that answers whether points lie inside it. The central contribution is a polynomial-time sampling algorithm that returns an approximation to this largest s within a multiplicative factor of O(√d), coming close to the best possible guarantee of Ω(√d/log d) that follows from earlier lower-bound constructions. Under the additional assumption that any zonotope admits a sparsification down to a linear number of generators, the same approach yields the optimal factor Θ(√d/log d). The authors establish this sparsification property for the special class of constant-Δ modular zonotopes by linking it to spectral sparsification techniques, and they prove a matching Ω(√d/log d) lower bound that holds for every zonotope. For arbitrary convex bodies the paper shows that a Θ(d/log d) factor is both achievable and tight in the oracle model.

Core claim

The central claim is that the zonotope containment problem max{s > 0 : sZ ⊆ Q} admits a sampling-based O(√d)-approximation algorithm in the membership-oracle model that nearly matches the Ω(√d/log d) lower bound of Khot and Naor; under the Talagrand conjecture on linear sparsification of zonotopes the factor improves to the optimal Θ(√d/log d). The conjecture is proved for Δ-modular zonotopes with constant Δ by reduction to the Batson-Spielman-Srivastava spectral sparsification theorem, and a universal Ω(√d/log d) lower bound is shown for all zonotopes. For general convex bodies a tight Θ(d/log d) approximation is obtained via Naszódi's polytope approximation result, and the same lower bound

What carries the argument

The sampling procedure that estimates the maximal scaling factor s for a zonotope inside an oracle-described body, together with the reduction of improved approximation to linear zonotope sparsification and its equivalence to spectral sparsification in the constant-Δ modular case.

If this is right

Zonotope containment has approximation factor between Ω(√d/log d) and O(√d) in the oracle model.
The optimal Θ(√d/log d) factor is achievable for all constant-Δ modular zonotopes.
General convex-body containment admits a tight Θ(d/log d) approximation in polynomial time with oracles.
Barvinok's polytope approximation of centrally symmetric convex bodies cannot be computed in polynomial time under the oracle model.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The link between zonotope sparsification and spectral sparsification may yield new approximation results for other structured convex bodies.
Oracle-based sampling techniques could be adapted to containment problems involving spectrahedra or other spectrahedral shadows.
The universal lower bound indicates that high-dimensional convex containment problems remain computationally hard even when oracles are provided.

Load-bearing premise

Every zonotope can be sparsified to a linear number of generators (Talagrand conjecture), which the paper verifies only for constant-Δ modular zonotopes.

What would settle it

A concrete zonotope Z together with a membership oracle for some outer body Q such that the returned scaling factor differs from the true optimum by more than a constant multiple of √d, or a constant-Δ modular zonotope that requires super-linear generators in every sparsification.

Figures

Figures reproduced from arXiv: 2605.04183 by Friedrich Eisenbrand, Matteo Russo, Ruben Skorupinski, Thomas Rothvoss.

**Figure 1.** Figure 1: The main idea behind the algorithm. A vertex view at source ↗

read the original abstract

We investigate the convex-body containment problem $\max\{s >0 : s Z \subseteq Q\}$, where the outer body $Q \subseteq \mathbb R^d$ is described by a membership oracle and the inner body $Z \subseteq \mathbb R^d$ is a zonotope. Our main result is a sampling-based $O(\sqrt{d})$-approximation algorithm for this problem that almost matches the lower bound of $\Omega(\sqrt{d/\log d})$ by Khot and Naor in the oracle model. Assuming zonotopes can be sparsified by a linear number of generators, which is referred to as Talagrand conjecture, our approach attains the optimal approximation factor of $\Theta(\sqrt{d/\log d})$. Our second main result is a proof of Talagrand's conjecture for $\Delta$-modular zonotopes whenever $\Delta$ is constant. Those zonotopes are of the form $Z = \{ Wx \colon \| x\|_\infty \leq 1\}$ where the non-zero $d \times d$ sub-determinants of $W$ are between $1$ and $\Delta$. This result establishes a connection between zonoid sparsification and spectral sparsification of Batson, Spielman and Srivastava. We complement these results with a universal $\Omega(\sqrt{d/\log d})$ lower bound holding for all zonotopes. Finally, we consider containment problems $\max\{s >0 : s K \subseteq Q\}$, for general convex bodies $K \subseteq \mathbb R^d$. A result of Nasz\'odi on approximating $K \subseteq \mathbb R^d$ by a polytope implies a $\Theta(d/\log d)$ approximation algorithm in polynomial time. We show the tightness of this approximation factor in the oracle model via a reduction to the circumradius computation. Our lower bound holds for centrally symmetric convex sets, implying that Barvinok's optimal $O(\sqrt{d})$-approximation of a centrally symmetric convex body by a polytope with a polynomial number of vertices cannot be computed in polynomial time.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a solid O(sqrt(d)) sampling algorithm for zonotope containment in the oracle model and proves Talagrand's conjecture for constant-Delta modular zonotopes via spectral sparsification, but the optimal Theta(sqrt(d/log d)) bound remains conditional on the general conjecture.

read the letter

The key point is that this work provides a sampling algorithm for the zonotope containment problem that runs in the membership oracle model and achieves an O(sqrt(d)) approximation factor. This comes close to the Omega(sqrt(d / log d)) lower bound from Khot and Naor. They also show a lower bound of the same order that holds for every zonotope, and they prove Talagrand's conjecture on linear sparsification when the zonotope is Delta-modular with Delta constant, using a reduction to the Batson-Spielman-Srivastava spectral sparsification technique. What the paper does well is establish that connection between zonotope sparsification and spectral methods. It is a clean link that might have broader uses. The algorithm itself is sampling-based, which fits the oracle setting nicely, and the tightness result for general convex bodies via circumradius computation is a solid addition. The claims line up with the cited prior work without obvious circularity. The main limitation is that the stronger Theta(sqrt(d / log d)) guarantee requires the full Talagrand conjecture, which remains open outside the constant-Delta modular case. The general algorithm stops at O(sqrt(d)), so the nearly-tight label is accurate only conditionally. The soundness looks reasonable from the abstract, with no internal contradictions, but the sampling analysis and the exact error bounds would need close inspection in the full proofs. The citation pattern is appropriate, building on the right references. This paper is for people working on high-dimensional convex geometry, approximation algorithms, and related areas in theoretical computer science. A reader who knows the Khot-Naor lower bound and the basics of zonotopes will find the new contributions clear. It shows honest engagement with the literature and the open problems, so it qualifies as serious thinking even if one disagrees on the importance of the special case. I think it deserves peer review. The results are substantial enough to warrant referee time, even with the conditional optimality.

Referee Report

0 major / 3 minor

Summary. The manuscript investigates the convex-body containment problem of computing the largest s > 0 such that sZ ⊆ Q, where Q is given via membership oracle and Z is a zonotope. The central algorithmic result is a sampling-based O(√d)-approximation algorithm that nearly matches the Ω(√d/log d) lower bound. Assuming the Talagrand conjecture on linear sparsification of zonotopes, the algorithm achieves the optimal Θ(√d/log d) factor. The authors prove the conjecture for constant-Δ modular zonotopes by reduction to Batson-Spielman-Srivastava spectral sparsification. They also establish a universal Ω(√d/log d) lower bound that holds for every zonotope and show that the analogous containment problem for general convex bodies K admits a tight Θ(d/log d) approximation in the oracle model via a reduction to circumradius computation.

Significance. If the claims hold, the work advances the theory of approximation algorithms for high-dimensional convex containment problems in the membership-oracle model. The unconditional O(√d) algorithm together with the matching (up to log d) lower bound, the explicit connection between zonoid sparsification and spectral sparsification, and the tightness result for general convex bodies are all substantive contributions. The special-case resolution of Talagrand’s conjecture for constant-Δ modular zonotopes is a concrete positive step that may guide future work on the general conjecture.

minor comments (3)

[Abstract] Abstract: the sentence 'our approach attains the optimal approximation factor of Θ(√d/log d)' is qualified by the assumption, but a parenthetical reminder that the assumption is proven only for constant-Δ modular zonotopes would prevent any reader from misreading the headline result as unconditional optimality.
[Lower-bound section] The universal lower bound is stated to hold for all zonotopes; the manuscript should explicitly indicate in the relevant theorem statement (presumably §4 or §5) whether the proof is self-contained or re-uses the Khot-Naor construction, so that the 'complement' claim is immediately verifiable.
[Preliminaries / Definition of modular zonotopes] Notation: the definition of Δ-modular zonotopes via non-zero d×d sub-determinants is clear, yet a short sentence recalling that this class includes all zonotopes generated by integer matrices with bounded minors would help readers outside combinatorial optimization.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, the recognition of its contributions to approximation algorithms for convex containment in the oracle model, and the recommendation for minor revision. No specific major comments were listed in the report, so we have no individual points requiring detailed rebuttal or revision.

Circularity Check

0 steps flagged

No significant circularity; main results are self-contained algorithmic and hardness contributions

full rationale

The paper's core O(√d) sampling algorithm for zonotope containment is derived from membership-oracle access and standard convex-geometry sampling techniques, without reducing to fitted parameters or self-definitions. The unconditional lower bound of Ω(√d/log d) is established directly via reduction to circumradius computation, while the cited Khot-Naor bound serves as external context rather than a load-bearing self-citation. The Talagrand conjecture is used only conditionally for the tighter Θ(√d/log d) factor, with an independent proof supplied for the constant-Δ modular case that reduces to the external Batson-Spielman-Srivastava spectral sparsification theorem; no ansatz, renaming, or uniqueness claim is smuggled through self-citation. The general-body results similarly rely on Naszódi's external polytope approximation and a direct oracle-model reduction, keeping the derivation chain non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies on established frameworks in convex geometry and the oracle model with no new free parameters, invented entities, or ad-hoc axioms introduced to support the central claims.

axioms (2)

standard math Standard definitions and properties of zonotopes, convex bodies, and membership oracles in Euclidean space
Invoked throughout the problem formulation and algorithm design in the abstract.
domain assumption Existence and usability of a membership oracle for the outer body Q
Central modeling assumption for the containment problem.

pith-pipeline@v0.9.0 · 5690 in / 1539 out tokens · 28370 ms · 2026-05-08T18:12:56.520244+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

59 extracted references · 4 canonical work pages

[1]

Combining zonotopes and support functions for efficient reach- ability analysis of linear systems

Matthias Althoff and Goran Frehse. “Combining zonotopes and support functions for efficient reach- ability analysis of linear systems”. In:CDC. IEEE, 2016, pp. 7439–7446

2016
[2]

Integer programs with nearly totally unimodular matrices: the cographic case

Manuel Aprile et al. “Integer programs with nearly totally unimodular matrices: the cographic case”. In:SODA. SIAM, 2025, pp. 2301–2312

2025
[3]

A strongly polynomial algorithm for bimodular integer linear programming

Stephan Artmann, Robert Weismantel, and Rico Zenklusen. “A strongly polynomial algorithm for bimodular integer linear programming”. In:STOC. ACM, 2017, pp. 1206–1219

2017
[4]

Geometric bijections for regular matroids, zonotopes, and Ehrhart theory

Spencer Backman, Matthew Baker, and Chi Ho Yuen. “Geometric bijections for regular matroids, zonotopes, and Ehrhart theory”. In:Forum of Mathematics, Sigma. Vol. 7. Cambridge University Press. 2019, e45

2019
[5]

Shadows of convex bodies

Keith Ball. “Shadows of convex bodies”. In:Transactions of the American Mathematical Society327.2 (1991), pp. 891–901

1991
[6]

Thrifty approximations of convex bodies by polytopes

Alexander Barvinok. “Thrifty approximations of convex bodies by polytopes”. In:International Math- ematics Research Notices2014.16 (2014), pp. 4341–4356

2014
[7]

Twice-Ramanujan Sparsifiers

Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava. “Twice-Ramanujan Sparsifiers”. In:SIAM Review56.2 (2014), pp. 315–334

2014
[8]

Approximating Matrixp-norms

Aditya Bhaskara and Aravindan Vijayaraghavan. “Approximating Matrixp-norms”. In:SODA. SIAM, 2011, pp. 497–511

2011
[9]

Inapproximability of Matrix p→q Norms

Vijay Bhattiprolu et al. “Inapproximability of Matrix p→q Norms”. In:SIAM J. Comput.52.1 (2023), pp. 132–155

2023
[10]

A Class of Convex Bodies

Ethan D. Bolker. “A Class of Convex Bodies”. In:Transactions of the American Mathematical Society 145 (1969), pp. 323–345

1969
[11]

Geometry of Banach spaces and harmonic analysis

Jean Bourgain. “Geometry of Banach spaces and harmonic analysis”. In:Proceedings of the Interna- tional Congress of Mathematicians. Vol. 1. Citeseer. 1986, p. 2

1986
[12]

On high dimensional maximal functions associated to convex bodies

Jean Bourgain. “On high dimensional maximal functions associated to convex bodies”. In:American Journal of Mathematics108.6 (1986), pp. 1467–1476

1986
[13]

Approximation of zonoids by zonotopes

Jean Bourgain, Joram Lindenstrauss, and Vitali Milman. “Approximation of zonoids by zonotopes”. In:Acta Mathematica162 (1989), pp. 73–141

1989
[14]

The vector balancing constant for zonotopes

Rainie Bozzai, Victor Reis, and Thomas Rothvoss. “The vector balancing constant for zonotopes”. In: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2023, pp. 1292– 1300

2023
[15]

Approximation of Diameters: Randomization Doesn’t Help

Andreas Brieden et al. “Approximation of Diameters: Randomization Doesn’t Help”. In:FOCS. IEEE Computer Society, 1998, pp. 244–251

1998
[16]

Deterministic and randomized polynomial-time approximation of radii

Andreas Brieden et al. “Deterministic and randomized polynomial-time approximation of radii”. In: Mathematika48.1-2 (2001), pp. 63–105

2001
[17]

L p Row Sampling by Lewis Weights

Michael B. Cohen and Richard Peng. “L p Row Sampling by Lewis Weights”. In:STOC. ACM, 2015, pp. 183–192

2015
[18]

A near-optimal algorithm for approximating the John Ellipsoid

Michael B. Cohen et al. “A near-optimal algorithm for approximating the John Ellipsoid”. In:COLT. Proceedings of Machine Learning Research. PMLR, 2019, pp. 849–873

2019
[19]

Gaussian Cooling andO ∗(n3)Algorithms for Volume and Gaus- sian Volume

Ben Cousins and Santosh Vempala. “Gaussian Cooling andO ∗(n3)Algorithms for Volume and Gaus- sian Volume”. In:SIAM Journal on Computing47.3 (2018), pp. 1237–1273. 16

2018
[20]

Graded Ehrhart Theory of Unimodular Zonotopes

Colin Crowley and Ethan Partida. “Graded Ehrhart Theory of Unimodular Zonotopes”. In:arXiv preprint arXiv:2603.07873(2026)

work page arXiv 2026
[21]

Excluding a Line Minor via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure

Daniel Dadush et al. “Excluding a Line Minor via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure”. In:SODA. SIAM, 2026, pp. 871–879

2026
[22]

Quermaßintegrals and asymptotic shape of random polytopes in an isotropic convex body

Nikos Dafnis, Apostolos Giannopoulos, and Antonis Tsolomitis. “Quermaßintegrals and asymptotic shape of random polytopes in an isotropic convex body”. In:Michigan Mathematical Journal62.1 (2013), pp. 59–79

2013
[23]

A Random Polynomial Time Algorithm for Ap- proximating the Volume of Convex Bodies

Martin E. Dyer, Alan M. Frieze, and Ravi Kannan. “A Random Polynomial Time Algorithm for Ap- proximating the Volume of Convex Bodies”. In:Journal of the ACM38.1 (1991), pp. 1–17

1991
[24]

Integer programs with bounded subdeterminants and two nonzeros per row

Samuel Fiorini et al. “Integer programs with bounded subdeterminants and two nonzeros per row”. In:Journal of the ACM72.1 (2025)

2025
[25]

On the complexity of four polyhedral set containment prob- lems

Robert M. Freund and James B. Orlin. “On the complexity of four polyhedral set containment prob- lems”. In:Mathematical Programming33.2 (1985), pp. 139–145

1985
[26]

Complexity of Injectivity and Verification of ReLU Neural Networks (Extended Abstract)

Vincent Froese, Moritz Grillo, and Martin Skutella. “Complexity of Injectivity and Verification of ReLU Neural Networks (Extended Abstract)”. In:COLT. Vol. 291. Proceedings of Machine Learning Research. PMLR, 2025, pp. 2188–2189

2025
[27]

Open Problem: Fixed-Parameter Tractability of Zonotope Problems

Vincent Froese et al. “Open Problem: Fixed-Parameter Tractability of Zonotope Problems”. In:COLT. Vol. 291. Proceedings of Machine Learning Research. PMLR, 2025, pp. 6210–6214

2025
[28]

Parameterized Hardness of Zonotope Containment and Neural Network Verifi- cation

Vincent Froese et al. “Parameterized Hardness of Zonotope Containment and Neural Network Verifi- cation”. In:CoRRabs/2509.22849 (2025)

work page arXiv 2025
[29]

On the Number of Distinct Rows of a Matrix with Bounded Subdeterminants

Christoph Glanzer, Robert Weismantel, and Rico Zenklusen. “On the Number of Distinct Rows of a Matrix with Bounded Subdeterminants”. In:SIAM Journal on Discrete Mathematics32.3 (2018), pp. 1706–1720

2018
[30]

Extremal properties of orthogonal parallelepipeds and their applications to the geometry of Banach spaces

Efim Davydovich Gluskin. “Extremal properties of orthogonal parallelepipeds and their applications to the geometry of Banach spaces”. In:Mathematics of the USSR-Sbornik64.1 (1989), pp. 85–96

1989
[31]

Martin Grötschel, László Lovász, and Alexander Schrijver.Geometric Algorithms and Combinatorial Optimization. Vol. 2. Algorithms and Combinatorics. Springer, 1988

1988
[32]

Geometric Methods in Combinatorial Op- timization

Martin Grötschel, László Lovász, and Alexander Schrijver. “Geometric Methods in Combinatorial Op- timization”. In:Progress in Combinatorial Optimization. Academic Press, 1984, pp. 167–183

1984
[33]

A note on Bourgain’s slicing problem

Qingyang Guan. “A note on Bourgain’s slicing problem”. In:arXiv preprint arXiv:2412.09075(2024)

work page arXiv 2024
[34]

Estimating the Matrix pq Norm

Larry Guth, Dominique Maldague, and John Urschel. “Estimating the Matrix pq Norm”. In:SIAM Journal on Matrix Analysis and Applications46.3 (2025), pp. 2080–2092

2025
[35]

Hardness of approximation of centered convex bodies by polytopes

Han Huang and Mark Rudelson. “Hardness of approximation of centered convex bodies by polytopes”. In:arXiv preprint arXiv:2602.23034(2026)

work page arXiv 2026
[36]

Random walks and anO ∗(n5)volume algorithm for convex bodies

Ravi Kannan, László Lovász, and Miklós Simonovits. “Random walks and anO ∗(n5)volume algorithm for convex bodies”. In:Random Structures and Algorithms11.1 (1997), pp. 1–50

1997
[37]

Linear equations modulo 2 and theL 1 diameter of convex bodies

Subhash Khot and Assaf Naor. “Linear equations modulo 2 and theL 1 diameter of convex bodies”. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07). IEEE. 2007, pp. 318–328

2007
[38]

Affirmative resolution of Bourgain’s slicing problem using Guan’s bound

Boaz Klartag and Joseph Lehec. “Affirmative resolution of Bourgain’s slicing problem using Guan’s bound”. In:Geometric and Functional Analysis35.4 (2025), pp. 1147–1168

2025
[39]

On the co-NP-completeness of the zonotope containment problem

Adrian Kulmburg and Matthias Althoff. “On the co-NP-completeness of the zonotope containment problem”. In:European Journal of Control62 (2021), pp. 84–91. 17

2021
[40]

Search-based and stochastic solutions to the zonotope and ellipsotope containment problems

Adrian Kulmburg, Ivan Brkan, and Matthias Althoff. “Search-based and stochastic solutions to the zonotope and ellipsotope containment problems”. In:2024 European Control Conference (ECC). IEEE. 2024, pp. 1057–1064

2024
[41]

Approximability of the Containment Problem for Zonotopes and Ellipsotopes

Adrian Kulmburg, Lukas Schafer, and Matthias Althoff. “Approximability of the Containment Problem for Zonotopes and Ellipsotopes”. In:IEEE Transactions on Automatic ControlPP (Jan. 2025), pp. 1–16

2025
[42]

The incidence structure of subspaces with well-scaled frames

Jon Lee. “The incidence structure of subspaces with well-scaled frames”. In:Journal of Combinatorial Theory, Series B50.2 (1990), pp. 265–287

1990
[43]

Polynomial Upper Bounds on the Number of Differing Columns of∆-Modular Integer Programs

Jon Lee et al. “Polynomial Upper Bounds on the Number of Differing Columns of∆-Modular Integer Programs”. In:Mathematics of Operations Research48.4 (2023), pp. 2267–2286

2023
[44]

Random Walks in a Convex Body and an Improved Volume Algorithm

László Lovász and Miklós Simonovits. “Random Walks in a Convex Body and an Improved Volume Algorithm”. In:Random Structures and Algorithms4.4 (1993), pp. 359–412

1993
[45]

The Mixing Rate of Markov Chains, an Isoperimetric Inequal- ity, and Computing the Volume

László Lovász and Miklós Simonovits. “The Mixing Rate of Markov Chains, an Isoperimetric Inequal- ity, and Computing the Volume”. In:FOCS. IEEE Computer Society, 1990, pp. 346–354

1990
[46]

Hit-and-Run from a Corner

László Lovász and Santosh Vempala. “Hit-and-Run from a Corner”. In:SIAM Journal on Computing 35.4 (2006), pp. 985–1005

2006
[47]

Nabil H Mustafa.Sampling in combinatorial and geometric set systems. Vol. 265. American Mathemat- ical Society, 2022

2022
[48]

Approximating a convex body by a polytope using the epsilon-net theorem

Márton Naszódi. “Approximating a convex body by a polytope using the epsilon-net theorem”. In: Discrete and Computational Geometry61.3 (2019), pp. 686–693

2019
[49]

On the Column Number and Forbidden Submatrices for∆-Modular Matrices

Joseph Paat et al. “On the Column Number and Forbidden Submatrices for∆-Modular Matrices”. In: SIAM Journal on Discrete Mathematics38.1 (2024), pp. 1–18

2024
[50]

University of Washington

Thomas Rothvoss.Asymptotic Convex Geometry. University of Washington. 2021

2021
[51]

Linear encodings for polytope containment problems

Sadra Sadraddini and Russ Tedrake. “Linear encodings for polytope containment problems”. In:2019 IEEE 58th conference on decision and control (CDC). IEEE. 2019, pp. 4367–4372

2019
[52]

Two observations regarding embedding subsets of Euclidean spaces in normed spaces

Gideon Schechtman. “Two observations regarding embedding subsets of Euclidean spaces in normed spaces”. In:Advances in Mathematics200.1 (2006), pp. 125–135

2006
[53]

John Wiley & Sons, 1998

Alexander Schrijver.Theory of linear and integer programming. John Wiley & Sons, 1998

1998
[54]

Approximability of the problem of finding a vector subset with the longest sum

Vladimir Shenmaier. “Approximability of the problem of finding a vector subset with the longest sum”. In:Journal of Applied and Industrial Mathematics12.4 (2018), pp. 749–758

2018
[55]

Complexity and algorithms for finding a subset of vectors with the longest sum

Vladimir Shenmaier. “Complexity and algorithms for finding a subset of vectors with the longest sum”. In:Theoretical Computer Science818 (2020), pp. 60–73

2020
[56]

How to compute the volume in high dimension?

Miklós Simonovits. “How to compute the volume in high dimension?” In:Mathematical Programming 97.1-2 (2003), pp. 337–374

2003
[57]

Computation of matrix norms with applications to robust optimization

Daureen Steinberg. “Computation of matrix norms with applications to robust optimization”. In:Re- search thesis, Technion-Israel University of Technology2 (2005)

2005
[58]

Embedding Subspaces ofL 1 intoℓ N 1

Michel Talagrand. “Embedding Subspaces ofL 1 intoℓ N 1 ”. In:Proceedings of the American Mathematical Society108.2 (1990), pp. 363–369

1990
[59]

Ziegler.Lectures on polytopes

Günter M. Ziegler.Lectures on polytopes. Vol. 152. Springer Science & Business Media, 2012. 18

2012