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

Carlos Martinhon; Fábio Protti

RAIRO - Theoretical Informatics and Applications (2011)

- Volume: 45, Issue: 2, page 181-196
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topMartinhon, 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 -

## References

top- S. Arora and S. Safra, Probabilistic checking of proofs: A new characterization of NP. J. ACM45 (1998) 70–122. Zbl0903.68076
- J.-C. Bermond and D. Peleg, The power of small coalitions in graphs. Discrete Appl. Math.127 (2003) 399–414. Zbl1025.68061
- P. Dagum, R. Karp, M. Luby and S. Ross, An optimal algorithm for Monte Carlo estimation. SIAM J. Comput.29 (2000) 1484–1496. Zbl1112.65300
- R.G. Downey and M.R. Fellows, Fixed parameter tractability and completeness I: Basic results. SIAM J. Comput.24 (1995) 873–921. Zbl0830.68063
- D. Dubashi and D. Ranjan, Balls and bins: A study of negative dependence. Random Struct. Algorithms13 (1998) 99–124.
- P. Erdös and J. Spencer, The Probabilistic Method in Combinatorics. Academic Press, San Diego (1974). Zbl0308.05001
- D. Fitoussi and M. Tennenholtz, Minimal social laws. Proc. AAAI'98 (1998) 26–31.
- R. Gandhi, S. Khuler, S. Parthasarathy and A. Srinivasan, Dependent rounding and its applications to approximation algorithms. J. ACM53 (2006) 324–360. Zbl1312.68233
- M.C. Golumbic, H. Kaplan and R. Shamir, Graph sandwich problems. J. Algorithms19 (1994) 449–473. Zbl0838.68054
- H. Kaplan and R. Shamir, Bounded degree interval sandwich problems. Algorithmica24 (1999) 96–104. Zbl0934.68070
- N. Karmarkar, A new polynomial time algorithm for linear programming. Combinatorica4 (1984) 375–395. Zbl0557.90065
- S. Khot, On the power of unique 2-prover 1-round games, in STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, NY, USA, ACM Press (2002) 767–775. Zbl1192.68367
- N. Linial, D. Peleg, Y. Rabinovich and N. Saks, Sphere packing and local majorities in graphs. Proc. 2nd Israel Symposium on Theoretical Computer Science, IEEE Computer Society Press, Rockville, MD (1993) 141–149.
- K. Makino, M. Yamashita and T. Kameda, Max-and min-neighborhood monopolies. Algorithmica34 (2002) 240–260. Zbl1016.68057
- R. Motwani and P. Raghavan, Randomized Algorithms. Cambridge University Press, London, 1995. Zbl0849.68039
- D. Peleg, Local majority voting, small coalitions and controlling monopolies in graphs: A review. Technical Report CS96-12, Weizmann Institute, Rehovot (1996).
- P. Raghavan and C.D. Thompson, Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica7 (1987) 365–374. Zbl0651.90052
- J.D. Rose, A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, in Graph Theory and Computing, edited by R.C. Reed, Academic Press, New York (1972) 183–217.
- Y. Shoham and M. Tennenholtz, Emergent conventions in multi-agent systems: Initial experimental results and observations. Proc. International Conference on Principles of Knowledge Representation and Reasoning (1992) 225–231.
- Y. Shoham and M. Tennenholtz, On the systhesis of useful social laws for artificial agent societies. Proc. AAAI'92 (1992) 276–281.
- S.J. Wright, Primal-Dual Interior-Point Methods. SIAM (1997). Zbl0863.65031
- M. Yannakakis, Computing the minimum fill-in is NP-complete. SIAM J. Algebr. Discrete Methods2 (1981) 77–79. Zbl0496.68033

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.