A new exact algorithm is proposed to compute the 3D geometric moments of a homogeneous shape defined by an unstructured triangulation of its surface. This algorithm relies on the analytical integration of the moments ...
详细信息
A new exact algorithm is proposed to compute the 3D geometric moments of a homogeneous shape defined by an unstructured triangulation of its surface. This algorithm relies on the analytical integration of the moments on tetrahedra defined by the surface triangles and a central point and on a set of recurrent relationships between the corresponding integrals, and achieves linear running time complexities with respect to the number of triangles in the surface mesh and with respect to the number of moments that are computed. This effectively reduces the complexity for computing moments up to order N from N-6 to N-3 with respect to the fastest previously proposed exact algorithm.
Given three convex polygons having n vertices in total in the plane, we consider the problem of finding a translation for each polygon such that the translated polygons are pairwise disjoint and the area or the perime...
详细信息
Given three convex polygons having n vertices in total in the plane, we consider the problem of finding a translation for each polygon such that the translated polygons are pairwise disjoint and the area or the perimeter of their convex hull is minimized. We present the first O(n(2))-time algorithm that finds optimal translations of input polygons using O(n(2)) space for this problem. (C) 2015 Elsevier B.V. All rights reserved.
In this paper, we develop efficient exact and approximate algorithms for computing a maximum independent set in random graphs. In a random graph G, each pair of vertices are joined by an edge with a probability p, whe...
详细信息
In this paper, we develop efficient exact and approximate algorithms for computing a maximum independent set in random graphs. In a random graph G, each pair of vertices are joined by an edge with a probability p, where p is a constant between 0 and 1. We show that a maximum independent set in a random graph that contains n vertices can be computed in expected computation time 2(O(log22 n)). In addition, we show that, with high probability, the parameterized independent set problem is fixed parameter tractable in random graphs and the maximum independent set in a random graph in n vertices can be approximated within a ratio of 2n/2(root log2 n) in expected polynomial time.
The problem is, given a set of n vectors in a d-dimensional normed space, find a subset with the largest length of the sum vector. We prove that, in the case of the lp norm, the problem is APX-complete for any p is an...
详细信息
The problem is, given a set of n vectors in a d-dimensional normed space, find a subset with the largest length of the sum vector. We prove that, in the case of the lp norm, the problem is APX-complete for any p is an element of [1, 2] and is not in APX if p is an element of (2, infinity). In the case of an arbitrary norm, we propose an algorithm which finds an optimal solution in time 0 (n(d-1)(d + logn)), improving previously known algorithms. In particular, the two-dimensional problem can be solved in nearly linear time. We also present an improved algorithm for the cardinality-constrained version of the problem with running time 0 (dn(d+1)). In the two-dimensional case, this version is shown to be solvable in nearly quadratic time. (C) 2018 Elsevier B.V. All rights reserved.
We study the strip packing problem, in which a set of two-dimensional rectangular items has to be packed in a rectangular strip of fixed width and infinite height, with the aim of minimizing the height used. The probl...
详细信息
We study the strip packing problem, in which a set of two-dimensional rectangular items has to be packed in a rectangular strip of fixed width and infinite height, with the aim of minimizing the height used. The problem is important because it models a large number of real-world applications, including cutting operations where stocks of materials such as paper or wood come in large rolls and have to be cut with minimum waste, scheduling problems in which tasks require a contiguous subset of identical resources, and container loading problems arising in the transportation of items that cannot be stacked one over the other. The strip packing problem has been attacked in the literature with several heuristic and exact algorithms, nevertheless, benchmark instances of small size remain unsolved to proven optimality. In this paper we propose a new exact method that solves a large number of the open benchmark instances within a limited computational effort. Our method is based on a Benders' decomposition, in which in the master we cut items into unit-width slices and pack them contiguously in the strip, and in the slave we attempt to reconstruct the rectangular items by fixing the vertical positions of their unit-width slices. If the slave proves that the reconstruction of the items is not possible, then a cut is added to the master, and the algorithm is reiterated. We show that both the master and the slave are strongly N P-hard problems and solve them with tailored preprocessing, lower and upper bounding techniques, and exact algorithms. We also propose several new techniques to improve the standard Benders' cuts, using the so-called combinatorial Benders' cuts, and an additional lifting procedure. Extensive computational tests show that the proposed algorithm provides a substantial breakthrough with respect to previously published algorithms.
Background: Protein structure comparison is a key problem in bioinformatics. There exist several methods for doing protein comparison, being the solution of the Maximum Contact Map Overlap problem (MAX-CMO) one of the...
详细信息
Background: Protein structure comparison is a key problem in bioinformatics. There exist several methods for doing protein comparison, being the solution of the Maximum Contact Map Overlap problem (MAX-CMO) one of the alternatives available. Although this problem may be solved using exact algorithms, researchers require approximate algorithms that obtain good quality solutions using less computational resources than the formers. Results: We propose a variable neighborhood search metaheuristic for solving MAX-CMO. We analyze this strategy in two aspects: 1) from an optimization point of view the strategy is tested on two different datasets, obtaining an error of 3.5%(over 2702 pairs) and 1.7% (over 161 pairs) with respect to optimal values;thus leading to high accurate solutions in a simpler and less expensive way than exact algorithms;2) in terms of protein structure classification, we conduct experiments on three datasets and show that is feasible to detect structural similarities at SCOP's family and CATH's architecture levels using normalized overlap values. Some limitations and the role of normalization are outlined for doing classification at SCOP's fold level. Conclusion: We designed, implemented and tested. a new tool for solving MAX-CMO, based on a well-known metaheuristic technique. The good balance between solution's quality and computational effort makes it a valuable tool. Moreover, to the best of our knowledge, this is the first time the MAX-CMO measure is tested at SCOP's fold and CATH's architecture levels with encouraging results. Software is available for download at http://***/jrgonzalez/msvns4maxcmo.
We look at the computational complexity of 2-dimensional geometric optimization problems on a finite point set with respect to the number of inner points (that is, points in the interior of the convex hull). As a case...
详细信息
We look at the computational complexity of 2-dimensional geometric optimization problems on a finite point set with respect to the number of inner points (that is, points in the interior of the convex hull). As a case study, we consider the minimum weight triangulation problem. Finding a minimum weight triangulation for a set of n points in the plane is not known to be NP-hard nor solvable in polynomial time, but when the points are in convex position, the problem, can be solved in O(n(3)) time by dynamic programming. We extend the dynamic programming approach to the general problem and describe an exact algorithm which runs in O(6(k) n(5) log n) time where n is the total number of input points and k is the number of inner points. If k is taken as a parameter, this is a fixed-parameter algorithm. It also shows that the problem can be solved in polynomial time if k = O(log n). In fact, the algorithm works not only for convex polygons, but also for simple polygons with k inner points. (C) 2006 Elsevier B.V. All rights reserved.
This paper considers a new form of the Steiner tree problem that is more practical and reliable,which we call Reliable Steiner Tree(RST)*** authors give a detailed definition for this new problem and design both an ex...
详细信息
This paper considers a new form of the Steiner tree problem that is more practical and reliable,which we call Reliable Steiner Tree(RST)*** authors give a detailed definition for this new problem and design both an exact algorithm and an approximation algorithm for *** definition is based on the reliability of full components instead of Steiner *** task is thus to find the most reliable full components to make up an optimum reliable Steiner *** exact algorithm designed for this problem utilizes a dynamic programming *** approximation algorithm designed in this paper exploits a local search strategy that looks for the best full component according to a selection function at a time.
We show an 0*((l + 1)(n))-time algorithm for the channel assignment problem, where l is the maximum edge weight. This improves on the previous o*((l + 2)(n))-time algorithm by Kral (2005) [1], as well as algorithms fo...
详细信息
We show an 0*((l + 1)(n))-time algorithm for the channel assignment problem, where l is the maximum edge weight. This improves on the previous o*((l + 2)(n))-time algorithm by Kral (2005) [1], as well as algorithms for important special cases, like L(2, 1)-labeling. For the latter problem, our algorithm works in 0*(3(n)) time. The progress is achieved by applying the fast zeta transform in combination with the inclusion-exclusion principle. (C) 2011 Elsevier B.V. All rights reserved.
The b-chromatic number of a graph G, chi(b) (G), is the largest integer k such that G has a k-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of th...
详细信息
The b-chromatic number of a graph G, chi(b) (G), is the largest integer k such that G has a k-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other color classes. In the b-CHROMATIC NUMBER problem, the objective is to decide whether X-b(G) >= k. Testing whether Xb(G) = (G) 1, where A(G) is the maximum degree of a graph, itself is NP-complete even for connected bipartite graphs (Kratochvil, Tuza and Voigt, WG 2002). We show that b-CHROMATIC NUMBER is W[1]-hard when parameterized by k, resolving the open question posed by Havet and Sampaio (algorithmica 2013). When k = (G) 1, we design an algorithm for b-CHROMATIC NUMBER running in time 200'2 log k) n ro(i) Finally, we show that b-CHROMATIC NUMBER for an n-vertex graph can be solved in time 0(3nn4logn). (C) 2016 Elsevier Inc. All rights reserved.
暂无评论