Discrete and Computational Geometry

DOI10.1007/B11261MaRDI QIDQ5897088zbMATH OpenOpenAlexFDO

Authors David Avis

Publication date 5 February 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b11261

Mathematics Subject Classification ID

Inequalities and extremum problems involving convexity in convex geometry (52A40) Computational aspects related to convexity (52B55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
• A bound on the k-gonality of facets of the hypermetric cone and related complexity problems
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• Estimating the gap of finite metric spaces of strict \(p\)-negative type
• Testing gap \(k\)-planarity is NP-complete
• Tight bounds for testing k-linearity
• scientific article; zbMATH DE number 4147329
• Complexity results for the gap inequalities for the max-cut problem
• Some complexity bounds for subtype inequalities
• scientific article; zbMATH DE number 2086691

Cited in

(5)

• A bound on the k-gonality of facets of the hypermetric cone and related complexity problems
• Binary Positive Semidefinite Matrices and Associated Integer Polytopes
• Complexity results for the gap inequalities for the max-cut problem
• The Boolean quadric polytope
• Binary positive semidefinite matrices and associated integer polytopes

This page was built for publication: Discrete and Computational Geometry

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5897088)