Given a weighted graph G = (V, E), the Equitable Traveling Salesman Problem (ETSP) asks for two perfect matchings in G such that (1) the two matchings together form a Hamiltonian cycle in G and (2) the absolute differ...
详细信息
Given a weighted graph G = (V, E), the Equitable Traveling Salesman Problem (ETSP) asks for two perfect matchings in G such that (1) the two matchings together form a Hamiltonian cycle in G and (2) the absolute difference in costs between the two matchings is minimized. The problem is shown to be NP Hard, even when the graph G is complete. We present two integer programming models to solve the ETSP problem and compare the strength of these formulations. One model is solved through branch-and cut, whereas the other model is solved through a branch-and-price framework. A simple local search heuristic is also implemented. We conduct computational experiments on different types of instances, often derived from the TSPLib. It turns out that the behavior of the different approaches varies with the type of instances. For small and medium sized instances, branch-and-bound and branch-and-price produce comparable results. However, for larger instances branch-and-bound outperforms branch-and price. (C) 2017 Elsevier B.V. All rights reserved.
The aim of this paper is to point out that all mathematical programming models proposed by Ying et al. (2016) are incorrect. We present four revised mathematical programming models and four improved mathematical progr...
详细信息
The aim of this paper is to point out that all mathematical programming models proposed by Ying et al. (2016) are incorrect. We present four revised mathematical programming models and four improved mathematical programming models by adding and revising some constraints and decision variables. Moreover, we show that the first three scheduling problems considered in their paper are equivalent to the problems with the objective of minimizing the sum of completion times or minimizing the maximum lateness, which can be solved by algorithms proposed by Luo et al. (2015) in O(n(2)) time. (C) 2017 Elsevier Ltd. All rights reserved.
This paper deals with four single-machine scheduling problems (SMSPs) with a variable machine maintenance. The objectives of the four SMSPs are to minimize mean lateness, maximum tardiness, total flow time and mean ta...
详细信息
This paper deals with four single-machine scheduling problems (SMSPs) with a variable machine maintenance. The objectives of the four SMSPs are to minimize mean lateness, maximum tardiness, total flow time and mean tardiness, respectively. These four SMSPs are important in the literature and in practice. This study proposes an exact algorithm with the computational complexity O(n(2)) for each of the four SMSPs. In addition to the given jobs, the machine maintenance activity between two consecutive jobs is optimally scheduled. (C) 2016 Elsevier Ltd. All rights reserved.
In the INTERVALIZING COLOURED GRAPHS problem, one must decide for a given graph G = (V, E) with a proper vertex colouring of G whether G is the subgraph of a properly coloured interval graph. For the case that the num...
详细信息
In the INTERVALIZING COLOURED GRAPHS problem, one must decide for a given graph G = (V, E) with a proper vertex colouring of G whether G is the subgraph of a properly coloured interval graph. For the case that the number of colors is fixed, we give an exact algorithm that uses 2(O(n/log n)) time. We also give an O*(2(n)) algorithm for the case that the number of colors is not fixed.
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 the game of KAYLES, two players select alternatingly a vertex from a given graph G, but may never choose a vertex that is adjacent or equal to an already chosen vertex. The last player that can select a vertex wins...
详细信息
In the game of KAYLES, two players select alternatingly a vertex from a given graph G, but may never choose a vertex that is adjacent or equal to an already chosen vertex. The last player that can select a vertex wins the game. In this paper, we give an exact algorithm to determine which player has a winning strategy in this game. To analyze the running time of the algorithm, we introduce the notion of a K-set: a nonempty set of vertices W subset of V is a K-set in a graph G = (V, E), if G[W] is connected and there exists an independent set X such that W = V - N[X]. The running time of the algorithm is bounded by a polynomial factor times the number of K-sets in G. We prove that the number of K-sets in a graph with n vertices is bounded by O(1.6052(n)). A computer-generated case analysis improves this bound to O(1.6031(n)) K-sets, and thus we have an upper bound of O(1.6031(n)) on the running time of the algorithm for KAYLES. We also show that the number of K-sets in a tree is bounded by n center dot 3(n/3) and thus KAYLEs can be solved on trees in O(1.4423(n)) time. We show that apart from a polynomial factor, the number of K-sets in a tree is sharp. As corollaries, we obtain that determining which player has a winning strategy in the games G(avoid)(POSDNF2) and G(seek)(POSDNF3) can also be determined in O(1.6031(n)) time. In G(avoid)(POSDNF2), we have a positive formula F on n Boolean variables in Disjunctive Normal Form with two variables per clause. Initially, all variables are false, and players alternately set a variable from false to true;the first player that makes F true loses the game. The game G(seek)(POSDNF3) is similar, but now there are three variables per clause, and the first player that makes F true wins the game. (C) 2014 Elsevier B.V. All rights reserved.
A dominating induced matching, also called an efficient edge domination, of a graph G = (V, E) with n = vertical bar V vertical bar vertices and m = vertical bar E vertical bar edges is a subset F subset of E of edges...
详细信息
A dominating induced matching, also called an efficient edge domination, of a graph G = (V, E) with n = vertical bar V vertical bar vertices and m = vertical bar E vertical bar edges is a subset F subset of E of edges in the graph such that no two edges in F share a common endpoint and each edge in E \ F is incident with exactly one edge in F. It is NP-hard to decide whether a graph admits a dominating induced matching or not. In this paper, we design a 1.1467(n)n(0(1)) -time exact algorithm for this problem, improving all previous results. This problem can be redefined as a partition problem that is to partition the vertex set of a graph into two parts I and F, where I induces an independent set (a 0-regular graph) and F induces a perfect matching (a 1-regular graph), After giving several structural properties of the problem, we show that the problem always contains some "good vertices," branching on which by including them to either I or F we can effectively reduce the graph. This leads to a fast exact algorithm to this problem. (C) 2015 Elsevier B.V. All rights reserved.
Motion planning is a major topic in robotics. Divergent paths have been taken by practical roboticists and theoretical motion planners. Our goal is to produce algorithms that are practical and have strong theoretical ...
详细信息
ISBN:
(纸本)9783319165950;9783319165943
Motion planning is a major topic in robotics. Divergent paths have been taken by practical roboticists and theoretical motion planners. Our goal is to produce algorithms that are practical and have strong theoretical guarantees. Recently, we have proposed a subdivision approach based on soft predicates Wang, C., Chiang, Y.-J., Yap, C.: On soft predicates in subdivision motion planning. In: 29th ACM Symposium on Computational Geometry (SoCG'13), pp. 349-358 (2013). To appear CGTA, Special Issue for SoCG' 13 [20], but with a new notion of correctness called resolution-exactness. Unlike mos ques for planar link robots. The technical contributions of this paper are the design of soft predicates for link robots, a novel "T/R splitting method" for subdivision, and feature-based search strategies. The T/R idea is to give primacy to the translational (T) components, and perform splitting of rotational components (R) only at the leaves of a subdivision tree. We implemented our algorithm for a 2-link robot with 4 degrees of freedom (DOFs). Our implementation achieves real-time performance on a variety of nontrivial scenarios. For comparison, our method outperforms sampling-based methods significantly. We extend our 2-link planner to thick link robots with little impact on performance. Note that there are no known exact algorithms for thick link robots.
In this paper,we consider the exact quantum query complexity of two fundamental symmetric functions.1)MOD_(m)^(n),which calculates the Hamming weight of an-bit string modulo;2)exact_(k,l)^(n),which determines if the H...
详细信息
In this paper,we consider the exact quantum query complexity of two fundamental symmetric functions.1)MOD_(m)^(n),which calculates the Hamming weight of an-bit string modulo;2)exact_(k,l)^(n),which determines if the Hamming weight of an-bit string is exactly k or *** these two symmetric functions have received considerable attention,their exact quantum query complexities have not been fully ***,our results are as follows:1)We design an optimal quantum query algorithm to compute MOD_(m)^(n)exactly and thus provide a tight characterization of its exact quantum query complexity,which settles a previous *** on this algorithm,we demonstrate that a broad class of symmetric functions is not evasive in the quantum model,i.e.,there exist quantum algorithms to compute these functions exactly when the number of queries is less than their input size.2)By proposing a quantum algorithm that utilizes the minimum number of queries to compute exact_(k,l)^(n)exactly for some specific values of k and l,we give a tight characterization of its exact quantum query complexity in these scenarios.
The Orienteering Problem is a routing problem aiming at selecting a subset of a given set of customers to visited within a given time budget, so that a total revenue is maximized. Multiple variants of the problem have...
详细信息
The Orienteering Problem is a routing problem aiming at selecting a subset of a given set of customers to visited within a given time budget, so that a total revenue is maximized. Multiple variants of the problem have been studied. The Probabilistic Orienteering Problem is one of these variants, where customers will require visit according to a certain given probability. Stochasticity makes the model more practical, but concurrently more difficult to solve. Effective approaches to solve the problem potentially lead to higher quality planning in real-life logistics, thanks to the exploitation of the probabilistic informations that can normally be derived from historical data. In this paper we present an iterative model-based algorithm that solves a sequence of deterministic problems and is able to retrieve and certify optimal solutions if run for sufficient time. Experimental results show that the new approach is performing well when compared against both the exact (proven optimality) and heuristic (high quality solutions) algorithms available in the literature.
暂无评论