Deterministic versus randomized adaptive test cover

DOI10.1016/j.tcs.2016.09.019zbMath1353.68257MaRDI QIDQ329717

Peter Damaschke

Publication date: 21 October 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.09.019

zbMATH Keywords

game theory; randomization; set cover; combinatorial search; fractional graph theory; LP duality

Mathematics Subject Classification ID

05C65: Hypergraphs

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68W20: Randomized algorithms

05C72: Fractional graph theory, fuzzy graph theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterizations of test cover with bounded test sizes
• Rounds in combinatorial search
• Approximation algorithms for the test cover problem
• Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
• (Non-)existence of polynomial kernels for the test cover problem
• A new randomized algorithm for group testing with unknown number of defective items
• Parameterized Study of the Test Cover Problem
• Partially Polynomial Kernels for Set Cover and Test Cover
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A Tighter Analysis of Set Cover Greedy Algorithm for Test Set
• A Greedy Heuristic for the Set-Covering Problem
• Non-approximability results for optimization problems on bounded degree instances
• Group Testing With Probabilistic Tests: Theory, Design and Application
• Group Testing With Random Pools: Optimal Two-Stage Algorithms
• Paths, Trees, and Flowers
• A Parameterized Perspective on Packing Paths of Length Two