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

• 成果类型: Article; Proceedings Paper
• 署名作者: Gabow, Harold N.
• 署名单位: University of Colorado System; University of Colorado Boulder
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-006-0061-9
• 发表日期: 2007
• 页码: 111-144
• 关键词: algorithms

摘要

We discuss extensions of Jain's framework for network design [8] that go beyond undirected graphs. The main problem is approximating a minimum cost set of directed edges that covers a crossing supermodular function. We show that iterated rounding gives a factor 3 approximation, where factor 4 was previously known and factor 2 was conjectured. Our bound is tight for the simplest interpretation of iterated rounding. We also show that (the simplest version of) iterated rounding has unbounded approximation ratio when the problem is extended to mixed graphs.