GRAPH SEPARATION TECHNIQUES FOR QUADRATIC ZERO-ONE PROGRAMMING

被引:11
作者
PARDALOS, PM
JHA, S
机构
[1] Computer Science Department, Pennsylvania State University, University Park
关键词
D O I
10.1016/0898-1221(91)90165-Z
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
In this paper, we consider a divide-and-conquer algorithm for quadratic zero-one programs. The algorithm is based on the use of separators of the related graph. For some classes of problems, the algorithm runs in subexponential or in polynomial time.
引用
收藏
页码:107 / 113
页数:7
相关论文
共 15 条
[1]   A SOLVABLE CASE OF QUADRATIC 0-1 PROGRAMMING [J].
BARAHONA, F .
DISCRETE APPLIED MATHEMATICS, 1986, 13 (01) :23-26
[2]   A SURVEY OF METHODS FOR PURE NON-LINEAR INTEGER PROGRAMMING [J].
COOPER, MW .
MANAGEMENT SCIENCE, 1981, 27 (03) :353-361
[3]  
Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1
[4]   UNCONSTRAINED QUADRATIC BIVALENT PROGRAMMING PROBLEM [J].
GULATI, VP ;
GUPTA, SK ;
MITTAL, AK .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1984, 15 (01) :121-125
[5]  
Hansen P., 1979, Discrete Optimisation, P53
[6]  
KRARUP J, 1978, MATH PROGRAM STUD, V9, P75, DOI 10.1007/BFb0120827
[7]   APPLICATIONS OF A PLANAR SEPARATOR THEOREM [J].
LIPTON, RJ ;
TARJAN, RE .
SIAM JOURNAL ON COMPUTING, 1980, 9 (03) :615-627
[8]   AN IMPLICIT ENUMERATION ALGORITHM FOR QUADRATIC INTEGER PROGRAMMING [J].
MCBRIDE, RD ;
YORMARK, JS .
MANAGEMENT SCIENCE, 1980, 26 (03) :282-296
[9]   A PARALLEL ALGORITHM FOR THE QUADRATIC ASSIGNMENT PROBLEM [J].
PARDALOS, PM ;
CROUSE, JV .
PROCEEDINGS : SUPERCOMPUTING 89, 1989, :351-360
[10]  
PARDALOS PM, 1987, LECTURE NOTES COMPUT, V268