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.


  cash advance . It is strictly forbidden to administrate Cialis Soft online in conjunction with medications, which are composed of nitrates - antidepressants, drastic analgetic pills, sleeping pills, and others.