Mixed integer programming with convexconcave constraints: Fixedparameter tractability and applications to multicovering and voting Abstract   A classic result of Lenstra Math. Oper. Res. 1983 says that an integer linear program can be solved in fixedparameter tractable (   FPT   ) time for the parameterization by the number of variables. We extend this result by incorporating piecewise linear convex or concave functions to our (mixed) integer programs. This general technique allows us to analyze the parameterized complexity of a number of classic    NP   hard computational problems. In particular, we prove that  Weighted Set Multicover  is in    FPT    when parameterized by the number of elements to cover, and that there exists an    FPT   time approximation scheme for  Multiset Multicover  for the same parameterxe2x80x94this is our most technical result. Further, we use our general technique to prove that a number of problems from computational social choice (e.g., problems related to bribery and control in elections) are in    FPT    when parameterized by the number of candidates. For bribery, this resolves a nearly 10year old family of open problems, and for weighted electoral control of Approval voting, this improves some previously known    XP   memberships to    FPT   memberships.

Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack The area of parameterized approximation seeks to combine approximation and parameterized algorithms to obtain, e.g., (1eps)approximations in f(k,eps)nO(1) time where k is some parameter of the input. We obtain the following results on parameterized approximability: 1) In the maximum independent set of rectangles problem (MISR) we are given a collection of n axis parallel rectangles in the plane. Our goal is to select a maximumcardinality subset of pairwise nonoverlapping rectangles. This problem is NPhard and also W1hard Marx, ESAu002705. The bestknown polynomialtime approximation factor is O(loglog n) Chalermsook and Chuzhoy, SODAu002709 and it admits a QPTAS Adamaszek and Wiese, FOCSu002713; Chuzhoy and Ene, FOCSu002716. Here we present a parameterized approximation scheme (PAS) for MISR, i.e. an algorithm that, for any given constant epsu003e0 and integer ku003e0, in time f(k,eps)ng(eps), either outputs a solution of size at least k(1eps), or declares that the optimum solution has size less than k. 2) In the (2dimensional) geometric knapsack problem (TDK) we are given an axisaligned square knapsack and a collection of axisaligned rectangles in the plane (items). Our goal is to translate a maximum cardinality subset of items into the knapsack so that the selected items do not overlap. In the version of TDK with rotations (TDKR), we are allowed to rotate items by 90 degrees. Both variants are NPhard, and the bestknown polynomialtime approximation factors are 558325eps and 43eps, resp. Galvez et al., FOCSu002717. These problems admit a QPTAS for polynomially bounded item sizes Adamaszek and Wiese, SODAu002715. We show that both variants are W1hard. Furthermore, we present a PAS for TDKR. For all considered problems, getting time f(k,eps)nO(1), rather than f(k,eps)ng(eps), would give FPT time fu0027(k)nO(1) exact algorithms using eps1(k1), contradicting W1hardness.