On the \(L_{\infty}\)-norm of extreme points for crossing supermodular directed network LPs

DOI10.1007/s10107-006-0061-9zbMath1111.90115OpenAlexW2110257828MaRDI QIDQ877196

Harold N. Gabow

Publication date: 19 April 2007

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

Full work available at URL: https://doi.org/10.1007/s10107-006-0061-9

zbMATH Keywords

Linear programmingApproximation algorithmsNetwork designBasic feasible solutionCrossing supermodular functionDirected networksExtreme pointIterated rounding

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) Approximation algorithms (68W25)

Related Items (1)

Approximating the smallest k -edge connected spanning subgraph by LP-rounding

Cites Work

• Submodular functions in graph theory
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Approximation algorithms for minimum-cost k-vertex connected subgraphs
• Approximation algorithm for k-node connected subgraphs via critical graphs
• Approximation Algorithms for Several Graph Augmentation Problems
• Biconnectivity approximations and graph carvings
• Algorithms for a network design problem with crossing supermodular demands
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the \(L_{\infty}\)-norm of extreme points for crossing supermodular directed network LPs