Fast and simple approximation schemes for generalized flow.

DOI10.1007/S101070100238zbMATH Open1049.90105OpenAlexW2144532599MaRDI QIDQ5957564FDOQ5957564

Authors: Lisa Fleischer, Kevin D. Wayne 

Publication date: 2002

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s101070100238

Recommendations

• Combinatorial approximation algorithms for generalized flow problems
• Approximating fractional multicommodity flow independent of the number of commodities
• New algorithms for generalized network flows
• Fast approximation algorithms for multicommodity flow problems
• Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Abstract computational complexity for mathematical programming problems (90C60)

Cited In (14)

• A generalized approximation framework for fractional network flow and packing problems
• A simple GAP-canceling algorithm for the generalized maximum flow problem
• A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
• Title not available (Why is that?)
• Maximum flows in generalized processing networks
• Approximation schemes for fractional multicommodity flow problems
• A strongly polynomial algorithm for generalized flow maximization
• Distributive lattices, polyhedra, and generalized flows
• Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains
• A critical survey on the network optimization algorithms for evacuation planning problems
• Shortest path and maximum flow problems in networks with additive losses and gains
• Efficient Approximation of Flow Problems With Multiple Scales in Time
• Malleable scheduling for flows of jobs and applications to MapReduce
• Generalized maximum flow over time with intermediate storage

This page was built for publication: Fast and simple approximation schemes for generalized flow.

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