No label defined (Q4247441)

Fractional combinatorial optimization (FCO) is a special case of general fractional optimization: maximize \(f(x)/g(x)\) over a subset \(D\) of \(\mathbb{R}^n\). An equivalent formulation of FCO is as follows: find \(\delta\in R\) such that \(h(\delta)=0\), where \(h(\delta)= \max\{f(x)- \delta g(x)\mid x\in X \subseteq\{0,1\}^p\}\). This Handbook chapter is focused on two main methods for FCO, the Newton method and Megiddo's parametric search method. Computational complexity of these methods are analysed for general linear case and for several problems on linear graphs with \(n\) vertices and \(m\) edges. It is proved, for example, the Newton method solves a linear FCO problem in \(O(p^2\log p)\) iterations, maximum-ratio paths (and cycles) problem in \(O(m\log n)\) iterations and maximum mean-weight cut problem in \(O(m)\) iterations for nonnegative edge weights. Megiddo's method is generalized by introducing a linear algorithm and the notion of a stage of the computation. Using this framework three theorems concerning time complexity are presented. The chapter is clearly written and is a valuable reference to researchers in combinatorial optimization. Concluding remarks outlines some problems yet unsolved. For the entire collection see [Zbl 0903.90001].