Algorithmic construction of sets for k -restrictions
From MaRDI portal
Publication:2944511
DOI10.1145/1150334.1150336zbMath1321.68445OpenAlexW2126479983WikidataQ56443115 ScholiaQ56443115MaRDI QIDQ2944511
Shmuel Safra, Dana Moshkovitz, Noga Alon
Publication date: 2 September 2015
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1150334.1150336
Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items (77)
\(O_n\) is an \(n\)-MCFL ⋮ (Total) vector domination for graphs with bounded branchwidth ⋮ A note on systems with max-min and max-product constraints ⋮ Give-and-take based peer-to-peer content distribution networks ⋮ Polytopal complexes: maps, chain complexes and… necklaces ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Tracing a single user ⋮ Deterministic constructions of high-dimensional sets with small dispersion ⋮ The \(k\)-hop connected dominating set problem: hardness and polyhedra ⋮ Towards the price of leasing online ⋮ Probabilistic distributed algorithms for energy efficient routing and tracking in wireless sensor networks ⋮ Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem ⋮ Fair splitting of colored paths ⋮ The complexity of speedrunning video games ⋮ Randomized Online Algorithms for Set Cover Leasing Problems ⋮ PTAS for the minimum weighted dominating set in growth bounded graphs ⋮ Linear Time Constructions of Some $$d$$-Restriction Problems ⋮ The \(l\)-diversity problem: tractability and approximability ⋮ Spy game: FPT-algorithm, hardness and graph products ⋮ Non-adaptive complex group testing with multiple positive sets ⋮ The complexity of minimum convex coloring ⋮ Removing local extrema from imprecise terrains ⋮ On the approximation ability of evolutionary optimization with application to minimum set cover ⋮ Observation strategies for event detection with incidence on runtime verification: theory, algorithms, experimentation ⋮ Minimize the maximum duty in multi-interface networks ⋮ Maximum subset intersection ⋮ On the approximability of covering points by lines and related problems ⋮ Fair Division and Generalizations of Sperner- and KKM-type Results ⋮ Spy game: FPT-algorithm and results on graph products ⋮ Non-adaptive learning of a hidden hypergraph ⋮ Explicit constructions of centrally symmetric \(k\)-neighborly polytopes and large strictly antipodal sets ⋮ Simplotopal maps and necklace splitting ⋮ Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs ⋮ Hardness and inapproximability of convex recoloring problems ⋮ Manipulation in Games ⋮ Circulant graphs and GCD and LCM of subsets ⋮ The Constant Inapproximability of the Parameterized Dominating Set Problem ⋮ Efficient sensor network design for continuous monitoring of moving objects ⋮ Fractional Set Cover in the Streaming Model. ⋮ The Optimal Design of Low-Latency Virtual Backbones ⋮ A new strongly competitive group testing algorithm with small sequentiality ⋮ Online budgeted maximum coverage ⋮ Spy-game on graphs: complexity and simple topologies ⋮ Towards flexible demands in online leasing problems ⋮ Face-guarding polyhedra ⋮ Randomized Post-optimization for t-Restrictions ⋮ Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs ⋮ Mobile facility location: combinatorial filtering via weighted occupancy ⋮ Non-cooperative facility location and covering games ⋮ Computing solutions of the paintshop-necklace problem ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ Video distribution under multiple constraints ⋮ A \(\Theta (\log n)\)-approximation for the set cover problem with set ownership ⋮ New results on optimizing rooted triplets consistency ⋮ Approximability and inapproximability of the minimum certificate dispersal problem ⋮ Unnamed Item ⋮ Approximation algorithms for the transportation problem with market choice and related models ⋮ An approximation algorithm for the partial vertex cover problem in hypergraphs ⋮ Approximation in (Poly-) logarithmic space ⋮ Approximating Minimum Reset Sequences ⋮ Bounds on upper transversals in hypergraphs ⋮ On the Approximability of Combinatorial Exchange Problems ⋮ A randomised approximation algorithm for the hitting set problem ⋮ Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences ⋮ Approximation in (Poly-) Logarithmic Space ⋮ A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem ⋮ On the approximability of the maximum agreement subtree and maximum compatible tree problems ⋮ Non-adaptive Learning of a Hidden Hypergraph ⋮ Computing a small agreeable set of indivisible items ⋮ Approximation and heuristic algorithms for computing backbones in asymmetric ad-hoc networks ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Splitting Necklaces, with Constraints ⋮ On interval and circular-arc covering problems ⋮ Complexities of Some Problems Related to Synchronizing, Non-Synchronizing and Monotonic Automata ⋮ A combinatorial approach to the design of vaccines ⋮ Reprint of: Face-guarding polyhedra ⋮ On connected dominating sets of restricted diameter
This page was built for publication: Algorithmic construction of sets for k -restrictions
