A vertex i of a graph G = (V,E) is said to be controlled by 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 is controlled by M. Given a set and two graphs G1 = () and G2 = () where , the monopoly verification problem (mvp) consists of deciding whether there exists a sandwich graph G = (V,E) (i.e., a graph where ) 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 + , where n=|V|>4. (The case 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.
Mots-clés : derandomization, Monte Carlo method, randomized rounding, sandwich problems
@article{ITA_2011__45_2_181_0, author = {Martinhon, Carlos and Protti, F\'abio}, title = {An improved derandomized approximation algorithm for the max-controlled set problem}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {181--196}, publisher = {EDP-Sciences}, volume = {45}, number = {2}, year = {2011}, doi = {10.1051/ita/2011006}, mrnumber = {2811653}, zbl = {1218.68196}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita/2011006/} }
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 - Informatique Théorique et Applications PY - 2011 SP - 181 EP - 196 VL - 45 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2011006/ DO - 10.1051/ita/2011006 LA - en ID - ITA_2011__45_2_181_0 ER -
%0 Journal Article %A Martinhon, Carlos %A Protti, Fábio %T An improved derandomized approximation algorithm for the max-controlled set problem %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2011 %P 181-196 %V 45 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2011006/ %R 10.1051/ita/2011006 %G en %F ITA_2011__45_2_181_0
Martinhon, Carlos; Protti, Fábio. An improved derandomized approximation algorithm for the max-controlled set problem. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 2, pp. 181-196. doi : 10.1051/ita/2011006. http://archive.numdam.org/articles/10.1051/ita/2011006/
[1] Probabilistic checking of proofs: A new characterization of NP. J. ACM 45 (1998) 70-122. | MR | Zbl
and ,[2] The power of small coalitions in graphs. Discrete Appl. Math. 127 (2003) 399-414. | MR | Zbl
and ,[3] An optimal algorithm for Monte Carlo estimation. SIAM J. Comput. 29 (2000) 1484-1496. | MR | Zbl
, , and ,[4] Fixed parameter tractability and completeness I: Basic results. SIAM J. Comput. 24 (1995) 873-921. | MR | Zbl
and ,[5] Balls and bins: A study of negative dependence. Random Struct. Algorithms 13 (1998) 99-124. | MR | Zbl
and ,[6] The Probabilistic Method in Combinatorics. Academic Press, San Diego (1974). | Zbl
and ,[7] Minimal social laws. Proc. AAAI'98 (1998) 26-31. | MR
and ,[8] Dependent rounding and its applications to approximation algorithms. J. ACM 53 (2006) 324-360. | MR
, , and ,[9] Graph sandwich problems. J. Algorithms 19 (1994) 449-473. | MR | Zbl
, and ,[10] Bounded degree interval sandwich problems. Algorithmica 24 (1999) 96-104. | MR | Zbl
and ,[11] A new polynomial time algorithm for linear programming. Combinatorica 4 (1984) 375-395. | MR | Zbl
,[12] 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. | MR | Zbl
,[13] Sphere packing and local majorities in graphs. Proc. 2nd Israel Symposium on Theoretical Computer Science, IEEE Computer Society Press, Rockville, MD (1993) 141-149.
, , and ,[14] Max-and min-neighborhood monopolies. Algorithmica 34 (2002) 240-260. | MR | Zbl
, and ,[15] Randomized Algorithms. Cambridge University Press, London, 1995. | MR | Zbl
and ,[16] Local majority voting, small coalitions and controlling monopolies in graphs: A review. Technical Report CS96-12, Weizmann Institute, Rehovot (1996).
,[17] Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica 7 (1987) 365-374. | MR | Zbl
and ,[18] 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. | MR | Zbl
,[19] Emergent conventions in multi-agent systems: Initial experimental results and observations. Proc. International Conference on Principles of Knowledge Representation and Reasoning (1992) 225-231.
and ,[20] On the systhesis of useful social laws for artificial agent societies. Proc. AAAI'92 (1992) 276-281.
and ,[21] Primal-Dual Interior-Point Methods. SIAM (1997). | MR | Zbl
,[22] Computing the minimum fill-in is NP-complete. SIAM J. Algebr. Discrete Methods 2 (1981) 77-79. | MR | Zbl
,Cité par Sources :