#	Pagina
attuale pagina	/open-h2020/projects/200702/results.html

Report

Teaser, summary, work performed and final results

Periodic Reporting for period 2 - TOTAL (Technology transfer between modern algorithmic paradigms)

Teaser

Summary

The two most recognized algorithmic paradigms of dealing with NP-hard problems in theoretical computer science nowadays are approximation algorithms and fixed parameter tractability (FPT). Despite the fact that both fields are by now developed, they have grown mostly on their own. In our opinion the two fields have critical mass allowing for synergy effects to appear when using techniques from one area to obtain results in the other, which is the main theme of the project.

Based on our experience with parameterized complexity and approximation algorithms we proposed three research directions with potential of solving major long-standing open problems in both areas with the following objectives.
(a) Transfer from Approximation to FPT: use the PCP theorem to prove lower bounds for exact parameterized algorithms under the Exponential Time Hypothesis and take advantage of extended formulations in FPT branching algorithms.
(b) Transfer from FPT to Approximation: utilize parameterized algorithms tools in local-search- based approximation algorithms and explore the potential of proving new inapproximability results based on the Exponential Time Hypothesis.
(c) Rigorous Analysis of Practical Heuristics: unravel the practical effectiveness of randomized local search heuristics by proving their parameterized and approximation properties, when given subexponential or even moderately exponential running time.

Work performed

Here we would like to highlight four results obtained in the first stage of the project.

We have combined Probabilistically Checkable Proofs (PCP) and Exponential Time Hypothesis (ETH) to obtain new lower bounds for Minimum Fill-In, Interval Completion and a few its variants. To get tight results we needed to rely on an additional conjecture on subexponential approximation of min-bisection in sparse graphs. Interestingly, a follow up of our work was published at SODA\'17 by Cao and Sandeep, where they show a new reduction which relies solely on ETH and PCP for the Minimum Fill-In problem.

In a paper published at ICALP\'17 we have performed a systematic study of the landscape of fine-grained complexity under the assumption that the (min,+)-convolution problem does not admit trully subquadratic algorithms. Conditional lower bound were obtained for knapsack and other problems.

In an article published at ESA\'17 (and awarded the Best Paper award) we have obtained faster algorithms searching through the space of all small local improvements for the travelling salesman problem (TSP). The popular k-opt heuristic for TSP finds a local optimum by starting from an arbitrary tour H and then improving it by a sequence of k-moves. Until 2016, the only known algorithm to find an improving k-move for a given tour was the naive solution in time O(n^k). At ICALP\'16 de Berg, Buchin, Jansen and Woeginger showed an O(n^{floor(2/3k)+1})-time algorithm. We have shown an algorithm which runs in O(n^{(1/4 + epsilon_k)k}) time, where lim_{k -> infinity} epsilon_k = 0.

Finally, the most important result of the project so far is our work published at FOCS\'17, where we have considered questions that arise from the intersection between the areas of approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms, that is whether there is a non-trivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In this paper, we have shown that both Clique and DomSet admit no non-trivial FPT-approximation algorithm. Our results hold under the Gap Exponential Time Hypothesis (GapETH) which states that no 2^o(n) -time algorithm can distinguish between a satisfiable 3SAT formula and one which is not even (1 - Îµ)-satisfiable for some constant Îµ > 0.

Final results

We believe that our work in the second half of the project will allow for next results published at major computer science conferences. We would like to note that for each category wrote in the proposal, we have made a substantial progress already.