SC 98-24 Norbert Ascheuer, Martin Grötschel, Sven O. Krumke, Jörg Rambau: Combinatorial Online Optimization (Appeared in: Proceedings of the International Conference of
Operations Research Zürich (OR98), Springer, 1999, pp.
21-37)
Abstract: In ``classical optimization, all data of a problem instance
are
considered given. The standard theory and the usual algorithmic
techniques apply to such cases only. Online optimization is
different. Many decisions have to be made before all data are
available. In addition, decisions once made cannot be changed. How
should one act ``best in such an environment?
In this paper we survey online problems coming up in combinatorial
optimization. We first outline theoretical concepts, such as
competitiveness against various adversaries, to analyze online
problems and algorithms. The focus, however, lies on real-world
applications. We report, in particular, on theoretical
investigations and our practical experience with problems arising in
transportation and the automatic handling of material.
Keywords: Online Optimization,
competitiveness,
combinatorial optimization,
real-world problems
MSC: 90C27, 90B06, 90C90