INFORMS journal on computing · 2008 · 120 citations · 16 references
Natural SciencesComputer ScienceMathematicsAlgorithmsDesign OptimizationOptimizationApproximation AlgorithmsCombinatorial OptimizationHeuristic OptimizationInteger ProgrammingLayout OptimizationMetaheuristic OptimizationDiversity OptimizationGraph PartitioningHeuristic AlgorithmsInteger Quadratic ProgrammingNp-hardnessPartitioning ProblemsQuadratic Integer ProgrammingScatter Search
The max-cut problem consists of finding a partition of the nodes of a weighted graph into two subsets such that the sum of the weights on the arcs connecting the two subsets is maximized. This is an NP-hard problem that can also be formulated as an integer quadratic program. Several solution methods have been developed since the 1970s and applied to a variety of fields, particularly in engineering and layout design. We propose a heuristic method based on the scatter-search methodology for finding approximate solutions to this optimization problem. Our solution procedure incorporates some innovative features within the scatter-search framework: (1) the solution of the maximum diversity problem to increase diversity in the reference set, (2) a dynamic adjustment of a key parameter within the search, and (3) the adaptive selection of a combination method. We perform extensive computational experiments to first study the effect of changes in critical scatter-search elements and then to compare the efficiency of our proposal with previous solution procedures.
16
P-Complete Approximation Problems
Sartaj Sahni, Teofilo F. Gonzalez · Journal of the ACM · 1976 · 1.7K citations · Full text
On the Shannon capacity of a graph
László Lovász · IEEE Transactions on Information Theory · 1979 · 1.7K citations