Linear Programming
6.854 Notes #11

David Karger

1 Linear Programming

1.1 Introduction

Problem description:

lemma: every LP is infeasible, has opt, or is unbounded

Problem formulation:

Some steps towards efficient solution:

1.2 Linear Equalities

How solve? First review systems of linear equalities.

To talk formally about polynomial size/time, need to talk about size of problems.

Claim: if \(A\) is \(n \times n\) matrix, then \(\det(A)\) is poly in size of \(A\)


What if \(A\) isn’t square? Can we find an answer?

So can check answer in polynomial time.

Can we show there isn’t an answer?


1.3 Geometry


1.4 Basic Feasible Solutions

Again, let’s start by thinking about structure of optimal solution.

Where can optimum be? At “corners.”

Basic solutions:

In fact, vertex, extreme point, bfs are equivalent.

Any standard form lp \(\min cx,\ Ax=b,\ x\ge 0\) with opt has one at a BFS.



1.5 Vertices and Extreme Points

Two other characterizations of corner.


Extreme Point

Shows output is polynomial size:

Yields first algorithm for LP: try all bfs.

OK, this is an exponential method for finding the optimum. Maybe we can do better if we just try to verify the optimum. Let’s look for a way to prove that a given solution \(x\) is optimal.

Quest for nonexponential algorithm: start at an easier place: how decide if a solution is optimal?