Deterministic versus randomized adaptive test cover

DOI10.1016/j.tcs.2016.09.019zbMath1353.68257OpenAlexW2528667811MaRDI 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 theoryrandomizationset covercombinatorial searchfractional graph theoryLP duality

Mathematics Subject Classification ID

Hypergraphs (05C65) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20) Fractional graph theory, fuzzy graph theory (05C72)

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