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

DOI10.1051/ita/2011006zbMath1218.68196OpenAlexW2960420609MaRDI QIDQ5198931

Fábio Protti, Carlos A. Martinhon

Publication date: 10 August 2011

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2011__45_2_181_0/

zbMATH Keywords

Monte Carlo methodderandomizationrandomized roundingsandwich problems

Mathematics Subject Classification ID

Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Bounded degree interval sandwich problems
• The power of small coalitions in graphs
• Max- and Min-neighborhood monopolies
• Dependent rounding and its applications to approximation algorithms
• On the power of unique 2-prover 1-round games
• Probabilistic checking of proofs
• Computing the Minimum Fill-In is NP-Complete
• Balls and bins: A study in negative dependence
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Graph Sandwich Problems
• An Optimal Algorithm for Monte Carlo Estimation

This page was built for publication: An improved derandomized approximation algorithm for the max-controlled set problem