A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes

DOI10.1287/moor.24.3.544zbMath0967.90079OpenAlexW2159658403MaRDI QIDQ4951039

Karl Heinz Borgwardt

Publication date: 3 September 2001

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://opus.bibliothek.uni-augsburg.de/opus4/files/28277/%2826%29A%20Sharp%20Upper%20Bound%20for%20the%20Expected%20Number%20of%20Shadow-Vertices.....pdf

zbMATH Keywords

stochastic geometryaverage-case complexityrotation symmetry modelcanonical linear programming

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Random convex sets and integral geometry (aspects of convex geometry) (52A22)

Related Items (1)

A Friendly Smoothed Analysis of the Simplex Method

This page was built for publication: A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes