Name
Title | ||
|---|---|---|
Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets |
Abstract | ||
|---|---|---|
In this work, we study the well-known r-DIMENSIONAL k-MATCHING ((r, k)-DM), and r-SET k-PACKING ((r, k)-SP) problems. Given a universe U := U-1 ... U-r and an r-uniform family F subset of U-1 x ... x U-r, the (r, k)-DM problem asks if F admits a collection of k mutually disjoint sets. Given a universe U and an r-uniform family F subset of 2(U), the (r, k)-SP problem asks if F admits a collection of k mutually disjoint sets. We employ techniques based on dynamic programming and representative families. This leads to a deterministic algorithm with running time O(2.851((r-1)k) .vertical bar F vertical bar. n log(2)n . logW) for the weighted version of (r, k)-DM, where W is the maximum weight in the input, and a deterministic algorithm with running time O(2.851((r-0.5501)k).vertical bar F vertical bar.n log(2) n . logW) for the weighted version of (r, k)-SP. Thus, we significantly improve the previous best known deterministic running times for (r, k)-DM and (r, k)-SP and the previous best known running times for their weighted versions. We rely on structural properties of (r, k)-DM and (r, k)-SP to develop algorithms that are faster than those that can be obtained by a standard use of representative sets. Incorporating the principles of iterative expansion, we obtain a better algorithm for (3, k)-DM, running in time O(2.004(3k).vertical bar F vertical bar . n log(2)n). We believe that this algorithm demonstrates an interesting application of representative families in conjunction with more traditional techniques. Furthermore, we present kernels of size O(e(r)r(k-1)(r) logW) for the weighted versions of (r, k)-DM and (r, k)-SP, improving the previous best known kernels of size O(r!r(k-1)(r) logW) for these problems. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1137/140981290 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
r-dimensional matching,set packing,3D-matching,fixed-parameter algorithms,representative sets,iterative expansion | Discrete mathematics,Combinatorics,Disjoint sets,Packing problems,Set packing,Deterministic algorithm,3-dimensional matching,Mathematics | Journal |
Volume | Issue | ISSN |
29 | 4 | 0895-4801 |
Citations | PageRank | References |
3 | 0.37 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Prachi Goyal | 1 | 9 | 1.52 |
| Neeldhara Misra | 2 | 341 | 31.42 |
| Fahad Panolan | 3 | 112 | 23.04 |
| Meirav Zehavi | 4 | 119 | 48.69 |