共查询到20条相似文献,搜索用时 31 毫秒
1.
The minimum clique partition (MCP) problem is that of partitioning the vertex set of a given graph into a minimum number of
cliques. Given n points in the plane, the corresponding unit disk graph (UDG) has these points as vertices, and edges connecting points at
distance at most 1. MCP in UDGs is known to be NP-hard and several constant factor approximations are known, including a recent
PTAS. We present two improved approximation algorithms for MCP in UDGs with a realization: (I) A polynomial time approximation
scheme (PTAS) running in time nO(1/e2){n^{O(1/\varepsilon^2)}}. This improves on a previous PTAS with nO(1/e4){n^{O(1/\varepsilon^4)}} running time by Pirwani and Salavatipour (arXiv:0904.2203v1, 2009). (II) A randomized quadratic-time algorithm with approximation ratio 2.16. This improves on a ratio 3 algorithm with O(n
2) running time by Cerioli et al. (Electron. Notes Discret. Math. 18:73–79, 2004). 相似文献
2.
When homogeneous sensors are deployed into a three-dimensional space instead of a plane, the mathematical model for the sensor
network is a unit ball graph instead of a unit disk graph. It is known that for the minimum connected dominating set in unit
disk graph, there is a polynomial time approximation scheme (PTAS). However, that construction cannot be extended to obtain
a PTAS for unit ball graph. In this paper, we will introduce a new construction, which gives not only a PTAS for the minimum
connected dominating set in unit ball graph, but also improves running time of PTAS for unit disk graph. 相似文献
3.
Magnús M. Halldrsson Guy Kortsarz 《Journal of Algorithms in Cognition, Informatics and Logic》2002,42(2):334
We study graph multicoloring problems, motivated by the scheduling of dependent jobs on multiple machines. In multicoloring problems, vertices have lengths which determine the number of colors they must receive, and the desired coloring can be either contiguous (nonpreemptive schedule) or arbitrary (preemptive schedule). We consider both the sum-of-completion times measure, or the sum of the last color assigned to each vertex, as well as the more common makespan measure, or the number of colors used. In this paper, we study two fundamental classes of graphs: planar graphs and partial k-trees. For both classes, we give a polynomial time approximation scheme (PTAS) for the multicoloring sum, for both the preemptive and nonpreemptive cases. On the other hand, we show the problem to be strongly NP-hard on planar graphs, even in the unweighted case, known as the sum coloring problem. For a nonpreemptive multicoloring sum of partial k-trees, we obtain a fully polynomial time approximation scheme. This is based on a pseudo-polynomial time algorithm that holds for a general class of cost functions. Finally, we give a PTAS for the makespan of a preemptive multicoloring of partial k-trees that uses only O(log n) preemptions. These results are based on several properties of multicolorings and tools for manipulating them, which may be of more general applicability. 相似文献
4.
Hans L. Bodlaender Corinne Feremans Alexander Grigoriev Eelko Penninkx Ren Sitters Thomas Wolle 《Computational Geometry》2009,42(9):939-951
In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into “rooms”, one has to find the minimum length tree along the edges of the decomposition such that every room is incident to a vertex of the tree. We show that the problem is strongly NP-hard and give a subexponential time exact algorithm. For the special case when the room connectivity graph is k-outerplanar the algorithm running time becomes cubic. We develop a polynomial time approximation scheme for the case when all rooms are fat and have nearly the same size. When rooms are fat but are of varying size we give a polynomial time constant factor approximation algorithm. 相似文献
5.
We consider the problem of scheduling a set of jobs with different release times on parallel machines so as to minimize the makespan of the schedule. The machines have the same processing speed, but each job is compatible with only a subset of those machines. The machines can be linearly ordered such that a higher-indexed machine can process all those jobs that a lower-indexed machine can process. We present an efficient algorithm for this problem with a worst-case performance ratio of 2. We also develop a polynomial time approximation scheme (PTAS) for the problem, as well as a fully polynomial time approximation scheme (FPTAS) for the case in which the number of machines is fixed. 相似文献
6.
A. A. Ageev V. P. Il’ev A. V. Kononov A. S. Talevnin 《Journal of Applied and Industrial Mathematics》2007,1(1):1-8
The computational complexity of the graph approximation problem is investigated. It is shown that the different variants of this problem are NP-hard both for undirected and directed graphs. A polynomial-time approximation scheme (PTAS) for one of the variants is presented. 相似文献
7.
Hardness results for the center and median string problems under the weighted and unweighted edit distances 总被引:1,自引:0,他引:1
Given a finite set of strings, the Median String problem consists in finding a string that minimizes the sum of the edit distances to the strings in the set. Approximations of the median string are used in a very broad range of applications where one needs a representative string that summarizes common information to the strings of the set. It is the case in classification, in speech and pattern recognition, and in computational biology. In the latter, Median String is related to the key problem of multiple alignment. In the recent literature, one finds a theorem stating the NP-completeness of the Median String for unbounded alphabets. However, in the above mentioned areas, the alphabet is often finite. Thus, it remains a crucial question whether the Median String problem is NP-complete for bounded and even binary alphabets. In this work, we provide an answer to this question and also give the complexity of the related Center String problem. Moreover, we study the parameterized complexity of both problems with respect to the number of input strings. In addition, we provide an algorithm to compute an optimal center under a weighted edit distance in polynomial time when the number of input strings is fixed. 相似文献
8.
9.
本文考虑基于波分复用技术 (WDM)的光学网络中的排序与波长分配问题 .在波长数目固定的情况下 ,我们证明此问题是NP 困难问题 ,并且给出一个多项式时间近似方案 .若波长数目不固定 ,我们证明此问题不存在多项式时间近似方案 相似文献
10.
问题Pm|rj,B|∑Cj的多项式时间近似算法 总被引:2,自引:0,他引:2
本文针对同型机分批排序问题Pm|rj,B|∑Cj进行了研究,给出了该问题在批容量B及机器台数m为常数情况下的多项式时间近似算法(以下简称PTAS);在B为常数时设计出了问题1|rj,B|∑WjCj的计算时间更少的PTAS. 相似文献
11.
Bang Ye Wu Kun-Mao Chao Chuan Yi Tang 《Journal of Algorithms in Cognition, Informatics and Logic》2000,36(2):182
Given an undirected graph with nonnegative edge lengths and nonnegative vertex weights, the routing requirement of a pair of vertices is assumed to be the product of their weights. The routing cost for a pair of vertices on a given spanning tree is defined as the length of the path between them multiplied by their routing requirement. The optimal product-requirement communication spanning tree is the spanning tree with minimum total routing cost summed over all pairs of vertices. This problem arises in network design and computational biology. For the special case that all vertex weights are identical, it has been shown that the problem is NP-hard and that there is a polynomial time approximation scheme for it. In this paper we show that the generalized problem also admits a polynomial time approximation scheme. 相似文献
12.
We consider two problems: given a collection of n fat objects in a fixed dimension, (1) ( packing) find the maximum subcollection of pairwise disjoint objects, and (2) ( piercing) find the minimum point set that intersects every object. Recently, Erlebach, Jansen, and Seidel gave a polynomial-time approximation scheme (PTAS) for the packing problem, based on a shifted hierarchical subdivision method. Using shifted quadtrees, we describe a similar algorithm for packing but with a smaller time bound. Erlebach et al.'s algorithm requires polynomial space. We describe a different algorithm, based on geometric separators, that requires only linear space. This algorithm can also be applied to piercing, yielding the first PTAS for that problem. 相似文献
13.
14.
Monaldo Mastrolilli 《Discrete Applied Mathematics》2006,154(4):640-649
We address the classical knapsack problem and a variant in which an upper bound is imposed on the number of items that can be selected. We show that appropriate combinations of rounding techniques yield novel and more powerful ways of rounding. Moreover, we present a linear-storage polynomial time approximation scheme (PTAS) and a fully polynomial time approximation scheme (FPTAS) that compute an approximate solution, of any fixed accuracy, in linear time. These linear complexity bounds give a substantial improvement of the best previously known polynomial bounds [A. Caprara, et al., Approximation algorithms for knapsack problems with cardinality constraints, European J. Oper. Res. 123 (2000) 333-345]. 相似文献
15.
On spanning tree problems with multiple objectives 总被引:4,自引:0,他引:4
We investigate two versions of multiple objective minimum spanning tree problems defined on a network with vectorial weights. First, we want to minimize the maximum ofQ linear objective functions taken over the set of all spanning trees (max-linear spanning tree problem, ML-ST). Secondly, we look for efficient spanning trees (multi-criteria spanning tree problem, MC-ST).Problem ML-ST is shown to be NP-complete. An exact algorithm which is based on ranking is presented. The procedure can also be used as an approximation scheme. For solving the bicriterion MC-ST, which in the worst case may have an exponential number of efficient trees, a two-phase procedure is presented. Based on the computation of extremal efficient spanning trees we use neighbourhood search to determine a sequence of solutions with the property that the distance between two consecutive solutions is less than a given accuracy.Partially supported by Deutsche Forschungsgemeinschaft and HCº Contract no. ERBCHRXCT 930087.Partially supported by Alexander von Humboldt-Stiftung. 相似文献
16.
Bansal and Sviridenko [N. Bansal, M. Sviridenko, New approximability and inapproximability results for 2-dimensional bin packing, in: Proceedings of the 15th Annual ACM–SIAM Symposium on Discrete Algorithms, SODA, 2004, pp. 189–196] proved that there is no asymptotic PTAS for 2-dimensional Orthogonal Bin Packing (without rotations), unless P=NP. We show that similar approximation hardness results hold for several 2- and 3-dimensional rectangle packing and covering problems even if rotations by ninety degrees are allowed. Moreover, for some of these problems we provide explicit lower bounds on asymptotic approximation ratio of any polynomial time approximation algorithm. Our hardness results apply to the most studied case of 2-dimensional problems with unit square bins, and for 3-dimensional strip packing and covering problems with a strip of unit square base. 相似文献
17.
Alexandr Andoni Constantinos Daskalakis Avinatan Hassidim Sebastien Roch 《Stochastic Processes and their Applications》2012
We consider the trace reconstruction problem on a tree (TRPT): a binary sequence is broadcast through a tree channel where we allow substitutions, deletions, and insertions; we seek to reconstruct the original sequence from the sequences received at the leaves. The TRPT is motivated by the multiple sequence alignment problem in computational biology. We give a simple recursive procedure giving strong reconstruction guarantees at low mutation rates. To our knowledge, this is the first rigorous trace reconstruction result on a tree in the presence of indels. 相似文献
18.
V. S. Vladimirov 《Theoretical and Mathematical Physics》2011,167(2):539-546
We review several purely mathematical results concerning boundary value problems for nonlinear pseudodifferential equations
for p-adic closed and open strings in the tree approximation in the case d = 1. For the solutions of these problems, we present formulas establishing the relations between the numbers of their zeros,
the multiplicities of the zeros, and the numbers indicating how many times the solutions change sign. 相似文献
19.
Leah Epstein Tamir Tassa 《Journal of Algorithms in Cognition, Informatics and Logic》2003,48(2):360-384
We present a general framework for vector assignment problems. In such problems one aims at assigning n input vectors to m machines such that the value of a given target function is minimized. While previous approaches concentrated on simple target functions such as max–max, the general approach presented here enables us to design a polynomial time approximation scheme (PTAS) for a wide class of target functions. In particular, thanks to a novel technique of preprocessing the input vectors, we are able to deal with nonmonotone target functions. Such target functions arise in vector assignment problems in the context of video transmission and broadcasting. 相似文献
20.
Batch sizing and job sequencing on a single machine 总被引:7,自引:0,他引:7
E. G. Coffman Jr. M. Yannakakis M. J. Magazine C. Santos 《Annals of Operations Research》1990,26(1):135-147
We study a single-machine scheduling problem in which the items to be processed have to be batched as well as sequenced. Since processed items become available in batches, flow times are defined to be the same for all items in the same batch. A constant set-up delay is incurred between consecutive batches. For any fixed, but arbitrary item sequence, we present an algorithm that finds a sequence of batches such that the total flow time of the items is minimized; we prove that for a set ofn items, the algorithm runs inO(n) time. We show that, among all sequences, the one leading to the minimum flow time has the items in non-decreasing order of running times. Thus, the optimal algorithm for the combined problem, called thebatch-sizing problem, runs inO(n logn) time. We also prove that this algorithm yields an improved solution to a scheduling problem recently studied by Baker [1]. 相似文献