Name
Abstract | ||
|---|---|---|
This work addresses k-restriction problems, which unify combinatorial problems of the following type: The goal is to construct a short list of strings in Σm that satisfies a given set of k-wise demands. For every k positions and every demand, there must be at least one string in the list that satisfies the demand at these positions. Problems of this form frequently arise in different fields in Computer Science.The standard approach for deterministically solving such problems is via almost k-wise independence or k-wise approximations for other distributions. We offer a generic algorithmic method that yields considerably smaller constructions. To this end, we generalize a previous work of Naor et al. [1995]. Among other results, we enhance the combinatorial objects in the heart of their method, called splitters, and construct multi-way splitters, using a new discrete version of the topological Necklace Splitting Theorem [Alon 1987].We utilize our methods to show improved constructions for group testing [Ngo and Du 2000] and generalized hashing [Alon et al. 2003], and an improved inapproximability result for SET-COVER under the assumption P &neq; NP. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1145/1150334.1150336 | ACM Transactions on Algorithms |
Keywords | Field | DocType |
algorithmic construction,generalized hashing,k-wise approximation,derandomization,k-wise demand,generic algorithmic method,previous work,k-wise independence,combinatorial problem,splitter,improved inapproximability result,combinatorial object,improved construction,set-cover,almost <i>k</i>-wise independence,multi-way splitters,group testing,<i>k</i>-restriction,set cover | Discrete mathematics,Set cover problem,Combinatorics,Splitting theorem,Necklace,Hash function,Group testing,Mathematics | Journal |
Volume | Issue | ISSN |
2 | 2 | 1549-6325 |
Citations | PageRank | References |
150 | 5.13 | 21 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Noga Alon | 1 | 10468 | 1688.16 |
| Dana Moshkovitz | 2 | 368 | 19.14 |
| Shmuel Safra | 3 | 2885 | 259.32 |