共查询到20条相似文献,搜索用时 211 毫秒
1.
Abstract. We show that the 2-Opt and 3-Opt heuristics for the traveling salesman problem (TSP) on the complete graph K
n
produce a solution no worse than the average cost of a tour in K
n
in a polynomial number of iterations. As a consequence, we get that the domination numbers of the 2- Opt , 3- Opt , Carlier—Villon,
Shortest Path Ejection Chain, and Lin—Kernighan heuristics are all at least (n-2)! / 2 . The domination number of the Christofides heuristic is shown to be no more than
, and for the Double Tree heuristic and a variation of the Christofides heuristic the domination numbers are shown to be
one (even if the edge costs satisfy the triangle inequality). Further, unless P = NP, no polynomial time approximation algorithm
exists for the TSP on the complete digraph
with domination number at least (n-1)!-k for any constant k or with domination number at least (n-1)! - (( k /(k+1))(n+r))!-1 for any non-negative constants r and k such that (n+r)
0 mod (k+1). The complexities of finding the median value of costs of all the tours in
and of similar problems are also studied. 相似文献
2.
2-Opt is probably the most basic local search heuristic for the TSP. This heuristic achieves amazingly good results on “real world” Euclidean instances both with respect to running time and approximation ratio. There are numerous experimental studies on the performance of 2-Opt. However, the theoretical knowledge about this heuristic is still very limited. Not even its worst case running time on 2-dimensional Euclidean instances was known so far. We clarify this issue by presenting, for every $p\in\mathbb{N}$ , a family of L p instances on which 2-Opt can take an exponential number of steps. Previous probabilistic analyses were restricted to instances in which n points are placed uniformly at random in the unit square [0,1]2, where it was shown that the expected number of steps is bounded by $\tilde{O}(n^{10})$ for Euclidean instances. We consider a more advanced model of probabilistic instances in which the points can be placed independently according to general distributions on [0,1] d , for an arbitrary d≥2. In particular, we allow different distributions for different points. We study the expected number of local improvements in terms of the number n of points and the maximal density ? of the probability distributions. We show an upper bound on the expected length of any 2-Opt improvement path of $\tilde{O}(n^{4+1/3}\cdot\phi^{8/3})$ . When starting with an initial tour computed by an insertion heuristic, the upper bound on the expected number of steps improves even to $\tilde{O}(n^{4+1/3-1/d}\cdot\phi^{8/3})$ . If the distances are measured according to the Manhattan metric, then the expected number of steps is bounded by $\tilde{O}(n^{4-1/d}\cdot\phi)$ . In addition, we prove an upper bound of $O(\sqrt[d]{\phi})$ on the expected approximation factor with respect to all L p metrics. Let us remark that our probabilistic analysis covers as special cases the uniform input model with ?=1 and a smoothed analysis with Gaussian perturbations of standard deviation σ with ?~1/σ d . 相似文献
3.
《国际计算机数学杂志》2012,89(5):649-664
This paper extends the work of a previous paper of the author. A theoretical argument is provided to justify the heuristic algorithm used in the former paper. On the basis of the theory one derives, the previous algorithm can be further simplified. In the simplified basis function algorithm, the regular basis function (where $N_i^1(t)$ is 1 for $t_i \le t \lt t_{i + 1}$ and zero elsewhere) can be used for all cases except the case of the last point of a clamped B-spline where the basis function is modified to $N_{i,1} (t)$ where is 1 for $t_i \le t \le t_{i + 1}$ and zero elsewhere. Under this simplified algorithm, the knots ( i.e. , $t_{0}$ , $t_{1}, \ldots, t_{n+k}$ ) are a k -extended partition in the interior of the knot vector with a possibility that two ends of the knot vector could be a $(k + 1)$ -extended partition (case of clamped B-spline). It is shown that given a set of $(n + 1)$ control points, $V_{0}$ , $V_{1}, \ldots, V_{n}$ , the order of k , and the knots $(t_{0}, t_{1}, \ldots, t_{n+k})$ , the B-spline $P(t) = \sum_{i = 0}^{n} N_{i}^{k}(t)V_{i}$ is a continuous function for $t \in [t_{k - 1}, t_{n + 1}]$ and maintains the partition of unity. This algorithm circumvents the problem of generating a spike at the last point of a clamped B-spline. The constraint of having k -extended partition interior knots overcomes the problem of disconnecting the B-spline at the k repeated knot. 相似文献
4.
For a set $P$ of $n$ points in the plane and an integer $k \leq
n$, consider the problem of finding the smallest circle enclosing
at least $k$ points of $P$. We present a randomized algorithm
that computes in $O( n k )$ expected time such a circle, improving
over previously known algorithms. Further, we present a linear
time $\delta$-approximation algorithm that outputs a circle that
contains at least $k$ points of $P$ and has radius less than
$(1+\delta)r_{opt}(P,k)$, where $r_{opt}(P,k)$ is the radius of the
minimum circle containing at least $k$ points of $P$. The expected
running time of this approximation algorithm is $O(n + n
\cdot\min((1/k\delta^3) \log^2 (1/\delta),
k))$. 相似文献
5.
Tahmineh? Keshavarzi Farideh?Sedaghat G.?Ali?Mansoori 《Microfluidics and nanofluidics》2010,8(1):97-104
The aim of our research is to develop a theory, which can predict the behavior of confined fluids in nanoslit pores. The nanoslit
pores studied in this work consist of two structureless and parallel walls in the xy plane located at z = 0 and z = H, in equilibrium with a bulk homogeneous fluid at the same temperature and at a given uniform bulk density. We have derived
the following general equation for prediction of the normal pressure tensor P
zz
of confined inhomogeneous fluids in nanoslit pores:
$ P_{zz} = kT\rho \left( {r_{1z} } \right)\left[ {1 + \frac{1}{kT}\frac{{\partial \phi_{\text{ext}} }}{{\partial r_{1z} }}{\text{d}}r_{1z} } \right] - \frac{1}{2}\int\limits_{v} {\varphi^{\prime}(\vec{r}_{12} )\rho^{(2)} \left( {\overset{\lower0.5em\hbox{$ P_{zz} = kT\rho \left( {r_{1z} } \right)\left[ {1 + \frac{1}{kT}\frac{{\partial \phi_{\text{ext}} }}{{\partial r_{1z} }}{\text{d}}r_{1z} } \right] - \frac{1}{2}\int\limits_{v} {\varphi^{\prime}(\vec{r}_{12} )\rho^{(2)} \left( {\overset{\lower0.5em\hbox{ 相似文献
6.
We study the problem of computing the k maximum sum subsequences. Given a sequence of real numbers
and an integer parameter k,
the problem involves finding the k largest values of
for
The problem for fixed k = 1, also known as the maximum sum subsequence problem, has received much attention in the literature
and is linear-time solvable. Recently, Bae and Takaoka presented a
-time algorithm for the k maximum sum subsequences problem. In this paper we design an efficient algorithm that solves the
above problem in
time in the worst case. Our algorithm is optimal for
and improves over the previously best known result for any value of the user-defined parameter k < 1. Moreover, our results
are also extended to the multi-dimensional versions of the k maximum sum subsequences problem; resulting in fast algorithms
as well. 相似文献
7.
The aim of our research is to demonstrate the role of attractive intermolecular potential energy on normal pressure tensor
of confined molecular fluids inside nanoslit pores of two structureless purely repulsive parallel walls in xy plane at z = 0 and z = H, in equilibrium with a bulk homogeneous fluid at the same temperature and at a uniform density. To achieve this we have derived
the perturbation theory version of the normal pressure tensor of confined inhomogeneous fluids in nanoslit pores:
|
设为首页 | 免责声明 | 关于勤云 | 加入收藏 |
Copyright©北京勤云科技发展有限公司 京ICP备09084417号 |