Linear programming.
define •
• assumptions:
– nonempty, bounded polyhedron
– minimizing x1
– unique minimum, at a vertex
– exactly d constraints per vertex
definitions: •
– hyperplanes H
– basis B(H) of hyperplanes that define optimum
– optimum value O(H)
• Simplex
– exhaustive polytope search:
– walks on vertices
– runs in O(n�d/2�) time in theory
– often great in practice
• polytime algorithms exist (ellipsoid)
• but bit-dependent (weakly polynomial)!
• OPEN: strongly polynomial LP
• goal today: polynomial algorithms for small d
Random sampling algorithm
• Goal: find B(H)
• Plan: random sample
– solve random subproblem
– keep only violating constraints V
– recurse on leftover
• problem: violators may not contain all of B(H)
• bf BUT, contain some of B(H)
– opt of sample better than opt of whole
1