On the Inapproximability of Maximum Root-free Subset Problems with Polynomial Constraints
- LecturerMr. Meng-Tsung Tsai (Ph.D. Candidate, Rutgers University)
Host: Kai-Min Chung - Time2015-12-18 (Fri.) 14:00 ~ 16:00
- LocationAuditorium 126 at CITI Building
Abstract
We study the Maximum Root-Free Subset Problem Mrfs(F) for an r-ary function F(x1, x2, . . . , xr), which is defined as: given a set S of integers, find a maximum cardinality subset T of S such that for every r distinct integers a1, a2, . . . , ar in T, F(a1, a2, . . . , ar) [@BackSlash]ne 0. We show that if the function F is a homogeneous, 3+-variate, and linear polynomial, then Mrfs(F) has no PTAS unless P = NP. We generalize and extend these results by showing the same
inapproximability result applies to conjunctions and disjunctions of linear polynomials, under certain technical conditions. Many problems can be encoded as such an inapproximable Mrfs(F). These include: problems that were not known to be NP-hard, such as Max-3-Sum and Max-3-AP; problems that were known to be NP-hard, but for which no inapproximability results were known, such as Max-k-Cycle-Free-Subgraph for every fixed k ≥3; and problems that where known to have no PTASs, but for which no concrete inapproximability constant was known, such as Max-Sidon. Our result provides improved bounds on all these problems.