## Contributed Session Thu.1.H 3010

#### Thursday, 10:30 - 12:00 h, Room: H 3010

**Cluster 1: Approximation & online algorithms** [...]

### Approximation algorithms

**Chair: Naonori Kakimura**

**Thursday, 10:30 - 10:55 h, Room: H 3010, Talk 1**

**David P. Williamson**

A dual-fitting *3⁄2*-approximation algorithm for some minimum-cost graph problems

**Coauthor: James M. Davis**

**Abstract:**

In a recent paper, Couëtoux gives a beautiful *3⁄2*-approximation algorithm to the problem of finding a minimum-cost set of edges such that each connected components has at least *k* vertices in it. The algorithm improved on previous 2-approximation algorithms for the problem. In this paper, we show how to reinterpret Couëtoux's analysis as dual-fitting and also show how to generalize the algorithm to a broader class of graph problems previously considered in the literature.

**Thursday, 11:00 - 11:25 h, Room: H 3010, Talk 2**

**Stavros Kolliopoulos**

Planar disjoint-paths completion

**Coauthors: Isolde Adler, Dimitrios Thilikos**

**Abstract:**

Take any graph property represented by a collection *P* of graphs. The corresponding completion problem asks typically for the minimum number of edges to add to a graph so that it belongs to *P.* Several such problems have been studied in the literature.

We introduce the completion version of Disjoint Paths on planar graphs. Given a plane graph *G,* *k* pairs of terminals, and a face *F* of *G,* find the minimum set of edges, if one exists, to be added inside *F* so that: the embedding remains planar and the pairs become connected by *k* disjoint paths in the augmented network.

We give an explicit upper bound on the number of additional edges needed if a solution exists. This bound is a function of *k,* independent of the size *n* of *G.* Second, we show that the problem is fixed-parameter tractable, i.e., it can be solved in time *f(k)poly(n).*

**Thursday, 11:30 - 11:55 h, Room: H 3010, Talk 3**

**Naonori Kakimura**

Computing knapsack solutions with cardinality robustness

**Coauthors: Kazuhisa Makino, Kento Seimi**

**Abstract:**

In this paper, we study the robustness over the cardinality variation for the knapsack problem. For the knapsack problem and a positive number *α ≤ 1*, we say that a feasible solution is *α*-robust if, for any positive integer *k*, it includes an *α*-approximation of the maximum *k*-knapsack solution, where a *k*-knapsack solution is a feasible solution that consists of at most *k* items. In this talk, we show that, for any *ε >0*, the problem of deciding whether the knapsack problem admits a *( ν +ε)*-robust solution is weakly NP-hard, where * ν * denotes the rank quotient of the corresponding knapsack system. Since the knapsack problem always admits a * ν *-robust knapsack solution, this result provides a sharp border for the complexity of the robust knapsack problem. On the positive side, we show that a max-robust knapsack solution can be computed in pseudo-polynomial time, and present a fully polynomial-time approximation scheme(FPTAS) for computing a max-robust knapsack solution.