*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
TITLE: Projection of Shortest Path Extended Formulations
ABSTRACT:
Several important subproblems, such as switching machines on and off, finding an optimal convex set in 2-D, or buying and selling of a commodity, can be formulated as shortest/longest path problems in an acyclic graph. The corresponding polyhedron provides an implicit polynomial size description of the convex hull of solutions. A natural question is whether one can find a similar description in the original variables of the problem. In this talk we present several examples, each time using a different technique to obtain the projection. This is in large part joint work with Maurice Queyranne.
