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


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



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


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.


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.