Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Monday, January 16, 2006, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Kiyohito Nagano (Univ. of Tokyo)
Submodularity plays an important role in combinatorial optimization. A submodular polyhedron (or an extended polymatroid) is a polyhedron associated with a submodular set function. In this talk, we consider a line search problem in a submodular polyhedron, which is a generalization of submodular function minimization and a fair maximum flow problem. We present a first strongly polynomial time algorithm for this problem with the aid of a fully combinatorial algorithm for submodular function minimization. The algorithm is based on the parametric search method proposed by Megiddo.
Automatic MiSe System Software Version 1.4803M | admin login