*********************************
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: Information and Entropy
SPEAKER: Sebastian Pokutta
ABSTRACT:
Limits of system performance can often understood in the context of
information and entropy. In the talk we give two examples. One
theoretical one where a strong bound on the size of a smallest possible
representation is obtained via an entropy argument. The second deals
with an application where the goal is to eliminate information
asymmetries using optimization methods.
More precisely:
In the first part, we solve a 20-year old problem posed by M.
Yannakakis and prove that there exists no polynomial-size linear program
(LP) whose associated polytope projects to the traveling salesman
polytope, even if the LP is not required to be symmetric. Moreover, we
prove that this holds also for the maximum cut problem and the stable
set problem.
In the second part, we consider a real-world energy market coupling
problem which aims for a more balanced and consistent determination of
prices in adjacent markets in presence of coupling mechanisms. By doing
so the amount of possible arbitrage is minimized.
(The first part is joined work with: Samuel Fiorini, Serge Massar,
Hans Raj Tiwary, and Ronald de Wolf // the second part is joined work
with: Alexander Martin and Johannes Müller)
