jackedmonds2010

	Programa de doctorat de Matemàtica Aplicada Facultat de Matemàtiques i Estadística Universitat Politècnica de Catalunya
	Advanced Course Polymatroids etcetera: Algorithms and Pretty Theorems by Jack Edmonds January11-21, 2010

Course Description

Some quotes from the book 'Combinatorial Optimization', by Lex Schrijver

Registration and further information

Preliminary Schedule

Preliminary list of participants

Lecture room and directions

Updates will be posted concerning lecture room, directions, list of participants and course notes.

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 and further information

Please send an e-mail tagged 'Edmonds2010Course' to info.osrm@upc.edu indicating

Name
Affiliation
e-mail address
Short cv (academic degree, current situation, mathematical background)

There is no registration fee.

For further information please contact info.osrm@upc.edu.

You are kindly requested to post the pdf announcement of the course.

Preliminary Schedule

Day	Time	Topic
Tuesday 12	11h-13h	Marriage, Network Flows, Traveling Salesmen.
Wednesday 13	11h-13h	Linear Systems: Indeterminate, Diophantine, or Non-negative.
Thursday 14	11h-13h	Polymatroids, Submodularity, Intersections and Partitioning.
Tuesday 19	11h-13h	Branching Systems.
Wednesday 20	11h-13h	Lemke Pivoting and Game Theory.
Thursday 21	11h-13h	Boolean Circuits, Extrema, and Complexity.

Preliminary list of participants

Aguiló, Francesc (Ma4, UPC Barcelona)
Aráoz, Julián (LSI, UPC, Barcelona)
Arratia, Argimiro (LSI, UPC, Barcelona)

Atserias, Albert (LSI, UPC, Barcelona)

Ball, Simeon (MA4, UPC, Barcelona)
Balle, Borja (LSI, UPC, Barcelona)

Boroczky, Karoly (Rényi Institute, Budapest)
Brunat, Josep M. (Ma2, UPC, Barcelona)

Jordi Castro (LSI, UPC, Barcelona)
Chen, Hubie (UPF, Barcelona)

Chen, Lei (ITN, Linkopkins Univ., Sweeden)

Comellas, Francesc (Ma4, UPC, Barcelona)

Conde, Josep (Univ Lleida)
Dalmau, Víctor (UPF, Barcelona)
Fàbrega, Josep (Ma4, UPC, Barcelona)

Faizrahnemoon, Mahsa (Amirkabir Univ. Technology, Tehran)

Farràs, Oriol (MA4, UPC, Barcelona)

Gascón, Adrià (LSI, UPC, Barcelona)

Gavaldà, Ricard (LSI, UPC, Barcelona)

Gimbert, Joan (U de LLeida)

Huemer, Clemens (Ma4, UPC, Barcelona)

LLadó, Anna (Ma4, UPC, Barcelona)
López-Masip, Susana-Clara (Ma4, UPC, Barcelona)

Maneva, Elitza (UB, Barcelona)
Marueso, Montserrat (Ma2, UPC, Barcelona)

Miralles, Alícia (Ma4, UPC, Barcelona)

Noy, Marc (Ma2, UPC, Barcelona)
Oliva, Sergi (LSI, UPC, Barcelona)
Padrol, Arnau (Ma2, UPC, Barcelona)
Perarnau, Guillem (Ma4, UPC, Barcelona)
Pérez-Mansilla, Sónia (Ma4, UPC, Barcelona)
Pfeifle, Julian (Ma2, UPC, Barcelona)
Sanvicente, Emilio (ENTEL, UPC, Barcelona)
Serra, Oriol (Ma4, UPC, Barcelona)

Lecture room and directions

The lectures will be held in Room 101 in the building of the Facultat de Matemàtiques i Estadística.

Please see the map for the location of the building. To get there you can use Metro L3 (Green Line)

and step off at Palau Reial. For further directions ask info.osrm@upc.edu

Updates will be posted concerning lecture room, directions, list of participants and course notes.