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.


  The majority of financial loan companies provide the service of getting North Carolina Payday Loans for U.S. citizens. Since its introduction in the market buying Generic Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.