-------------------------------------------------------------------------------------
Polymatroids etcetera: Algorithms and Pretty Theorems
by Jack Edmonds
January 11 to 21, 2010
Facultat de Matematiques i Estadistica
Universitat Politecnica de Catalunya
Barcelona, Spain
--------------------------------------------------------------------------------------
Course Description
A variety of combinatorial existence theorems will be proved by
algorithms which
tell how to find an instance of what is asserted to exist.
Another main purpose will be to introduce polyhedral combinatorics,
which uses systems of linear equations to obtain algorithms and theorems.
Emphasis will be on matroids and polymatroids with a variety of
applications,
especially to tree systems and branching systems in networks.
Books and graph theory and combinatorial optimization will be resources.
Drafts of notes will be incrementally available.
-------------------------------------------------------------------------------------
Some quotes from the book 'Combinatorial Optimization', by Lex Schrijver
(Springer, 2000)
"Pionereed by the work of Jack Edmonds, polyhedral combinatorics has
proved to be a most powerful, coherent and unifying tool throughout
combinatorial optimization. Not only has it led to efficient (that is,
polynomial-time) algorithms, but also, conversely, efficient algorithms
often
imply polyhedral characterizations and related min-max relations. It
makes the two sides closely intertwined."
" In the 1960's Edmonds advocated calling an algorithm efficient [or
"good"] if its running time is bounded by a polynomial in the size of its
representation. Since then, this criterion has won broad acceptance,
also because Edmonds found polynomial-time algorithms for several
important optimization problems"
"Edmonds conjectured that there is no polynomial-time algorithm for the
traveling salesman problem. In language that was
developed later, this is equivalent to NP?P."
------------------------------------------------------------------------------------
Registration
Please send an email tagged 'Edmonds2010Course', as soon as possible,
to info.osrm@upc.edu, indicating your situation and email address.
There is no registration fee.
Further information at
https://www-ma4.upc.edu/~oserra/seminari/jackedmonds2010.html
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
