A generalized approximation framework for fractional network flow and packing problems

DOI10.1007/S00186-017-0604-2MaRDI QIDQ684147zbMATH OpenOpenAlexFDO

Authors Michael Holzhauser, Sven O. Krumke

Publication date 9 February 2018

Published in Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.05474

zbMATH Keywords

network flowsapproximation algorithmsfractional packing

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Abstract: We generalize the fractional packing framework of Garg and Koenemann to the case of linear fractional packing problems over polyhedral cones. More precisely, we provide approximation algorithms for problems of the form $max{c}^{T}x:Axleqb,xinC$, where the matrix $A$ contains no negative entries and $C$ is a cone that is generated by a finite set $S$ of non-negative vectors. While the cone is allowed to require an exponential-sized representation, we assume that we can access it via one of three types of oracles. For each of these oracles, we present positive results for the approximability of the packing problem. In contrast to other frameworks, the presented one allows the use of arbitrary linear objective functions and can be applied to a large class of packing problems without much effort. In particular, our framework instantly allows to derive fast and simple fully polynomial-time approximation algorithms (FPTASs) for a large set of network flow problems, such as budget-constrained versions of traditional network flows, multicommodity flows, or generalized flows. Some of these FPTASs represent the first ones of their kind, while others match existing results but offer a much simpler proof.

Recommendations

• Fast and simple approximation schemes for generalized flow.
• Approximating Fractional Packings and Coverings in O(1/epsilon) Iterations
• Near-linear time approximation schemes for some implicit fractional packing problems
• scientific article; zbMATH DE number 2163022
• Approximating fractional multicommodity flow independent of the number of commodities

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256706 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 910872 (Why is no real title available?)
• A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow
• A capacity scaling algorithm for the constrained maximum flow problem
• A characterization of the minimum cycle mean in a digraph
• A double scaling algorithm for the constrained maximum flow problem
• A faster polynomial algorithm for the constrained maximum flow problem
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• A note on two problems in connexion with graphs
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Approximate parametric searching
• Approximating Fractional Packings and Coverings in O(1/epsilon) Iterations
• Approximating fractional multicommodity flow independent of the number of commodities
• Approximation Schemes for the Restricted Shortest Path Problem
• Budget-constrained minimum cost flows
• Combinatorial Optimization with Rational Objective Functions
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• Combinatorial approximation algorithms for generalized flow problems
• Combinatorial optimization. Networks and matroids
• Coordination Complexity of Parallel Price-Directive Decomposition
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
• Fast and simple approximation schemes for generalized flow.
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Faster approximation schemes for fractional multicommodity flow problems
• Geometric algorithms and combinatorial optimization.
• Improved Algorithms For Linear Inequalities with Two Variables Per Inequality
• Maximizing concave functions in fixed dimension
• Maximum flows in generalized processing networks
• On a capacity scaling algorithm for the constrained maximum flow problem
• On the complexity and approximability of budget-constrained minimum cost flows
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• Potential function methods for approximately solving linear programming problems: theory and practice.
• Slowing down sorting networks to obtain faster sorting algorithms
• Testing membership in matroid polyhedra

Cited in

(1)

• A simplex algorithm for network flow problems with piecewise linear fractional objective function

This page was built for publication: A generalized approximation framework for fractional network flow and packing problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q684147)