Algorithmic construction of sets for k-restrictions

No abstract is available for this paper.

• Publication year

  2006

• Venue

  TALG

• Publication date

  2006-04-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1150334.1150336
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Generalized hashing and parent-identifying codes

  2003influential reference
• Splitting Necklaces

  2003influential reference
• Improved Approximation Guarantees for Packing and Covering Integer Programs

  1999cited by this paper
• PCP characterizations of NP: towards a polynomially-small error-probability

  1999influential reference
• Efficient approximation of product distributions

  1998cited by this paper
• Probabilistic checking of proofs: a new characterization of NP

  1998cited by this paper
• A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP

  1997cited by this paper
• Improved Low-Degree Testing and its Applications

  1997influential reference
• A threshold of ln n for approximating set cover (preliminary version)

  1996cited by this paper
• A tight analysis of the greedy algorithm for set cover

  1996cited by this paper
• A Sub-constant Error-probability Pcp Characterization of Np Part Ii: the Consistency Test

  1996influential reference
• Color-coding

  1995cited by this paper
• Splitters and near-optimal derandomization

  1995cited by this paper
• On the hardness of approximating minimization problems

  1994cited by this paper
• Constructing small sample spaces satisfying given constraints

  1993cited by this paper
• Combinatorial Group Testing and Its Applications

  1993cited by this paper
• Efficient probabilistically checkable proofs and applications to approximations

  1993cited by this paper
• Simple Construction of Almost k-wise Independent Random Variables

  1992influential reference
• Construction Of Asymptotically Good Low-rate Error-correcting Codes Through Pseudo-random Graphs

  1991influential reference
• Graph Algorithms

  1991cited by this paper
• Small-bias probability spaces: efficient constructions and applications

  1990influential reference
• On the ratio of optimal integral and fractional covers

  1975cited by this paper
• The complexity of theorem-proving procedures

  1971influential reference
• DIMACS Series in Discrete Mathematics and Theoretical Computer Science A Survey on Combinatorial Group Testing Algorithms with Applications to DNA Library Screening

  year unknowncited by this paper

• Disjoint dominating and 2-dominating sets in graphs: Hardness and approximation results

  2025cites this paper
• Matching and Edge Cover in Temporal Graphs

  2025cites this paper
• Non-iterative sparse signal recovery algorithms for sparse matrices and their guarantees

  2025cites this paper
• Application-Aware Real-Time Network Resource Allocation for Industry 5.0

  2025cites this paper
• On Average Baby PIH and Its Applications

  2025cites this paper
• Hardness of SetCover Reoptimization

  2025cites this paper
• Connected k-Median with Disjoint and Non-disjoint Clusters

  2025cites this paper
• On the complexity of temporal arborescence reconfiguration

  2025cites this paper
• Fast and Optimal Extraction for Sparse Equality Graphs

  2024cites this paper
• A note on the k-restriction problem

  2024cites this paper
• Fair Submodular Cover

  2024cites this paper
• Online Multiset Submodular Cover

  2024cites this paper
• Efficient Unsupervised Community Search with Pre-trained Graph Transformer

  2024cites this paper
• Efficient Greedy Algorithms with Accuracy Guarantees for Combinatorial Restrictions

  2024cites this paper
• Cops and robber on variants of retracts and subdivisions of oriented graphs

  2023cites this paper
• Dynamic Obstacles Tracking in mmWave Networks

  2023cites this paper
• Disjoint Dominating and 2-Dominating Sets in Graphs: Hardness and Approximation results

  2023cites this paper
• MONA: An Efficient and Scalable Strategy for Targeted k-Nodes Collapse

  2023cites this paper
• Chemical Reaction Optimization for Minimum Weight Dominating Set

  2023cites this paper
• Designing a Large Scale Autonomous Observing Network: A Set Theory Approach

  2022cites this paper
• NuSC: An Effective Local Search Algorithm for Solving the Set Covering Problem

  2022cites this paper
• Data-Driven Beamforming Codebook Design to Improve Coverage in Millimeter Wave Networks

  2022cites this paper
• Group Testing on General Set-Systems

  2022cites this paper
• Optimal Las Vegas Approximate Near Neighbors in ℓp

  2022cites this paper
• A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Science in THE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES

  2022cites this paper
• A Transfer Function Design Using A Knowledge Database based on Deep Image and Primitive Intensity Profile Features Retrieval

  2022cites this paper
• Constant Approximating Parameterized k-SetCover is W[2]-hard

  2022cites this paper
• splitting of colored paths.

  2022cites this paper
• Minimizing Congestion for Balanced Dominators

  2021cites this paper
• Lower Bounds on Approximability Via PCP and Gap Reductions

  2021cites this paper
• Spy Game: FPT-Algorithm and Results on Graph Products

  2021cites this paper
• Online Budgeted Maximum Coverage

  2021cites this paper
• Preference-Based Trajectory Clustering - An Application of Geometric Hitting Sets

  2021cites this paper
• 1 Basic Lower Bounds on Approximability Via PCP and Gap Reductions 2

  2021cites this paper
• 1 Basic Lower Bounds on Approximability Via PCP and Gap Reductions 2

  2021cites this paper
• Basic Lower Bounds on Approximability Via PCP and Gap Reductions

  2021cites this paper
• On the Approximability of Multistage Min-Sum Set Cover

  2021cites this paper
• Algorithms, hardness and graph products on a pursuit-evasion game

  2021cites this paper
• Efficient Splitting of Necklaces

  2021cites this paper
• Searching, Sorting, and Cake Cutting in Rounds

  2020cites this paper
• $O_n$ is an $n$-MCFL

  2020cites this paper
• Shake It! Detecting Flaky Tests Caused by Concurrency with Shaker

  2020cites this paper
• Metaheuristics for the Minimum Set Cover Problem: A Comparison

  2020cites this paper
• Perfect Hash Families: The Generalization to Higher Indices

  2020cites this paper
• Approximation in (Poly-) Logarithmic Space

  2020cites this paper
• Deterministic Replacement Path Covering

  2020cites this paper
• Efficient Splitting of Measures and Necklaces

  2020cites this paper
• Size-Relaxed Committee Selection under the Chamberlin-Courant Rule

  2020cites this paper
• The Optimal Design of Low-Latency Virtual Backbones

  2020influential citation
• New Directions in Streaming Algorithms

  2020cites this paper
• Bounds on upper transversals in hypergraphs

  2020cites this paper
• Weighted lambda superstrings applied to vaccine design

  2019cites this paper
• Improved Local Computation Algorithm for Set Cover via Sparsification

  2019cites this paper
• Towards Next Generation Networks with SDN and NFV

  2019cites this paper
• On the Cover Problem for Coded Caching in Wireless Networks via Deep Neural Network

  2019cites this paper
• Optimal Las Vegas Approximate Near Neighbors in l_p

  2019cites this paper
• The Inapproximability of k-DominatingSet for Parameterized \mathsf AC^0 AC 0 Circuits

  2019cites this paper
• openPrimeR for multiplex amplification of highly diverse templates

  2019cites this paper
• Approximation and Hardness: Beyond P and NP

  2019cites this paper
• Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)

  2019cites this paper
• On the Parameterized Complexity of Approximating Dominating Set

  2019cites this paper
• Bounds on upper transversals in hypergraphs

  2019cites this paper
• Deterministic Constructions of High-Dimensional Sets with Small Dispersion

  2019influential citation
• Optimal Set Similarity Data-structures Without False Negatives IT University of Copenhagen

  2019influential citation
• The Inapproximability of k-DominatingSet for Parameterized AC 0 Circuits †

  2019cites this paper
• Splitting Necklaces, with Constraints

  2019cites this paper
• Domination and identification games in graphs

  2019cites this paper
• A Simple Gap-producing Reduction for the Parameterized Set Cover Problem

  2019cites this paper
• On interval and circular-arc covering problems

  2018cites this paper
• Set Cover in Sub-linear Time

  2018cites this paper
• Covering arrays for some equivalence classes of words

  2018cites this paper
• A Binary Particle Swarm Optimization for the Minimum Weight Dominating Set Problem

  2018cites this paper
• On is an n-MCFL

  2018cites this paper
• Multi-Commodity Flow with In-Network Processing

  2018cites this paper
• Provably Efficient Algorithms for Placement of Service Function Chains with Ordering Constraints

  2018cites this paper
• Resource allocation and decision making for groups

  2018cites this paper
• Optimal Dependability and Fine Granular Error Resilience Methodology for Reconfigurable Systems

  2018cites this paper
• Optimal Las Vegas Approximate Near Neighbors in 𝓁p

  2018cites this paper
• Shortest path queries, graph partitioning and covering problems in worst and beyond worst case settings

  2018cites this paper
• Towards Fast Computation of Certified Robustness for ReLU Networks

  2018cites this paper
• On the Minimum Copy Number Generation Problem in Cancer Genomics

  2018cites this paper
• The complexity of speedrunning video games

  2018cites this paper
• Scheduling on (Un-)Related Machines with Setup Times

  2018cites this paper
• Fractional Set Cover in the Streaming Model

  2017cites this paper
• Exact Learning from an Honest Teacher That Answers Membership Queries

  2017cites this paper
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg

  2017cites this paper
• Charging Distributed Sensor Nodes Exploiting Clustering and Energy Trading

  2017cites this paper
• Improved Distributed Algorithms for Fundamental Graph Problems

  2017cites this paper
• Sublinear algorithms for massive data problems

  2017cites this paper
• Optimal Las Vegas Locality Sensitive Data Structures

  2017cites this paper
• Spy-game on graphs: Complexity and simple topologies

  2017cites this paper
• Optimizing Analytical Depth and Cost Efficiency of IEF-LC/MS Proteomics

  2017cites this paper
• Controllability of complex networks with unilateral inputs

  2017cites this paper
• Boolean Tensor Decomposition for Conjunctive Queries with Negation

  2017cites this paper
• Sparse Combinatorial Group Testing for Low-Energy Massive Random Access

  2017cites this paper
• On the parameterized complexity of approximating dominating set

  2017cites this paper
• Distributed Domination on Graph Classes of Bounded Expansion

  2017cites this paper
• Fair Splitting of Colored Paths

  2017cites this paper
• On Efficient Deployment of Wireless Sensors for Coverage and Connectivity in Constrained 3D Space

  2017cites this paper
• Approximation Algorithms for Schema-Mapping Discovery from Data Examples

  2017cites this paper