Journal
PROCEEDINGS OF THE TWENTY-EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS
Volume -, Issue -, Pages 2254-2263Publisher
ASSOC COMPUTING MACHINERY
Keywords
-
Funding
- Israel Science Foundation [635/16]
- Shulamit Aloni Post-Doctoral fellowship of the Israeli Ministry of Science
- Kreitman Foundation Post-Doctoral fellowship
- Swiss National Science Foundation [200020-162884, 200021-165977]
- Swiss National Science Foundation (SNF) [200021_165977, 200020_162884] Funding Source: Swiss National Science Foundation (SNF)
Ask authors/readers for more resources
Let HDd(p, q) denote the minimal size of a transversal that can always be guaranteed for a family of compact convex sets in R-d which satisfy the (p, q)-property (p >= q >= d + 1). In a celebrated proof of the Hadwiger-Debrunner conjecture, Alon and Kleitman proved that HDd(p, q) exists for all p >= q >= d + 1. Specifically, they prove that HDd(p, d + 1) is (O) over tilde (p(d2) (+) (d)). This paper has two parts. In the first part we present several improved bounds on HDd(p, q). In particular, we obtain the first near tight estimate of HDd(p, q) for an extended range of values of (p, q) since the 1957 Hadwiger-Debrunner theorem. In the second part we prove a (p, 2)-theorem for families in R-2 with union complexity below a specific quadratic bound. Based on this, we introduce a polynomial time constant factor approximation algorithm for MAX-CLIQUE of intersection graphs of convex sets satisfying this property. It is not likely that our constant factor approximation can be improved to a PTAS as MAX-CLIQUE for intersection graphs of fat ellipses is known to be APX-HARD and fat ellipses have sub-quadratic union complexity.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available