%0 Conference Paper %1 DBLP:conf/foga/Pourhassan0N17 %A Pourhassan, Mojgan %A Friedrich, Tobias %A Neumann, Frank %B Foundations of Genetic Algorithms (FOGA) %D 2017 %I ACM Press %K testing typo3 %P 37-44 %T On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary Algorithms %X We consider the weighted minimum vertex cover problem and investigate how its dual formulation can be exploited to design evolutionary algorithms that provably obtain a 2-approximation. Investigating multi-valued representations, we show that variants of randomized local search and the (1+1) EA achieve this goal in expected pseudo-polynomial time. In order to speed up the process, we consider the use of step size adaptation in both algorithms and show that RLS obtains a 2-approximation in expected polynomial time while the (1+1) EA still encounters a pseudo-polynomial lower bound.

@inproceedings{DBLP:conf/foga/Pourhassan0N17, abstract = {We consider the weighted minimum vertex cover problem and investigate how its dual formulation can be exploited to design evolutionary algorithms that provably obtain a 2-approximation. Investigating multi-valued representations, we show that variants of randomized local search and the (1+1) EA achieve this goal in expected pseudo-polynomial time. In order to speed up the process, we consider the use of step size adaptation in both algorithms and show that RLS obtains a 2-approximation in expected polynomial time while the (1+1) EA still encounters a pseudo-polynomial lower bound.}, added-at = {2017-09-19T19:30:30.000+0200}, author = {Pourhassan, Mojgan and Friedrich, Tobias and Neumann, Frank}, biburl = {https://www.bibsonomy.org/bibtex/290cbeb5fe879709946df3eb2ddbbce78/typo3tester}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, interhash = {394738f0df56e127c12247569d2ef74d}, intrahash = {90cbeb5fe879709946df3eb2ddbbce78}, keywords = {testing typo3}, pages = {37-44}, publisher = {ACM Press}, timestamp = {2017-09-19T19:30:30.000+0200}, title = {On the Use of the Dual Formulation for Minimum Weighted Vertex Cover in Evolutionary Algorithms}, year = 2017 }