An approximation algorithm for network design problems with downwards-monotone demand functions

被引：3

作者：

Laszlo, Michael ^{[1
]}

Mukherjee, Sumitra ^{[1
]}

机构：

[1] Nova SE Univ, Grad Sch Comp & Informat Sci, Ft Lauderdale, FL 33314 USA

来源：

OPTIMIZATION LETTERS | 2008年 / 2卷 / 02期

关键词：

Network design problems; Approximation algorithms; Spanning forests; Integer programs;

D O I：

10.1007/s11590-007-0051-8

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Building on an existing 2-approximate algorithm for the class of network design problems with downwards-monotone demand functions, many of which are NP-hard, we present an algorithm that produces solutions that are at least as good as and typically better than solutions produced by the existing algorithm.

引用

页码：171 / 175

页数：5

共 8 条

[1] [Anonymous], 2001, Introduction to Algorithms
[2] Local ratio:: A unified framework for approximation algorithms -: In memoriam:: Shimon!Even -: 1935-2004
Bar-Yehuda, R
Bendel, K
Freund, A
Rawitz, D
[J]. ACM COMPUTING SURVEYS, 2004, 36 (04) : 422 - 463
[3] A GENERAL APPROXIMATION TECHNIQUE FOR CONSTRAINED FOREST PROBLEMS
GOEMANS, MX
WILLIAMSON, DP
[J]. SIAM JOURNAL ON COMPUTING, 1995, 24 (02) : 296 - 317
[4] GOEMANS MX, 1994, OPER RES LETT, V183, P244
[5] Goemans MX, 1997, APPROXIMATION ALGORI, P144
[6] A GREEDY HEURISTIC FOR A MINIMUM-WEIGHT FOREST PROBLEM
IMIELINSKA, C
KALANTARI, B
KHACHIYAN, L
[J]. OPERATIONS RESEARCH LETTERS, 1993, 14 (02) : 65 - 71
[7] Another greedy heuristic for the constrained forest problem
Laszlo, M
Mukherjee, S
[J]. OPERATIONS RESEARCH LETTERS, 2005, 33 (06) : 629 - 633
[8] Reinelt G., 1991, ORSA Journal on Computing, V3, P376, DOI 10.1287/ijoc.3.4.376

← 1 →