期刊
INFORMS JOURNAL ON COMPUTING
卷 25, 期 2, 页码 208-221出版社
INFORMS
DOI: 10.1287/ijoc.1110.0496
关键词
programming; integer; algorithms; heuristic
We develop a new local search algorithm for binary optimization problems, whose complexity and performance are explicitly controlled by a parameter Q, measuring the depth of the local search neighborhood. We show that the algorithm is pseudo-polynomial for general cost vector c, and achieves a w(2)/(2w - 1) approximation guarantee for set packing problems with exactly w ones in each column of the constraint matrix A, when using Q = w(2). Most importantly, we find that the method has practical promise on large, randomly generated instances of both set covering and set packing problems, as it delivers performance that is competitive with leading general-purpose optimization software (CPLEX 11.2).
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据