We discuss fast exponential time exact algorithms for generalized combinatorial optimization problems. The list of discussed NP-complete generalized combinatorial optimization problems includes the generalized minimum...
详细信息
ISBN:
(纸本)9783540735557
We discuss fast exponential time exact algorithms for generalized combinatorial optimization problems. The list of discussed NP-complete generalized combinatorial optimization problems includes the generalized minimum spanning tree problem, the generalized subset assignment problem and the generalized travelling salesman problem.
In the Connected Red-Blue Dominating Set problem we are given a graph G whose vertex set is partitioned into two parts R and B (red and blue vertices), and we are asked to find a connected subgraph induced by a subset...
详细信息
In the Connected Red-Blue Dominating Set problem we are given a graph G whose vertex set is partitioned into two parts R and B (red and blue vertices), and we are asked to find a connected subgraph induced by a subset S of B such that each red vertex of G is adjacent to some vertex in S. The problem can be solved in O*(2(n-|B|)) time by reduction to the Weighted Steiner Tree problem. Combining exhaustive enumeration when |B| is small with the Weighted Steiner Tree approach when |B| is large, solves the problem in O-*(1.4143(n)). In this paper we present a first non-trivial exact algorithm whose running time is in O-*(1.3645(n)). We use our algorithm to solve the Connected Dominating Set problem in O-*(1.8619(n)). This improves the current best known algorithm, which used sophisticated run-time analysis via the measure and conquer technique to solve the problem in O-*(1.8966(n)). (C) 2011 Elsevier B.V. All rights reserved.
The capacitated vehicle routing problem (CVRP) is the problem in which a set of identical vehicles located at a central depot is to be optimally routed to supply customers with known demands subject to vehicle capacit...
详细信息
The capacitated vehicle routing problem (CVRP) is the problem in which a set of identical vehicles located at a central depot is to be optimally routed to supply customers with known demands subject to vehicle capacity constraints. This paper provides a review of the most recent developments that had a major impact in the current state-of-the-art of exact algorithms for the CVRP. The most important mathematical formulations for the problem together with various CVRP relaxations are reviewed. The paper also describes the recent exact methods for the CVRP and reports a comparison of their computational performances.
Analyzing genomic data for finding those gene variations which are responsible for hereditary diseases is one of the great challenges in modern bioinformatics. In many living beings (including the human), every gene i...
详细信息
Analyzing genomic data for finding those gene variations which are responsible for hereditary diseases is one of the great challenges in modern bioinformatics. In many living beings (including the human), every gene is present in two copies, inherited from the two parents, the so-called haplotypes. In this paper, we propose a simple combinatorial model for classifying the set of haplotypes in a population according to their responsibility for a certain genetic disease. This model is based on the minimum-ones 2SAT problem with uniform clauses. The minimum-ones 2SAT problem asks for a satisfying assignment to a satisfiable formula in 2CNF which sets a minimum number of variables to true. This problem is well-known to be NP-hard, even in the case where all clauses are uniform, i.e., do not contain a positive and a negative literal. We analyze the approximability and present the first non-trivial exact algorithm for the uniform minimum-ones 2SAT problem with a running time of O(1.21061(n)) on a 2SAT formula with n variables. We also show that the problem is fixed-parameter tractable by showing that our algorithm can be adapted to verify in O*(2(k)) time whether an assignment with at most k true variables exists.
We introduce the s-Plex Cluster Editing problem as a generalization of the well-studied Cluster Editing problem;both are NP-hard and both are motivated by graph-based data clustering. Instead of transforming a given g...
详细信息
We introduce the s-Plex Cluster Editing problem as a generalization of the well-studied Cluster Editing problem;both are NP-hard and both are motivated by graph-based data clustering. Instead of transforming a given graph by a minimum number of edge modifications into a disjoint union of cliques (this is Cluster Editing), the task in the case of s-Plex Cluster Editing is to transform a graph into a cluster graph consisting of a disjoint union of so-called s-plexes. Herein, an s-plex is a vertex set S inducing a subgraph in which every vertex has degree at least vertical bar S vertical bar - s. Cliques are 1-plexes. The advantage of s-plexes for s >= 2 is that they allow us to model a more relaxed cluster notion (s-plexes instead of cliques), better reflecting inaccuracies of the input data. We develop a provably effective preprocessing based on data reduction (yielding a so-called problem kernel), a forbidden subgraph characterization of s-plex cluster graphs, and a depth-bounded search tree which is used to find optimal edge modification sets. Altogether, this yields efficient algorithms in case of moderate numbers of edge modifications;this is often a reasonable assumption under a maximum parsimony model for data clustering.
We develop an algorithmically useful refinement of a forbidden submatrix characterization of 0/1-matrices fulfilling the Consecutive Ones Property (C1P) This characterization finds applications in new polynomial-time ...
详细信息
We develop an algorithmically useful refinement of a forbidden submatrix characterization of 0/1-matrices fulfilling the Consecutive Ones Property (C1P) This characterization finds applications in new polynomial-time approximation algorithms and fixed-parameter tractability results for the NP-hard problem to delete a minimum number of rows or columns from a 0/1-matrix such that the remaining submatrix has the C I P (C) 2009 Elsevier Inc. All rights reserved
MINIMUM DOMINATING SET OF QUEENS is one of the typical programming exercises of a first year's computer science course. However, little work has been published on the complexity of this problem. We analyse here se...
详细信息
MINIMUM DOMINATING SET OF QUEENS is one of the typical programming exercises of a first year's computer science course. However, little work has been published on the complexity of this problem. We analyse here several algorithms and show that advanced algorithmic techniques may dramatically speed up solving this problem. (C) 2009 Elsevier B.V. All rights reserved.
The Traveling Salesman Problem (TSP) is one of the most famous problems in combinatorial optimization. Hundreds of papers have been written on the TSP and several exact and heuristic algorithms are available for it. T...
详细信息
The Traveling Salesman Problem (TSP) is one of the most famous problems in combinatorial optimization. Hundreds of papers have been written on the TSP and several exact and heuristic algorithms are available for it. Their concise guide outlines the most important and best algorithms for the symmetric and asymmetric versions of the TSP. In several cases, references to publicly available software are provided. Journal of the Operational Research Society (2010) 61, 35-40. doi:10.1057/jors.2009.76
We first propose a new method, called "bottom-up method", that, informally, "propagates" improvement of the worst-case complexity for "sparse" instances to "denser" ones and we ...
详细信息
ISBN:
(纸本)9783642137303
We first propose a new method, called "bottom-up method", that, informally, "propagates" improvement of the worst-case complexity for "sparse" instances to "denser" ones and we show an easy though nontrivial application of it to the MIN SET COVER problem. We then tackle MAX INDEPENDENT SET. Following the bottom-up method we propagate improvements of worst-case complexity from graphs of average degree d to graphs of average degree greater than d. Indeed, using algorithms for MAX INDEPENDENT SET in graphs of average degree 3, we tackle MAX INDEPENDENT SET in graphs of average degree 4, 5 and 6. Then, we combine the bottom-up technique with measure and conquer techniques to get improved running times for graphs of maximum degree 4, 5 and 6 but also for general graphs. The best computation bounds obtained for MAX INDEPENDENT SET are O*(1.157(n)), O*(1.1918(n)) and O*(1.2071(n)), for graphs of maximum (or more generally average) degree 4, 5 and 6 respectively, and O*(1.2127(n)) for general graphs. These results improve upon the best known polynomial space results for these cases.
We present a Monte Carlo algorithm for Hamiltonicity detection in an n-vertex undirected graph running in O*(1.657(n)) time. To the best of our knowledge, this is the first superpolynomial improvement on the worst cas...
详细信息
ISBN:
(纸本)9780769542447
We present a Monte Carlo algorithm for Hamiltonicity detection in an n-vertex undirected graph running in O*(1.657(n)) time. To the best of our knowledge, this is the first superpolynomial improvement on the worst case runtime for the problem since the O*(2(n)) bound established for TSP almost fifty years ago (Bellman 1962, Held and Karp 1962). It answers in part the first open problem in Woeginger's 2003 survey on exact algorithms for NP-hard problems. For bipartite graphs, we improve the bound to O*(1.414(n)) time. Both the bipartite and the general algorithm can be implemented to use space polynomial in n. We combine several recently resurrected ideas to get the results. Our main technical contribution is a new reduction inspired by the algebraic sieving method for k-Path (Koutis ICALP 2008, Williams IPL 2009). We introduce the Labeled Cycle Cover Sum in which we are set to count weighted arc labeled cycle covers over a finite field of characteristic two. We reduce Hamiltonicity to Labeled Cycle Cover Sum and apply the determinant summation technique for exact Set Covers (Bjorklund STACS 2010) to evaluate it.
暂无评论