An improved derandomized approximation algorithm for the max-controlled set problem

Martinhon, Carlos, and Protti, Fábio. "An improved derandomized approximation algorithm for the max-controlled set problem." RAIRO - Theoretical Informatics and Applications 45.2 (2011): 181-196. <http://eudml.org/doc/276341>.

@article{Martinhon2011,
abstract = { A vertex i of a graph G = (V,E) is said to be controlled by $M \subseteq V$ if the majority of the elements of the neighborhood of i (including itself) belong to M. The set M is a monopoly in G if every vertex $i\in V$ is controlled by M. Given a set $M \subseteq V$ and two graphs G1 = ($V,E_1$) and G2 = ($V,E_2$) where $E_1\subseteq E_2$, the monopoly verification problem (mvp) consists of deciding whether there exists a sandwich graph G = (V,E) (i.e., a graph where $E_1\subseteq E\subseteq E_2$) such that M is a monopoly in G = (V,E). If the answer to the mvp is No, we then consider the max-controlled set problem (mcsp), whose objective is to find a sandwich graph G = (V,E) such that the number of vertices of G controlled by M is maximized. The mvp can be solved in polynomial time; the mcsp, however, is NP-hard. In this work, we present a deterministic polynomial time approximation algorithm for the mcsp with ratio $\frac\{1\}\{2\}$ + $\frac\{1+\sqrt\{n\}\}\{2n-2\}$, where n=|V|>4. (The case $n\leq4$ is solved exactly by considering the parameterized version of the mcsp.) The algorithm is obtained through the use of randomized rounding and derandomization techniques based on the method of conditional expectations. Additionally, we show how to improve this ratio if good estimates of expectation are obtained in advance. },
author = {Martinhon, Carlos, Protti, Fábio},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Derandomization; Monte Carlo method; Randomized rounding; sandwich problems; derandomization; randomized rounding},
language = {eng},
month = {6},
number = {2},
pages = {181-196},
publisher = {EDP Sciences},
title = {An improved derandomized approximation algorithm for the max-controlled set problem},
url = {http://eudml.org/doc/276341},
volume = {45},
year = {2011},
}

TY - JOUR
AU - Martinhon, Carlos
AU - Protti, Fábio
TI - An improved derandomized approximation algorithm for the max-controlled set problem
JO - RAIRO - Theoretical Informatics and Applications
DA - 2011/6//
PB - EDP Sciences
VL - 45
IS - 2
SP - 181
EP - 196
AB - A vertex i of a graph G = (V,E) is said to be controlled by $M \subseteq V$ if the majority of the elements of the neighborhood of i (including itself) belong to M. The set M is a monopoly in G if every vertex $i\in V$ is controlled by M. Given a set $M \subseteq V$ and two graphs G1 = ($V,E_1$) and G2 = ($V,E_2$) where $E_1\subseteq E_2$, the monopoly verification problem (mvp) consists of deciding whether there exists a sandwich graph G = (V,E) (i.e., a graph where $E_1\subseteq E\subseteq E_2$) such that M is a monopoly in G = (V,E). If the answer to the mvp is No, we then consider the max-controlled set problem (mcsp), whose objective is to find a sandwich graph G = (V,E) such that the number of vertices of G controlled by M is maximized. The mvp can be solved in polynomial time; the mcsp, however, is NP-hard. In this work, we present a deterministic polynomial time approximation algorithm for the mcsp with ratio $\frac{1}{2}$ + $\frac{1+\sqrt{n}}{2n-2}$, where n=|V|>4. (The case $n\leq4$ is solved exactly by considering the parameterized version of the mcsp.) The algorithm is obtained through the use of randomized rounding and derandomization techniques based on the method of conditional expectations. Additionally, we show how to improve this ratio if good estimates of expectation are obtained in advance.
LA - eng
KW - Derandomization; Monte Carlo method; Randomized rounding; sandwich problems; derandomization; randomized rounding
UR - http://eudml.org/doc/276341
ER -