ISMP ’09: Tuesday

Today I spent the whole day (and part of the night) meeting with two of my co-authors and working on our research papers. That means I only had time to attend the two plenaries.
The morning plenary was given by Friedrich Eisenbrand and it was entitled “Algorithmic Geometry of Numbers and Integer Programming”. He talked about many classical problems in geometry of numbers such as the shortest vector problem and mentioned that finding a polynomial time approximation algorithm for it is an open question. Then, among other things, he proceeded to show that there is an equivalence between polynomial-time and strongly-polynomial time solvability for 0-1 optimization. He spent a good deal of time on the topic of integer programming in fixed dimensions and the quest for a linear-time algorithm. One curious observation (which I didn’t know) was that one can compute the gcd of two numbers a and b by solving the following integer program:
minimize xa + yb
s.t. xa + yb >= 1
x, y integer
Paul Tseng’s semi-plenary was cancelled, so I attended the talk by Martin Skutella on “Flows Over Time: Classical and More Recent Results”. He started by saying that flows over time are sort of like traditional network flows plus a scheduling component. There are added issues like transit time on arcs and flow variation due to things like seasonality. Classic flows, however, are static. One of the ways to deal with flows over time is by means of a time-expanded network, which is built by having a duplicate copy of the network for each time instant. This creates issues of efficiency, of course, which can be sometimes mitigated by carefully reducing the size of the expanded network. Other approaches involve approximation algorithms, which simplify the network at the cost of violating the time horizon limit. Some problems that are easy for static flows, become NP-Hard for flows over time, e.g. min cost flow. It was also interesting to learn that, in their original work, Ford and Fulkerson had already thought of flows over time. In addition, just like traditional max flows and min cuts come in pairs, there’s also something called a cut over time, but he didn’t get into the details of that. One of the interesting applications is in the area of evacuation planning. There the concept of earliest arrival flows comes up: find a flow over time that maximizes the arrival of flow into the sink at every time instant. Martin provided a link to a website (http://www.zet-evakuierung.de) that shows an animated evacuation plan that’s calculated with the help of simulation and the theory of flows over time. Pretty cool.
Today’s food picks: the penne with pesto and sun dried tomatoes at ESPN Zone (? E Ohio St) is pretty good, as is the Mezzelune Funghette at Coco Pazzo (300 W Hubbard St).

Today, I spent the whole day (and part of the night) meeting with two of my co-authors and working on our research papers. That means I only had time to attend the two plenaries (sorry to those who were counting on a more extensive report).

The morning plenary was given by Friedrich Eisenbrand and it was entitled “Algorithmic Geometry of Numbers and Integer Programming”. He talked about many classical problems in geometry of numbers such as the shortest vector problem and mentioned that finding a polynomial time approximation algorithm for it is an open question. Then, among other things, he proceeded to show that there is an equivalence between polynomial-time and strongly-polynomial time solvability for 0-1 optimization. He spent a good deal of time on the topic of integer programming in fixed dimensions and the quest for a linear-time algorithm. One curious observation (which I didn’t know) was that one can compute the gcd of two numbers a and b by solving the following integer program:

minimize  xa + yb

subject to:  xa + yb >= 1

x, y  integer

Paul Tseng‘s semi-plenary was cancelled, so I attended the talk by Martin Skutella on “Flows Over Time: Classical and More Recent Results”. He started by saying that flows over time are sort of like traditional network flows plus a scheduling component. There are added issues like transit time on arcs and flow variation due to things like seasonality. Classic flows, however, are static. One of the ways to deal with flows over time is by means of a time-expanded network, which is built by having a duplicate copy of the network for each time instant. This creates issues of efficiency, of course, which can be sometimes mitigated by carefully reducing the size of the expanded network. Other approaches involve approximation algorithms, which simplify the network at the cost of violating the time horizon limit. Some problems that are easy for static flows, become NP-Hard for flows over time, e.g. min cost flow. It was also interesting to learn that, in their original work, Ford and Fulkerson had already thought of flows over time. In addition, just like traditional max flows and min cuts come in pairs, there’s also something called a cut over time, but he didn’t get into the details of that. One of the interesting applications is in the area of evacuation planning. There the concept of earliest arrival flows comes up: find a flow over time that maximizes the arrival of flow into the sink at every time instant. Martin provided a link to a website (http://www.zet-evakuierung.de) about a project on evacuation simulation and optimization (and its associated software). He played a video that shows an animated evacuation plan that’s calculated with the help of simulation and the theory of flows over time. Pretty cool. (I guess it can be downloaded from that website.)

Today’s food picks: the penne with pesto and sun-dried tomatoes at ESPN Zone (43 E Ohio St) is pretty good, as is the Mezzalune Funghetto at Coco Pazzo (300 W Hubbard St).

3 Comments

Filed under ISMP, Travel

3 responses to “ISMP ’09: Tuesday

  1. apricoco

    something is wrong with your RSS feed when trying to view your posts in google reader… hmmm

  2. Ricardo

    This year I couldn’t attend to ISMP, but having some of it commented here is just great. Thanks for all ISMP related posts.

  3. orbythebeach

    You’re welcome, Ricardo. Yesterday I was too busy/tired and did not post, but later tonight I’ll do a combined Wed+Thu post. Um abraço.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s