On the L_-norm of extreme points for crossing supermodular directed network LPs

DOI10.1007/S10107-006-0061-9MaRDI QIDQ877196zbMATH OpenOpenAlexFDO

Authors 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

Approximation algorithmsLinear programmingNetwork 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)

Recommendations

• On the L  ∞ -Norm of Extreme Points for Crossing Supermodular Directed Network LPs
• Algorithms for a network design problem with crossing supermodular demands
• scientific article; zbMATH DE number 1342141
• Directed Network Design with Orientation Constraints
• Additive guarantees for degree-bounded directed network design

Cites work

• scientific article; zbMATH DE number 3661345 (Why is no real title available?)
• scientific article; zbMATH DE number 1757945 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Algorithms for a network design problem with crossing supermodular demands
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• Approximation Algorithms for Several Graph Augmentation Problems
• Approximation algorithm for \(k\)-node connected subgraphs via critical graphs
• Approximation algorithms for minimum-cost k-vertex connected subgraphs
• Biconnectivity approximations and graph carvings
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Submodular functions in graph theory

Cited in

(2)

• On the L  ∞ -Norm of Extreme Points for Crossing Supermodular Directed Network LPs
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding

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

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