Measure concentration in optimization

DOI10.1007/BF02614310zbMath0887.90184MaRDI QIDQ1365046

Alexander I. Barvinok

Publication date: 28 August 1997

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

semidefinite programmingpermanentsaverage case analysismeasure concentrationMonte-Carlo integrationmixed discriminantsefficient approximate counting

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Mathematical programming (90C99) Classical measure theory (28A99)

Related Items

Maximum feasible subsystems of distance geometry constraints, Random quantum correlations are generically non-classical, Distance geometry and data science, Concentration of measure for quantum states with a fixed expectation value, Barvinok's naive algorithm in distance geometry, Diagonally Dominant Programming in Distance Geometry, Typical representatives of free homotopy classes in multi-punctured plane

Cites Work

• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Problems of distance geometry and convex properties of quadratic maps
• Computing mixed discriminants, mixed volumes, and permanents
• On the mean radius of permutation polytopes
• Concentration of measure and isoperimetric inequalities in product spaces
• Approximating the permanent: A simple approach
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Two Algorithmic Results for the Traveling Salesman Problem
• Optimal numberings and isoperimetric problems on graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item