Cover Image

Non-Adaptive Evaluation of $k$-of-$n$ Functions: Tight Gap and a Unit-Cost PTAS

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Nielsen, Mads Anker, Rohwedder, Lars, Schewior, Kevin
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Combinatorial Perpetual Scheduling: Existence and Computation of Low-Height Schedules
by: Mendoza-Cadena, Mirabel, et al.
Published: (2026)

ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines
by: Rohwedder, Lars
Published: (2025)

Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling
by: Rohwedder, Lars, et al.
Published: (2024)

A k-swap Local Search for Makespan Scheduling
by: Rohwedder, Lars, et al.
Published: (2024)

Cost Preserving Dependent Rounding for Allocation Problems
by: Rohwedder, Lars, et al.
Published: (2025)

A Simple PTAS for Weighted $k$-means and Sensor Coverage
by: Pareek, Akash, et al.
Published: (2025)

Space-Efficient Algorithm for Integer Programming with Few Constraints
by: Rohwedder, Lars, et al.
Published: (2024)

Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting
by: Avila, Tatiana Rocha, et al.
Published: (2026)

Simple Algorithms for Stochastic Score Classification with Small Approximation Ratios
by: Plank, Benedikt M., et al.
Published: (2022)

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time
by: Armbruster, Alexander, et al.
Published: (2025)

Randomized Rounding over Dynamic Programs
by: Bamas, Etienne, et al.
Published: (2025)

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
by: Eisenbrand, Friedrich, et al.
Published: (2024)

The Submodular Santa Claus Problem
by: Bamas, Etienne, et al.
Published: (2024)

Tight Static Lower Bounds for Non-Adaptive Data Structures
by: Persiano, Giuseppe, et al.
Published: (2020)

Quickly Determining Who Won an Election
by: Hellerstein, Lisa, et al.
Published: (2024)

3.415-Approximation for Coflow Scheduling via Iterated Rounding
by: Rohwedder, Lars, et al.
Published: (2025)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
by: Rohwedder, Lars, et al.
Published: (2024)

A PTAS for Weighted Triangle-free 2-Matching
by: Bosch-Calvo, Miguel, et al.
Published: (2026)

Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation
by: Hellerstein, Lisa, et al.
Published: (2026)

Stochastic scheduling with Bernoulli-type jobs through policy stratification
by: Antoniadis, Antonios, et al.
Published: (2025)

NP-Hardness and a PTAS for the Pinwheel Problem
by: Kleinberg, Robert, et al.
Published: (2026)

Validating a PTAS for Triangle-Free 2-Matching via a Simple Decomposition Theorem
by: Kobayashi, Yusuke, et al.
Published: (2024)

Threshold Testing and Semi-Online Prophet Inequalities
by: Hoefer, Martin, et al.
Published: (2023)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
by: Bartlmae, Simon, et al.
Published: (2024)

Scheduling on a Stochastic Number of Machines
by: Buchem, Moritz, et al.
Published: (2024)

Adaptivity Gaps for Stochastic Probing with Subadditive Functions
by: Li, Jian, et al.
Published: (2025)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
by: Dai, Han, et al.
Published: (2025)

Designing Exploration Contracts
by: Hoefer, Martin, et al.
Published: (2024)

Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts
by: Fischer, Nick, et al.
Published: (2026)

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Mömke, Tobias, et al.
Published: (2024)

A PTAS for Travelling Salesman Problem with Neighbourhoods Over Parallel Line Segments of Similar Length
by: Ghaseminia, Benyamin, et al.
Published: (2025)

An $O(n\log n)$ Algorithm for Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices
by: Papadopoulos, Kleitos
Published: (2025)

Submodular Ground-Set Pruning: Monotone Tightness and a Non-Monotone Separation
by: Kuhnle, Alan
Published: (2026)

Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms
by: Geng, Yutong, et al.
Published: (2025)

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
by: An, Shinwoo, et al.
Published: (2024)

Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
by: Larsen, Kasper Green, et al.
Published: (2023)

Distributionally Robust $k$-of-$n$ Sequential Testing
by: Tan, Rayen, et al.
Published: (2026)

One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
by: Cohen, Edith, et al.
Published: (2024)

Multiplicative assignment with upgrades
by: Armbruster, Alexander, et al.
Published: (2025)

Stochastic Knapsack: Semi-Adaptivity Gaps and Improved Approximation
by: Barak, Zohar, et al.
Published: (2026)