A generalized approximation framework for fractional network flow and packing problems

Michael Holzhauser () and Sven O. Krumke ()
Additional contact information
Michael Holzhauser: University of Kaiserslautern
Sven O. Krumke: University of Kaiserslautern

Mathematical Methods of Operations Research, 2018, vol. 87, issue 1, No 2, 19-50

Abstract: Abstract We generalize the fractional packing framework of Garg and Koenemann (SIAM J Comput 37(2):630–652, 2007) 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 : Ax \le b, x \in C \}$$ max { c T x : A x ≤ b , x ∈ C } , 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.

Keywords: Approximation algorithms; Fractional packing; Network flows (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00186-017-0604-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:87:y:2018:i:1:d:10.1007_s00186-017-0604-2

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-017-0604-2

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().