Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, March 18, 2010, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Andrea Francke

A Quasioptimum for Linear Programs (Master's Thesis Presentation)

By a "quasioptimum", we denote a generalized notion of an optimum for a linear program that also is defined when the underlying program is unbounded or infeasible. It is intended to share some of the important properties of true optima of bounded and feasible linear programs. Such a quasioptimum might permit a simpler and more uniform treatment of solutions to linear programs when results from linear programming are used as building blocks in combinatorial proofs or algorithms. The specific quasioptimum I defined in my master's thesis is based on work by Gärtner and Schurr [1], who relate linear programming with unique sink orientations (USOs). In my talk, I am going to say more about the motivation behind my work, about the quasioptimum defined in my thesis, and its strenghts and weaknesses.

[1] Gärtner, B. and Schurr, I. 2006. Linear programming and unique sink orientations. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (Miami, Florida, January 22 - 26, 2006). SODA '06. ACM, New York, NY, 749-757. DOI

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login