%0 Conference Paper %1 chauhan2017approximating %A Chauhan, Ankit %A Friedrich, Tobias %A Quinzan, Francesco %B Genetic and Evolutionary Computation Conference (GECCO) %D 2017 %K testing typo3 %P 235-242 %T Approximating Optimization Problems using EAs on Scale-Free Networks %X It has been experimentally observed that real-world networks follow certain topologicalproperties, such as small-world, power-law etc. To study these networks, many random graph models, such as Preferential Attachment, have been proposed. In this paper, we consider the deterministic properties which capture power-law degree distribution and degeneracy. Networks with these properties are known as scale-free networks in the literature. Many interesting problems remain NP-hard on scale-free networks. We study the relationship between scale-free properties and the approximation-ratio of some commonly used evolutionary algorithms. For the Vertex Cover, we observe experimentally that the \((1+1)\) EA always gives the better result than a greedy local search, even when it runs for only \(O(n, log(n))\) steps. We give the construction of a scale-free network in which a multi-objective algorithm and a greedy algorithm obtain optimal solutions, while the \((1+1)\) EA obtains the worst possible solution with constant probability. We prove that for the Dominating Set, Vertex Cover, Connected Dominating Set and Independent Set, the \((1+1)\) EA obtains constant-factor approximation in expected run time \(O(n, log(n))\) and \(O(n^4)\) respectively. Whereas, GSEMO gives even better approximation than \((1+1)\) EA in expected run time \(O(n^3)\) for Dominating Set, Vertex Cover and Connected Dominating Set on such networks.

@inproceedings{chauhan2017approximating, abstract = {It has been experimentally observed that real-world networks follow certain topologicalproperties, such as small-world, power-law etc. To study these networks, many random graph models, such as Preferential Attachment, have been proposed. In this paper, we consider the deterministic properties which capture power-law degree distribution and degeneracy. Networks with these properties are known as scale-free networks in the literature. Many interesting problems remain NP-hard on scale-free networks. We study the relationship between scale-free properties and the approximation-ratio of some commonly used evolutionary algorithms. For the Vertex Cover, we observe experimentally that the \((1+1)\) EA always gives the better result than a greedy local search, even when it runs for only \(O(n, log(n))\) steps. We give the construction of a scale-free network in which a multi-objective algorithm and a greedy algorithm obtain optimal solutions, while the \((1+1)\) EA obtains the worst possible solution with constant probability. We prove that for the Dominating Set, Vertex Cover, Connected Dominating Set and Independent Set, the \((1+1)\) EA obtains constant-factor approximation in expected run time \(O(n, log(n))\) and \(O(n^4)\) respectively. Whereas, GSEMO gives even better approximation than \((1+1)\) EA in expected run time \(O(n^3)\) for Dominating Set, Vertex Cover and Connected Dominating Set on such networks.}, added-at = {2017-09-19T19:28:50.000+0200}, author = {Chauhan, Ankit and Friedrich, Tobias and Quinzan, Francesco}, biburl = {https://www.bibsonomy.org/bibtex/2a493438e57d6fd7bd9ba21b1c2bf5bca/typo3tester}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, interhash = {fa506efbf4502898e415129b7a3c7aec}, intrahash = {a493438e57d6fd7bd9ba21b1c2bf5bca}, keywords = {testing typo3}, pages = {235-242}, timestamp = {2017-09-19T19:28:50.000+0200}, title = {Approximating Optimization Problems using EAs on Scale-Free Networks}, year = 2017 }