2026-07-21T14:18:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24392 2025-12-12T15:01:24Z ddc:004 open_access

Non-Adaptive Evaluation of k-of- n Functions: Tight Gap and a Unit-Cost PTAS Nielsen, Mads Anker Rohwedder, Lars Schewior, Kevin Approximation scheme Boolean functions stochastic combinatorial optimization stochastic function evaluation sequential testing adaptivity We consider the Stochastic Boolean Function Evaluation (SBFE) problem in the well-studied case of k-of-n functions: There are independent Boolean random variables x_1,… ,x_n where each variable i has a known probability p_i of taking value 1, and a known cost c_i that can be paid to find out its value. The value of the function is 1 iff there are at least k 1s among the variables. The goal is to efficiently compute a strategy that, at minimum expected cost, tests the variables until the function value is determined. While an elegant polynomial-time exact algorithm is known when tests can be made adaptively, we focus on the non-adaptive variant, for which much less is known. First, we show a clean and tight lower bound of 2 on the adaptivity gap, i.e., the worst-case multiplicative loss in the objective function caused by disallowing adaptivity, of the problem. This improves the tight lower bound of 3/2 for the unit-cost variant. Second, we give a PTAS for computing the best non-adaptive strategy in the unit-cost case, the first PTAS for an SBFE problem. At the core, our scheme establishes a novel notion of two-sided dominance (w.r.t. the optimal solution) by guessing so-called milestone tests for a set of carefully chosen buckets of tests. To turn this technique into a polynomial-time algorithm, we use a decomposition approach paired with a random-shift argument. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mads Anker Nielsen and Lars Rohwedder and Kevin Schewior 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.26 urn:nbn:de:0030-drops-243920 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.26 eng https://creativecommons.org/licenses/by/4.0/legalcode