### Local search starting from an LP solution: Fast and quite goodLocal search starting from an LP solution: Fast and quite good

Access Restriction
Subscribed

 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

Source: ACM Digital Library