A BOUNDED APPROXIMATION FOR THE MINIMUM COST 2-SAT PROBLEM

被引：25

作者：

GUSFIELD, D ^{[1
]}

PITT, L ^{[1
]}

机构：

[1] UNIV ILLINOIS, DEPT COMP SCI, URBANA, IL 61801 USA

来源：

ALGORITHMICA | 1992年 / 8卷 / 02期

关键词：

SATISFIABILITY; COMBINATORIAL OPTIMIZATION; STABLE ROOMMATES PROBLEM; APPROXIMATION ALGORITHM;

D O I：

10.1007/BF01758838

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Given a satisfiable Boolean formula in 2-CNF, it is NP-hard to find a satisfying assignment that contains a minimum number of true variables. A polynomial-time approximation algorithm is given that finds an assignment with at most twice as many true variables as necessary. The algorithm also works for a weighted generalization of the problem. An application to the optimal stable roommates problem is given in detail, and other applications are mentioned.

引用

页码：103 / 117

页数：15

共 22 条

[1]

[Anonymous], 1989, STABLE MARRIAGE PROB

[2]

[Anonymous], 1971, STOC 71, DOI DOI 10.1145/800157.805047

[3] STRUCTURE PRESERVING REDUCTIONS AMONG CONVEX-OPTIMIZATION PROBLEMS [J].