共查询到20条相似文献,搜索用时 93 毫秒
1.
Given a graph G, an integer k, and a demand set D={(s1,t1),…,(sl,tl)}, the k-Steiner Forest problem finds a forest in graph G to connect at least k demands in D such that the cost of the forest is minimized. This problem was proposed by Hajiaghayi and Jain in SODA’06. Thereafter, using a Lagrangian relaxation technique, Segev et al. gave the first approximation algorithm to this problem in ESA’06, with performance ratio O(n2/3logl). We give a simpler and faster approximation algorithm to this problem with performance ratio O(n2/3logk) via greedy approach, improving the previously best known ratio in the literature. 相似文献
2.
For a set T of n points (terminals) in the plane, a Manhattan network on T is a network N(T)=(V,E) with the property that its edges are horizontal or vertical segments connecting points in V⊇T and for every pair of terminals, the network N(T) contains a shortest l1-path between them. A minimum Manhattan network on T is a Manhattan network of minimum possible length. The problem of finding minimum Manhattan networks has been introduced by Gudmundsson, Levcopoulos, and Narasimhan [J. Gudmundsson, C. Levcopoulos, G. Narasimhan, Approximating a minimum Manhattan network, Nordic Journal of Computing 8 (2001) 219–232. Proc. APPROX’99, 1999, pp. 28–37] and its complexity status is unknown. Several approximation algorithms (with factors 8, 4, and 3) have been proposed; recently Kato, Imai, and Asano [R. Kato, K. Imai, T. Asano, An improved algorithm for the minimum Manhattan network problem, ISAAC’02, in: LNCS, vol. 2518, 2002, pp. 344–356] have given a factor 2-approximation algorithm, however their correctness proof is incomplete. In this paper, we propose a rounding 2-approximation algorithm based on an LP-formulation of the minimum Manhattan network problem. 相似文献
3.
The local b-function bf,p(s) of an n-variate polynomial f∈C[x] (x=(x1,…,xn)) at a point p∈Cn is constant on each stratum of a stratification of Cn. We propose a new method for computing such a stratification and bf,p(s) on each stratum. In the existing method proposed in Oaku (1997b), a primary ideal decomposition of an ideal in C[x,s] is needed and our experiment shows that the primary decomposition can be a bottleneck for computing the stratification. In our new method, the computation can be done by just computing ideal quotients and examining inclusions of algebraic sets. The precise form of a stratum can be obtained by computing the decomposition of the radicals of the ideals in C[x] defining the stratum. We also introduce various techniques for improving the practical efficiency of the implementation and we show results of computations for some examples. 相似文献
4.
5.
Motivated by the famous 3n+1 conjecture, we call a mapping from Z to Zresidue-class-wise affine if there is a positive integer m such that it is affine on residue classes (mod m). This article describes a collection of algorithms and methods for computation in permutation groups and monoids formed by residue-class-wise affine mappings. 相似文献
6.
We show how to calculate three low degree set-theoretic generators (i.e., algebraic surfaces) for all rational space curves of low degree (degree ≤6) as well as for all higher degree rational space curves where at least one element of their μ-basis has degree 1 from a μ-basis of the parametrization. In addition to having low degree, at least two of these surface generators are always ruled surfaces. Whenever possible we also show how to compute two set-theoretic complete intersection generators for these rational space curves from a μ-basis of their parametrization. 相似文献
7.
We give simple, self-contained proofs of the basic hardness results for the classes W[t] of the weft hierarchy. We extend these proofs to higher levels of the hierarchy and illuminate the distinctions among its classes. The anti-monotone collapse at W[1,s] and the normalization of weft-t formulas arise as by-products of the proofs. 相似文献
8.
Motivated by recent applications of wireless sensor networks in monitoring infrastructure networks, we address the problem of optimal coverage of infrastructure networks using sensors whose sensing performance decays with distance. We show that this problem can be formulated as a continuous p-median problem on networks. The literature has addressed the discrete p-median problem on networks and in continuum domains, and the continuous p-median problem in continuum domains extensively. However, in-depth analysis of the continuous p-median problem on networks has been lacking. With the sensing performance model that decays with distance, each sensor covers a region equivalent to its Voronoi partition on the network in terms of the shortest path distance metric. Using Voronoi partitions, we define a directional partial derivative of the coverage metric with respect to a sensor’s location. We then propose a gradient descent algorithm to obtain a locally optimal solution with guaranteed convergence. The quality of an optimal solution depends on the choice of the initial configuration of sensors. We obtain an initial configuration using two approaches: by solving the discrete p-median problem on a lumped network and by random sampling. We consider two methods of random sampling: uniform sampling and D2-sampling. The first approach with the initial solution of the discrete p-median problem leads to the best coverage performance for large networks, but at the cost of high running time. We also observe that the gradient descent on the initial solution with the D2-sampling method yields a solution that is within at most 7% of the previous solution and with much shorter running time. 相似文献
9.
In this paper, we investigate the fault-tolerant capabilities of the k-ary n-cubes for even integer k with respect to the hamiltonian and hamiltonian-connected properties. The k-ary n-cube is a bipartite graph if and only if k is an even integer. Let F be a faulty set with nodes and/or links, and let k?3 be an odd integer. When |F|?2n-2, we show that there exists a hamiltonian cycle in a wounded k-ary n -cube. In addition, when |F|?2n-3, we prove that, for two arbitrary nodes, there exists a hamiltonian path connecting these two nodes in a wounded k-ary n-cube. Since the k-ary n -cube is regular of degree 2n, the degrees of fault-tolerance 2n-3 and 2n-2 respectively, are optimal in the worst case. 相似文献
10.
11.
Tag systems were invented by Emil Leon Post and proven recursively unsolvable by Marvin Minsky. These production systems have proved to be very useful in constructing small universal (Turing complete) systems for several different classes of computational systems, including Turing machines, and are thus important instruments for studying limits or boundaries of solvability and unsolvability. Although there are some results on tag systems and their limits of solvability and unsolvability, there are hardly any that consider both the shift number v and the number of symbols μ. This paper aims to contribute to research on limits of solvability and unsolvability for tag systems, taking into account these two parameters. The main result is the reduction of the 3n+1-problem to a surprisingly small tag system. It indicates that the present unsolvability line–defined in terms of μ and v–for tag systems might be significantly decreased. 相似文献
12.
We give an algorithm for constructing a basis and a multiplication table of a finite-dimensional finitely-presented Lie ring. Secondly, we give relations that are equivalent to the n-Engel condition, and only have to be checked for the elements of a basis of a Lie ring. We apply this to construct the freest t-generator Lie rings that satisfy the n-Engel condition, for (t,n)=(2,3),(3,3),(4,3),(2,4). 相似文献
13.
This paper deals with the multicriteria 0-1 knapsack problem (KP) with k-min objectives (MkMIN-KP) in which the first objective is of classical sum type and the remaining objectives are k-min objective functions. The k-min objectives are ordinal objectives, aiming at the maximization of the k th smallest objective coefficient in any feasible knapsack solution with at least k items in the knapsack. We develop efficient algorithms for the determination of the complete nondominated set of MkMIN-KP. 相似文献
14.
15.
16.
17.
18.
Recent observations of hundreds of hydrogen-rich magnetic white dwarf stars with magnetic fields up to 105 T (103 MG) have called for more comprehensive and accurate databases for wavelengths and oscillator strengths of the H atom in strong magnetic fields for all states evolving from the field-free levels with principal quantum numbers n≤10. We present a code to calculate the energy eigenvalues and wave functions of such states which is capable of covering the entire regime of field strengths B=0 T to B∼109 T. We achieve this high flexibility by using a two-dimensional finite element expansion of the wave functions in terms of B-splines in the directions parallel and perpendicular to the magnetic field, instead of using asymptotically valid basis expansions in terms of spherical harmonics or Landau orbitals. We have paid special attention to the automation of the program such that the data points for the magnetic field strengths at which the energy of a given state are calculated can be selected automatically. Furthermore, an elaborate method for varying the basis parameters is applied to ensure that the results reach a pre-selected precision, which also can be adjusted freely. Energies and wave functions are stored in a convenient format for further analysis, e.g. for the calculation of transition energies and oscillator strengths. The code has been tested to work for 300 states with an accuracy of better than 10−6 Rydberg across several symmetry subspaces over the entire regime of magnetic field strengths. 相似文献
19.
Continuous distance-based skyline queries in road networks 总被引:1,自引:0,他引:1
In recent years, the research community has introduced various methods for processing skyline queries in road networks. A skyline query retrieves the skyline points that are not dominated by others in terms of static and dynamic attributes (i.e., the road distance). This paper addresses the issue of efficiently processing continuous skyline queries in road networks. Two novel and important distance-based skyline queries are presented, namely, the continuous dε-skylinequery (Cdε-SQ) and the continuous k nearest neighbor-skyline query (Cknn-SQ ). A grid index is first designed to effectively manage the information of data objects and then two algorithms are proposed, the Cdε-SQalgorithm and the Cdε-SQ+algorithm , which are combined with the grid index to answer the Cdε-SQ. Similarly, the Cknn-SQ algorithm and the Cknn-SQ+algorithm are developed to efficiently process the Cknn-SQ. Extensive experiments using real road network datasets demonstrate the effectiveness and the efficiency of the proposed algorithms. 相似文献
20.
Isil Oz Haluk Rahmi Topcuoglu Mahmut Kandemir Oguz Tosun 《Journal of Parallel and Distributed Computing》2012
Continuously reducing transistor sizes and aggressive low power operating modes employed by modern architectures tend to increase transient error rates. Concurrently, multicore machines are dominating the architectural spectrum today in various application domains. These two trends require a fresh look at resiliency of multithreaded applications against transient errors from a software perspective. In this paper, we propose and evaluate a new metric called the Thread Vulnerability Factor (TVF). A distinguishing characteristic of TVF is that its calculation for a given thread (which is typically one of the threads of a multithreaded application) does not depend on its code alone, but also on the codes of the threads that share resources and data with that thread. As a result, we decompose TVF of a thread into two complementary parts: local and remote. While the former captures the TVF induced by the code of the target thread, the latter represents the vulnerability impact of the threads that interact with the target thread. We quantify the local and remote TVF values for three architectural components (register file, ALUs, and caches) using a set of ten multithreaded applications from the Parsec and Splash-2 benchmark suites. Our experimental evaluation shows that TVF values tend to increase as the number of cores increases, which means the system becomes more vulnerable as the core count rises. We further discuss how TVF metric can be employed to explore performance–reliability tradeoffs in multicores. Reliability-based analysis of compiler optimizations and redundancy-based fault tolerance are also mentioned as potential usages of our TVF metric. 相似文献