We are glad to have Jack Edmonds with us in Lisbon from the February 16 till March 3.

Jack will give a few lectures in the
course Advanced Algorithms
and the talk below on **February 20, at 13:30** (FA3, Pavilhão de Informática III, Alameda).

Everyone is welcome.

Long Advertisement:

NP and P have origins in “the marriage theorem”:

A matchmaker has as clients the parents of some boys

and some girls where some boy-girl pairs love each other.

The matchmaker must find a marriage of all the girls to distinct boys they love

or else prove to the parents that it is not possible. The input to

this marriage problem is usually imagined as a bipartite graph G

with boy nodes, girl nodes, and edges between them representing love.

A possible legal marriage of

is represented by a subset M of the edges of G, called a matching.

The matchmaker’s problem is to find a matching which hits all the girl nodes

Or else prove to the parents that there is none.

A predicate p(t) is a statement with a variable input t.

For example, p(t) might be the statement:

“There is a matching in bipartite graph, t, which hits all the girl nodes.”

This particular predicate p(t) is in complexity class NP because

whenever it is true there is an easy way relative to the size of t

to show the parents that it is true.

This predicate is also in coNP

whenever t is such that p(t) is not true, an easy way to show the parents

that there is no matching in G which hits all the girl nodes.

(Of course we need a mathematical definition of “easy”.)

It turns out that this predicate p(t) is also in complexity class, P.

That is, relative to the size of t,

there is an

Thinking about this in 1960, it occurred to me that maybe

a general predicate p(t) is in P whenever it is in NP ∩ coNP.

It is still not known whether or not P = NP ∩ coNP in general

but it has turned out to be often true. I think this is the origin of NP.

The optimum

given t = (a bipartite G, a numerical weight cj for each edge j, a matching M in G),

is p(t) true or false, where

p(t) is the statement “M is not the largest total weight matching in G” ?

Obviously this predicate p(t) is in NP because whenever p is true

we can show it easily by showing a larger weight matching.

Is this p in coNP? i.e. is “M is a maximum weight matching in G” in NP?

The 1931 Egervary Theorem says yes because it provides an easy

way to prove when an M is optimum.

Implicit in Egervary’s proof is an easy algorithm for deciding

whether or not the matching M is optimum, and so

this predicate p(t) is in complexity class P.

In 1954 Kuhn dubbed it “the Hungarian Method”.

Silvano Martello and friends have a fine book called

“Assignment Problems”.

http://www.or.deis.unibo.it/staff_pages/martello/cvitae.html

Egervary’s Theorem is the first known instance of

the linear programming duality theorem.

George Dantzig introduced the general field of linear programming,

and invented the simplex method for solving linear programs,

in the late 1940s.

A thrill of my life was in the mid 1960s showing to Dantzig’s l.p. class

that the simplex method can grow exponentially

even for shortest path problems, and so it does not put l.p. into P. In the

1980s Khachian showed that “the ellipsoid method”

(The Hungarian method is

Linear programming has become since the 1950s a foundation of

departments of operations research, management science,

or industrial engineering.

The matchings M in a graph G are represented by vectors x

with a coordinate for each edge j in the edge-set E of G.

“(Incidence) vector” x of M is x

Thus an optimum matching is the vector x of a matching

which maximizes a given linear function, cx, over matching vectors, x.

The convex hull of any finite set Q of points (vectors) in the space

of vectors indexed by the edge-set E of graph G, is a polytope,

the bounded solution-set of a finite set L of linear inequalities.

Thus optimizing cx over members of Q is the same as

the linear program of optimizing cx subject to L.

Normally for an easily described finite set Q of points in R

the number of inequalities needed in L is exponentially large relative to │E│.

Dantzig’s simplex algorithm would then be very exponential time.

An arrangement of the girls and boys around a banquet table

so that each is, on each side, next to someone loved,

is the same as a ‘Hamilton tour’ in the graph G. Suppose we want

a Hamilton tour C which optimizes the sum of love-weights on edges in C.

t = (a graph G, a love-weight c

then where p(t) = [H is not the largest total love-weight Hamilton tour in G],

is p(t) true or false? This predicate is clearly in NP.

In 1971 Steve Cook, and independently Leonid Levin,

showed that there exist NP complete predicates (“problems”).

Dick Karp showed that many natural combinatorial problems,

including the Traveling Salesman Problem, are NP complete. And hence an easy

algorithm for any one of them implies an easy algorithm for any NP predicate.

Throughout the 1960s , though in looking for easy algorithms of course I found

some easy reductions between problems,

have even given NP a bad name, when NP itself is a wonderfully positive thing.

In 1954, Dantzig, with Ray Fulkerson and Selmer Johnson,

solved a particular 48-city traveling salesman problem

by using linear programming. Their linear inequality system L’,

satisfied by all the Hamilton tour vectors, is easy to describe,

though exponentially large. Unfortunately the solution-set of L’ has

some extreme points which are fractional rather than Hamilton tour vectors,

and so optimizing subject to L’ might not be by a Hamilton tour.

Their work motivated Ralph Gomory in 1958

to introduce cutting plane methods for integer linear programming.

There was no mention of ‘easy’, meaning polynomially bounded time.

Their work prompted me in 1961 to notice the simple result

that

of inequalities describing the convex hull of finite point-set Q,

as well as an easy description of the members of Q,

then it does not matter that L is exponentially large in order to have that

the predicate p(t) = [point x of Q is optimum over Q] is in NP ∩ coNP.

And

It seemed plausible that if there is an easy description of Q

then there might be an easy description of a linear system, L,

describing the convex hull of Q. That is an important step

toward an easy general algorithm for optimizing over Q.

In particular I tried hard to find an NP description of a linear system L

whose solution-set is the convex hull of the vectors of Hamilton tours

in a complete graph, G. I was never able to, and so I conjectured that

NP is not equal to P, in particular that the TSP is not in P.

This conjecture is now usefully presumed. It is at the top of the Clay list

of unsolved math problems. Curiously it is the only problem in the list i

which is posed as a question rather than as a conjecture,

so it does not need to be called “Edmonds’ conjecture”.

During the 1960s, the decade before the discovery of NP completeness, as part of

the search for TSP in P, I did find some instances of easily described sets Q to have

NP descriptions of convex-hull determining linear systems, L, and P algorithms.

One of these, which solves the useful “Chinese Postman’s Problem”, is the

“optimum matching problem” in a graph G which is not necessarily bipartite,

i.e., the gay marriage problem, and the optimum gay marriage problem,

by algorithmically proving an easy description of “the matching polytope”.

This was hoped to be an ingredient for solving TSP, though apparently it is not.

In 1961 while working on combinatorial optimization problems in the

new Operations Research Section of the Mathematics Division of the

U.S. National Bureau of Standards, my wonderful mentor Alan Goldman arranged

through his wonderful Princeton mentor, Professor Tucker, thesis supervisor of

Nash’s equilibria and much else, for me to be a junior participant in a Summer

long workshop at the Rand Corporation, across from Muscle Beach in California.

Besides the utter novice me, seemingly every known combinatorist participated.

I needed a successful example of the NP idea, such as the non-bipartite matching

problem. The day before my scheduled lecture to the eminences I still did not

have it. Then Eureka, I did! You shrink blossoms! So the lecture was a success,

and attracted discussion. Professor Tucker offered me a job at Princeton, chairing

the Combinatorics and Games Seminar.

Very old non-bipartite matching “blossom algorithm” papers are on the internet.

Several good books on some P algs are called “Combinatorial Optimization”.

It seems that most of NP∩coNP successes are related to the marriage problem.

Another early P success, which led to matroid theory successes, was

a polynomial time way to solve a system of linear equations, Ax = b.

Well-known Gaussian elimination is not polynomial time

since the number of bits doubles as each column is treated.

The linear elimination algorithm in the very old paper,

Systems of Distinct Representatives and Linear Algebra, on the internet,

is polytime for integer entries but not with indeterminate symbol entries.

Thus there is a polynomial time

for testing non-singularity of the matrix A by substituting integers for symbols.

The paper asks the great still unanswered question: Is there a polynomial time

with indeterminate symbol entries? It answers yes for certain cases

– in particular where the entries of A are zeroes and distinct symbols.

How? By the marriage problem algorithm.

What about when the symbolic entries of A are not all distinct?

Thanks. Please come to the course. Jack.