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

Abstract

top
A vertex i of a graph G = (V,E) is said to be controlled by M 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 V is controlled by M. Given a set M V and two graphs G1 = ( V , E 1 ) and G2 = ( V , E 2 ) where E 1 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 E 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 1 2 + 1 + n 2 n - 2 , where n=|V|>4. (The case n 4 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.

How to cite

top

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 -

References

top
  1. S. Arora and S. Safra, Probabilistic checking of proofs: A new characterization of NP. J. ACM45 (1998) 70–122.  Zbl0903.68076
  2. J.-C. Bermond and D. Peleg, The power of small coalitions in graphs. Discrete Appl. Math.127 (2003) 399–414.  Zbl1025.68061
  3. 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
  4. R.G. Downey and M.R. Fellows, Fixed parameter tractability and completeness I: Basic results. SIAM J. Comput.24 (1995) 873–921.  Zbl0830.68063
  5. D. Dubashi and D. Ranjan, Balls and bins: A study of negative dependence. Random Struct. Algorithms13 (1998) 99–124.  
  6. P. Erdös and J. Spencer, The Probabilistic Method in Combinatorics. Academic Press, San Diego (1974).  Zbl0308.05001
  7. D. Fitoussi and M. Tennenholtz, Minimal social laws. Proc. AAAI'98 (1998) 26–31.  
  8. R. Gandhi, S. Khuler, S. Parthasarathy and A. Srinivasan, Dependent rounding and its applications to approximation algorithms. J. ACM53 (2006) 324–360.  Zbl1312.68233
  9. M.C. Golumbic, H. Kaplan and R. Shamir, Graph sandwich problems. J. Algorithms19 (1994) 449–473.  Zbl0838.68054
  10. H. Kaplan and R. Shamir, Bounded degree interval sandwich problems. Algorithmica24 (1999) 96–104.  Zbl0934.68070
  11. N. Karmarkar, A new polynomial time algorithm for linear programming. Combinatorica4 (1984) 375–395.  Zbl0557.90065
  12. 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
  13. 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.  
  14. K. Makino, M. Yamashita and T. Kameda, Max-and min-neighborhood monopolies. Algorithmica34 (2002) 240–260.  Zbl1016.68057
  15. R. Motwani and P. Raghavan, Randomized Algorithms. Cambridge University Press, London, 1995.  Zbl0849.68039
  16. D. Peleg, Local majority voting, small coalitions and controlling monopolies in graphs: A review. Technical Report CS96-12, Weizmann Institute, Rehovot (1996).  
  17. P. Raghavan and C.D. Thompson, Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica7 (1987) 365–374.  Zbl0651.90052
  18. 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.  
  19. 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.  
  20. Y. Shoham and M. Tennenholtz, On the systhesis of useful social laws for artificial agent societies. Proc. AAAI'92 (1992) 276–281.  
  21. S.J. Wright, Primal-Dual Interior-Point Methods. SIAM (1997).  Zbl0863.65031
  22. M. Yannakakis, Computing the minimum fill-in is NP-complete. SIAM J. Algebr. Discrete Methods2 (1981) 77–79.  Zbl0496.68033

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.