In this paper we present a faster exact exponential time algorithm for the edge dominating set problem. Our algorithm uses O(1.3226(n)) time and polynomial space. The algorithm combines an enumeration approach based o...
详细信息
ISBN:
(纸本)9783540797227
In this paper we present a faster exact exponential time algorithm for the edge dominating set problem. Our algorithm uses O(1.3226(n)) time and polynomial space. The algorithm combines an enumeration approach based on enumerating minimal vertex covers with the branch and reduce paradigm. Its time bound is obtained using the measure and conquer technique. The algorithm is obtained by starting with a slower algorithm which is refined stepwise. In this way a series of algorithms appears, each one slightly faster than the previous, resulting in the O(1.3226(n)) time algorithm. The techniques also gives faster exact algorithms for: minimum weight edge dominating set, minimum (weight) maximal matching, matrix domination and the parametrised version of minimum weight maximal matching.
We explore the complexity and exact computation of a variant of the classical stable marriage problem in which we seek matchings that are not only stable, but are also "fair" in a formal sense. In particular...
详细信息
We explore the complexity and exact computation of a variant of the classical stable marriage problem in which we seek matchings that are not only stable, but are also "fair" in a formal sense. In particular, we study the sex-equal stable marriage problem (SESM), in which, roughly speaking, we wish to find a stable matching with the property that the men's happiness is as close as possible to the women's happiness. This problem is known to be strongly NP-hard (Kato in Jpn. J. Ind. Appl. Math. 10:1-19, 1993). We specifically consider SESM instances in which the preference lists of the men and/or women are bounded in length by a constant. On the negative side, we show that SESM is NP-hard, even if both the men's and women's preference lists are of length at most three, and is not even in the class XP when parameterized by the objective value of the solution. This strengthens the NP-hardness results of Kato (Jpn. J. Ind. Appl. Math. 10:1-19, 1993). On the positive side, we show that our hardness result is "tight" by giving a polynomial-time algorithm for the case in which the preference lists on one side (say the men) are of length at most two, and the lengths of the lists on the other side (the women) are unbounded. Furthermore, we give a low-order exponential-time algorithm for SESM in which the preference lists on one side are of length at most l (and the lengths of the lists on the other side are unbounded). In particular, for every pair of constants and there is an algorithm with running time bounded by . Hence, if I mu is chosen to be a sufficiently small constant, the running time is in O (a
We design exact algorithms for the following two problems in survivable network design: (i) designing a minimum cost network with a desired value of edge connectivity, which is called MINIMUM WEIGHT lambda- CONNECTED ...
详细信息
We design exact algorithms for the following two problems in survivable network design: (i) designing a minimum cost network with a desired value of edge connectivity, which is called MINIMUM WEIGHT lambda- CONNECTED SPANNING SUBGRAPH and (ii) augmenting a given network to a desired value of edge connectivity at a minimum cost which is called MINIMUM WEIGHT lambda- CONNECTIVITY AUGMENTATION. It is easy to see that a minimum solution to these problems contains at most 2 lambda(n - 1) edges. Using this fact one can design a brute-force algorithm which runs in time 2(O()(lambda n log n)()), however no better algorithms were known previously. In this paper, we give the first single exponential time algorithm for these problems, i.e. running in time 2(O()(lambda n)), for both undirected and directed networks. Our results are obtained via well known characterizations of lambda-connected graphs, their connections to linear matroids and the recently developed technique of dynamic programming with representative sets.
We review the most important mathematical models and algorithms developed for the exact solution of the one-dimensional bin packing and cutting stock problems, and experimentally evaluate, on state-of-the art computer...
详细信息
We review the most important mathematical models and algorithms developed for the exact solution of the one-dimensional bin packing and cutting stock problems, and experimentally evaluate, on state-of-the art computers, the performance of the main available software tools. (C) 2016 Elsevier B.V. All rights reserved.
In this paper we review the exact algorithms proposed in the last three decades for the solution of the vehicle routing problem with time windows (VRPTW). The exact algorithms for the VRPTW are in many aspects inherit...
详细信息
In this paper we review the exact algorithms proposed in the last three decades for the solution of the vehicle routing problem with time windows (VRPTW). The exact algorithms for the VRPTW are in many aspects inherited from work on the traveling salesman problem (TSP). In recognition of this fact this paper is structured relative to four seminal papers concerning the formulation and exact solution of the TSP, i.e. the arc formulation, the arc-node formulation, the spanning tree formulation, and the path formulation. We give a detailed analysis of the formulations of the VRPTW and a review of the literature related to the different formulations. There are two main lines of development in relation to the exact algorithms for the VRPTW. One is concerned with the general decomposition approach and the solution to certain dual problems associated with the VRPTW. Another more recent direction is concerned with the analysis of the polyhedral structure of the VRPTW. We conclude by examining possible future lines of research in the area of the VRPTW. (C) 2006 Elsevier Ltd. All rights reserved.
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.
The maximum independent set problem is one of the most important problems in graph algorithms and has been extensively studied in the line of research on the worst-case analysis of exact algorithms for NP-hard problem...
详细信息
ISBN:
(纸本)9783030895433;9783030895426
The maximum independent set problem is one of the most important problems in graph algorithms and has been extensively studied in the line of research on the worst-case analysis of exact algorithms for NP-hard problems. In the weighted version, each vertex in the graph is associated with a weight and we are going to find an independent set of maximum total vertex weight. In this paper, we design several reduction rules and a fast exact algorithm for the maximum weighted independent set problem, and use the measure-and-conquer technique to analyze the running time bound of the algorithm. Our algorithm works on general weighted graphs and it has a good running time bound on sparse graphs. If the graph has an average degree at most 3, our algorithm runs in O* (1.1443(n)) time and polynomial space, improving previous running time bounds for the problem in cubic graphs using polynomial space.
This paper provides a review of the recent developments that had a major impact on the current state-of-the-art exact algorithms for the vehicle routing problem (VRP). The paper reviews mathematical formulations, rela...
详细信息
This paper provides a review of the recent developments that had a major impact on the current state-of-the-art exact algorithms for the vehicle routing problem (VRP). The paper reviews mathematical formulations, relaxations and recent exact methods for two of the most important variants of the VRP: the capacitated VRP (CVRP) and the VRP with time windows (VRPTW). The paper also reports a comparison of the computational performances of the different exact algorithms for the CVRP and VRPTW. (C) 2011 Elsevier B.V. All rights reserved.
The multi-objective spanning tree (MoST) is an extension of the minimum spanning tree problem (MST) that, as well as its single-objective counterpart, arises in several practical applications. However, unlike the MST,...
详细信息
The multi-objective spanning tree (MoST) is an extension of the minimum spanning tree problem (MST) that, as well as its single-objective counterpart, arises in several practical applications. However, unlike the MST, for which there are polynomial-time algorithms that solve it, the MoST is NP-hard. Several researchers proposed techniques to solve the MoST, each of those methods with specific potentialities and limitations. In this study, we examine those methods and divide them into two categories regarding their outcomes: Pareto optimal sets and Pareto optimal fronts. To compare the techniques from the two groups, we investigated their behavior on 2, 3 and 4-objective instances from different classes. We report the results of a computational experiment on 8100 complete and grid graphs in which we analyze specific features of each algorithm as well as the computational effort required to solve the instances.
Recent times have seen quite some progress in the development of 'efficient' exponential-time algorithms for NP-hard problems. These results are also tightly related to the so-called theory of fixed parameter ...
详细信息
Recent times have seen quite some progress in the development of 'efficient' exponential-time algorithms for NP-hard problems. These results are also tightly related to the so-called theory of fixed parameter tractability. In this incomplete, personally biased survey, we reflect on some recent developments and prospects in the field of fixed parameter algorithms. (C) 2001 Elsevier Science B.V. All rights reserved.
暂无评论