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

DOI10.1007/S10107-006-0061-9zbMATH Open1111.90115OpenAlexW2110257828MaRDI QIDQ877196FDOQ877196

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)

Cites Work

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

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)