Access Restriction

Author Avdil, Alaubek ♦ Weihe, Karsten
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2009
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Combinatorial optimization ♦ Heuristic ♦ Hybrid algorithms ♦ Local search ♦ Max-SAT ♦ Max-cut ♦ Max-k-SAT ♦ Polyhedral combinatorics
Abstract We present and evaluate a specific way to generate good start solutions for local search. The start solution is computed from a certain LP, which is related to the underlying problem. We consider three optimization problems: the directed MAX-CUT problem with a source and a sink and two variations of the $MAX-\textit{k}-SAT$ problem with $\textit{k}$ = 2 and $\textit{k}$ = 3. To compare our technique, we run local search repeatedly with random start solutions. Our technique produces, consistently, final solutions whose objective values are not too far from the best solutions from repeated random starts. The surprising degree of stability and uniformity of this result throughout all of our experiments on various classes of instances strongly suggests that we have consistently achieved nearly optimal solutions. On the other hand, the runtime of our technique is rather small, so the technique is very efficient and probably quite accurate.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2010-01-05
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 14
Page Count 26
Starting Page 1.6
Ending Page 1.31

Open content in new tab

   Open content in new tab
Source: ACM Digital Library