Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations

被引：46

作者：

Hochbaum, DS ^{[1
]}

机构：

[1] Univ Calif Berkeley, Dept Ind Engn & Operat Res, Berkeley, CA 94720 USA

[2] Univ Calif Berkeley, Walter A Haas Sch Business, Berkeley, CA 94720 USA

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2002年 / 140卷 / 02期

关键词：

approximation algorithm; half integrality; feasible cut; minimum satisfiability; vertex cover; generalized satisfiability; maximum clique; superoptimal; minimum cut;

D O I：

10.1016/S0377-2217(02)00071-1

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

引用

页码：291 / 321

页数：31

共 40 条

[1]

Ahuja RK, 1999, LECT NOTES COMPUT SC, V1610, P31

[2]

AHUJA RK, 1999, UNPUB CUT BASED ALGO

[3]

BALL M, 1992, P 5 US POST SERV ADV, P1169

[4] A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine [J].

Chudak, FA ;

Hochbaum, DS .

OPERATIONS RESEARCH LETTERS, 1999, 25 (05) :199-204

[5] A FAST PARAMETRIC MAXIMUM FLOW ALGORITHM AND APPLICATIONS [J].

GALLO, G ;

GRIGORIADIS, MD ;

TARJAN, RE .

SIAM JOURNAL ON COMPUTING, 1989, 18 (01) :30-55

[6] Approximate max-flow min-(multi)cut theorems and their applications [J].

Garg, N ;

Vazirani, VV ;

Yannakakis, M .

SIAM JOURNAL ON COMPUTING, 1996, 25 (02) :235-251

[7]

GARG N, 1994, P 21 INT C AUT LANG, P487

[8]

GARG N, 1994, ALGORITHMICA, V18, P3

[9]

GOEMANS MX, 1995, J ACM, V42, P115

[10] A NEW APPROACH TO THE MAXIMUM-FLOW PROBLEM [J].

GOLDBERG, AV ;

TARJAN, RE .

JOURNAL OF THE ACM, 1988, 35 (04) :921-940

← 1 2 3 4 →