Publications related to Polynomial-time approximation scheme

Sorting signed permutations by inversions in O(nlogn) time

Bernard Moret, Yu Lin, Vaibhav Rajan, Krister Swenson

The study of genomic inversions (or reversals) has been a mainstay of computational genomics for nearly 20 years. After the initial breakthrough of Hannenhalli and Pevzner, who gave the first polynomial-time algorithm for sorting signed permutations by inv ...

2010

k-Edge-Connectivity: Approximation and LP Relaxation

David Pritchard

This paper's focus is the following family of problems, denoted k-ECSS, where k denotes a positive integer: given a graph (V, E) and costs for each edge, find a minimum-cost subset F of E such that (V, F) is k-edge-connected. For k=1 it is the spanning tre ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010

Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks

This article concerns the following question arising in computational evolutionary biology. For a given subclass of phylogenetic networks, what is the maximum value of 0

2010

Scheduling periodic tasks in a hard real-time environment

Friedrich Eisenbrand, Martin Niemeier, Nicolai Hähnle

We give a rigorous account on the complexity landscape of an important real-time scheduling problem that occurs in the design of software-based aircraft control. The goal is to distribute tasks

\tau_i=(c_i,p_i)

on a minimum number of identical machines a ...

Springer-Verlag2010

On the Complexity of the Asymmetric VPN Problem

Thomas Rothvoss, Laura Sanità

We give the first constant factor approximation algorithm for the asymmetric Virtual Private Network (VPN) problem with arbitrary concave costs. We even show the stronger result, that there is always a tree solution of cost at most 2 OPT and that a tree so ...

Springer2009

Drawing (complete) binary tanglegrams: Hardness, approximation, fixed-parameter tractability

A binary tanglegram is a pair (S, T) of binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example in phylogenetics, it is essential that both trees are drawn without edge ...

Springer2009

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

Dominique de Werra

We study complexity and approximation of MIN WEIGHTED NODE COLORING in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove ...

2009

Combinatorial algorithms for wireless information flow

Christina Fragouli, Aurore Amaudruz

A long-standing open question in information theory is to characterize the unicast capacity of a wireless relay network. The difficulty arises due to the complex signal interactions induced in the network, since the wireless channel inherently broadcasts t ...

2009

Generalized Hypertree Decompositions: NP-hardness and Tractable Variants

Zoltán Miklós

The generalized hypertree width GHW(H) of a hypergraph H is a measure of its cyclicity. Classes of conjunctive queries or constraint satisfaction problems whose associated hypergraphs have bounded GHW are known to be solvable in polynomial time. However, i ...

2009

Sorting signed permutations by inversions in O(nlogn) time

Bernard Moret, Yu Lin, Vaibhav Rajan, Krister Swenson

The study of genomic inversions (or reversals) has been a mainstay of computational genomics for nearly 20 years. After the initial breakthrough of Hannenhalli and Pevzner, who gave the first polynomial-time algorithm for sorting signed permutations by inv ...

Springer2009

Polynomial-time approximation scheme

Graph Chatbot

Chat with Graph Search

Sorting signed permutations by inversions in O(nlogn) time

k-Edge-Connectivity: Approximation and LP Relaxation

Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks

Scheduling periodic tasks in a hard real-time environment

On the Complexity of the Asymmetric VPN Problem

Drawing (complete) binary tanglegrams: Hardness, approximation, fixed-parameter tractability

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

Combinatorial algorithms for wireless information flow

Generalized Hypertree Decompositions: NP-hardness and Tractable Variants

Sorting signed permutations by inversions in O(nlogn) time

Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks

Sorting signed permutations by inversions in O(nlogn) time

k-Edge-Connectivity: Approximation and LP Relaxation

Scheduling periodic tasks in a hard real-time environment

On the Complexity of the Asymmetric VPN Problem

Drawing (complete) binary tanglegrams: Hardness, approximation, fixed-parameter tractability

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

Combinatorial algorithms for wireless information flow

Generalized Hypertree Decompositions: NP-hardness and Tractable Variants

Sorting signed permutations by inversions in O(nlogn) time