Leírás
Abstract: A min-max theorem (or a good characterization) often serves as a
stopping rule or optimization criterion for checking immediately the
correctness of the output provided by an algorithm. Though there are
many algorithms without such a background (using a greedy approach or
dynamic programming), in several cases it is hopeless to develop an
efficient algorithm without knowing a stopping rule in advance. Think
of developing an algorithm for maximum matching without the
Berge-Tutte formula or for minimum dijoin without the Lucchesi-Younger
theorem. Polyhedral methods along with linear programming duality are
often in the background of such min-max results.
In the present talk, we consider problems where l.p. duality is not
enough anymore, and outline a new approach based on concepts from
discrete convex optimization. In this way, a great number of new
min-max theorems can be derived which pave the way to develop
polynomial algorithms. For example, finding a strongly connected
(even, $k$-edge-connected and in-degree constrained) orientation of a
mixed graph for which the square-sum of the in-degrees is minimum fits
the framework, as well as a wide class of inverse combinatorial
optimization problems.
No prerequisite is required from Discrete convex analysis, just the
opposite: a major goal of the talk, beyond outlining concrete
results, is to demonstrate and foster that DCA may become an
indispensable and ubiquitous tool in standard discrete optimization.
The talk is based on a joint work with Kazuo Murota.
After the talk, there will be a short virtual meeting with free discussion on any topic.
Please contact Tamás Király (tkiraly[at]cs.elte.hu) for Zoom access if you are not on the mailing list.