RAIRO-Theor. Inf. Appl.
Volume 45, Number 2, April-June 2011
|Page(s)||181 - 196|
|Published online||28 February 2011|
An improved derandomized approximation algorithm for the max-controlled set problem
Fluminense Federal University, Institute of Computing,
Rua Passo da Pátria 156, Bloco E, 24210-230, Niterói, RJ, Brazil; email@example.com; firstname.lastname@example.org
Accepted: 4 October 2010
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.
Mathematics Subject Classification: 68W20 / 68W25
Key words: Derandomization / Monte Carlo method / Randomized rounding / sandwich problems
© EDP Sciences, 2011
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.