A generalized approximation framework for fractional network flow and packing problems

DOI10.1007/S00186-017-0604-2zbMATH Open1388.90102arXiv1612.05474OpenAlexW2571358802MaRDI QIDQ684147FDOQ684147

Michael Holzhauser, Sven O. Krumke

Publication date: 9 February 2018

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

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.

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

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

zbMATH Keywords

network flowsapproximation algorithmsfractional packing

Mathematics Subject Classification ID

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

Cites Work

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

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)