scientific article; zbMATH DE number 1302174
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].
- Computing and minimizing the relative regret in combinatorial optimization with interval data
- Optimization with additional variables and constraints
- Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
- Approximation algorithms for fractional knapsack problems
- Min-max controllable risk problems
- Network disconnection games: a game theoretic approach to checkpoint evaluation in networks
- Column generation extensions of set covering greedy heuristics
- Expanding maximum capacity path under weighted sum-type distances
- Fractional 0-1 programming and submodularity
- Optimization on fractal sets
- Assortment optimization under the multinomial logit model with product synergies
- The maximum ratio clique problem
- Mathematical optimization ideas for biodiversity conservation
- A strongly polynomial algorithm for line search in submodular polyhedra
- Complexity of source-sink monotone 2-parameter min cut
- Exact solution approaches for a class of bilevel fractional programs
- Interdicting structured combinatorial optimization problems with {0,1}-objectives
- Sparsest-cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
- Solution of a fractional combinatorial optimization problem by mixed integer programming
- scientific article; zbMATH DE number 1256704 (Why is no real title available?)
- Approximation algorithms for combinatorial fractional programming problems
- A Mixed-Integer Fractional Optimization Approach to Best Subset Selection
- The multiroute maximum flow problem revisited
- On maximum ratio clique relaxations
- A survey of exact and approximation algorithms for linear-parametric optimization problems
- The inverse optimal value problem for linear fractional programming
- Parameterized searching with mismatches for run-length encoded strings
- Optimal selection of forest patches using integer and fractional programming
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4247441)
