Search

Although, the Hamiltonicity of solid grid graphs are polynomial-time decidable, the complexity of the longest cycle problem in these graphs is still open. In this paper, by presenting a linear-time constant-factor approximation algorithm, we show that the longest cycle problem in solid grid graphs is in APX. More precisely, our algorithm finds a cycle of length at least 2 n 3 + 1 in 2-connected n -node solid grid graphs. [ABSTRACT FROM AUTHOR]

Convex hulls are fundamental geometric tools used in a number of algorithms. This paper presents a fast, simple to implement and robust Smart Convex Hull (S-CH) algorithm for computing the convex hull of a set of points in E 3 . This algorithm is based on “spherical” space subdivision. The main idea of the S-CH algorithm is to eliminate as many input points as possible before the convex hull construction. The experimental results show that only a very small number of points are used for the final convex hull calculation. Experiments made also proved that the proposed S-CH algorithm achieves a better time complexity in comparison with other algorithms in E 3 . [ABSTRACT FROM AUTHOR]

Abstract: In computational cognitive science, many cognitive processes seem to be successfully modeled as Bayesian computations. Yet, many such Bayesian computations have been proven to be computationally intractable (NP-hard) for unconstrained input domains, even if only an approximate solution is sought. This computational complexity result seems to be in strong contrast with the ease and speed with which humans can typically make the inferences that are modeled by Bayesian models. This contrast—between theory and practice—poses a considerable theoretical challenge for computational cognitive modelers: How can intractable Bayesian computations be transformed into computationally plausible ‘approximate’ models of human cognition? In this paper, three candidate notions of ‘approximation’ are discussed, each of which has been suggested in the cognitive science literature. We will sketch how (parameterized) computational complexity analyses can yield model variants that are tractable and which can serve as the basis of computationally plausible models of cognition. [Copyright &y& Elsevier]

Abstract: One of the most relevant topics in the analysis of biological networks is the identification of functional motifs inside a network. A recent approach introduced in literature, called Graph Motif, represents the network as a vertex-colored graph, and the motif as a multiset of colors. An occurrence of a motif in a vertex-colored graph is a connected induced subgraph of whose vertex set is colored exactly as . In this paper we investigate three different variants of the Graph Motif problem. The first two variants, Minimum Adding Motif (Min-Add Graph Motif) and Minimum Substitution Motif (Min-Sub Graph Motif), deal with approximate occurrences of a motif in the graph, while the third variant, Constrained Graph Motif (CGM), constrains the motif to contain a given set of vertices. We investigate the computational and parameterized complexity of the three problems. We show that Min-Add Graph Motifand Min-Sub Graph Motifare both NP-hard, even when is a set, and the graph is a tree with maximum degree in which each color appears at most twice. Then, we show that Min-Sub Graph Motifis fixed-parameter tractable when parameterized by the size of . Finally, we consider the parameterized complexity of the CGMproblem; we give a fixed-parameter algorithm for graphs of bounded treewidth, and show that the problem is W[2]-hard when parameterized by , even if the input graph has diameter . [Copyright &y& Elsevier]

Abstract: We introduce a new type of meshes called 5–6–7 meshes. For many mesh processing tasks, low- or high-valence vertices are undesirable. At the same time, it is not always possible to achieve complete vertex valence regularity, i.e. to only have valence-6 vertices. A 5–6–7 mesh is a closed triangle mesh where each vertex has valence 5, 6, or 7. An intriguing question is whether it is always possible to convert an arbitrary mesh into a 5–6–7 mesh. In this paper, we answer the question in the positive. We present a 5–6–7 remeshing algorithm which converts a closed triangle mesh with arbitrary genus into a 5–6–7 mesh which (a) closely approximates the original mesh geometrically, e.g. in terms of feature preservation and (b) has a comparable vertex count as the original mesh. We demonstrate the results of our remeshing algorithm on meshes with sharp features and different topology and complexity. [Copyright &y& Elsevier]

Abstract: In this paper we consider imprecise terrains, that is, triangulated terrains with a vertical error interval in the vertices. In particular, we study the problem of removing as many local extrema (minima and maxima) as possible from the terrain; that is, finding an assignment of one height to each vertex, within its error interval, so that the resulting terrain has minimum number of local extrema. We show that removing only minima or only maxima can be done optimally in time, for a terrain with n vertices. Interestingly, however, the problem of finding a height assignment that minimizes the total number of local extrema (minima as well as maxima) is NP-hard, and is even hard to approximate within a factor of unless . Moreover, we show that even a simplified version of the problem where we can have only three different types of intervals for the vertices is already NP-hard, a result we obtain by proving hardness of a special case of 2-Disjoint Connected Subgraphs, a problem that has lately received considerable attention from the graph-algorithms community. [Copyright &y& Elsevier]

Abstract: The voting rules proposed by Dodgson and Young are both designed to find an alternative closest to being a Condorcet winner, according to two different notions of proximity; the score of a given alternative is known to be hard to compute under either rule. In this paper, we put forward two algorithms for approximating the Dodgson score: a combinatorial, greedy algorithm and an LP-based algorithm, both of which yield an approximation ratio of , where m is the number of alternatives and is the st harmonic number. We also prove that our algorithms are optimal within a factor of 2, unless problems in have quasi-polynomial-time algorithms. Despite the intuitive appeal of the greedy algorithm, we argue that the LP-based algorithm has an advantage from a social choice point of view. Further, we demonstrate that computing any reasonable approximation of the ranking produced by Dodgsonʼs rule is -hard. This result provides a complexity-theoretic explanation of sharp discrepancies that have been observed in the social choice theory literature when comparing Dodgson elections with simpler voting rules. Finally, we show that the problem of calculating the Young score is -hard to approximate by any factor. This leads to an inapproximability result for the Young ranking. [Copyright &y& Elsevier]

Abstract: The Consensus Clustering problem has been introduced as an effective way to analyze the results of different microarray experiments (Filkov and Skiena (2004a,b) . The problem asks for a partition that summarizes a set of input partitions (each corresponding to a different microarray experiment) under a simple and intuitive cost. The problem on instances with two input partitions has a simple polynomial time algorithm, but it becomes APX-hard on instances with three input partitions. The quest for defining the boundary between tractable and intractable instances leads to the investigation of the restriction of Consensus Clustering when the output partition contains a fixed number of sets. In this paper, we give a randomized polynomial time approximation scheme for such problems, while proving its NP-hardness even for 2 output partitions, therefore definitively settling the approximation complexity of the problem. [Copyright &y& Elsevier]

Abstract: In comparative genomics, the first step of sequence analysis is usually to decompose two or more genomes into syntenic blocks that are segments of homologous chromosomes. For the reliable recovery of syntenic blocks, noise and ambiguities in the genomic maps need to be removed first. Maximal Strip Recovery (MSR) is an optimization problem proposed by Zheng, Zhu, and Sankoff for reliably recovering syntenic blocks from genomic maps in the midst of noise and ambiguities. Given genomic maps as sequences of gene markers, the objective of MSR- is to find subsequences, one subsequence of each genomic map, such that the total length of syntenic blocks in these subsequences is maximized. For any constant , a polynomial-time -approximation for MSR- was previously known. In this paper, we show that for any , MSR- is APX-hard, even for the most basic version of the problem in which all gene markers are distinct and appear in positive orientation in each genomic map. Moreover, we provide the first explicit lower bounds on approximating MSR- for all . In particular, we show that MSR- is NP-hard to approximate within . From the other direction, we show that the previous -approximation for MSR- can be optimized into a polynomial-time algorithm even if is not a constant but is part of the input. We then extend our inapproximability results to several related problems including CMSR-, -gap-MSR-, and -gap-CMSR-. [Copyright &y& Elsevier]

Abstract: Simulation distances are essentially approximations of simulation which provide a measure of the extent by which behaviors in systems are inequivalent. In this paper, we consider the general quantitative model of weighted transition systems, where transitions are labeled with elements of a finite metric space. We study the so-called point-wise and accumulating simulation distances which provide extensions to the well-known Boolean notion of simulation on labeled transition systems. We introduce weighted process algebras for finite and regular behavior and offer sound and (approximate) complete inference systems for the proposed simulation distances. We also settle the algorithmic complexity of computing the simulation distances. [Copyright &y& Elsevier]

Abstract: In this paper we propose a novel approach to decentralised coordination, that is able to efficiently compute solutions with a guaranteed approximation ratio. Our approach is based on a factor graph representation of the constraint network. It builds a tree structure by eliminating dependencies between the functions and variables within the factor graph that have the least impact on solution quality. It then uses the max-sum algorithm to optimally solve the resulting tree structured constraint network, and provides a bounded approximation specific to the particular problem instance. In addition, we present two generic pruning techniques to reduce the amount of computation that agents must perform when using the max-sum algorithm. When this is combined with the above mentioned approximation algorithm, the agents are able to solve decentralised coordination problems that have very large action spaces with a low computation and communication overhead. We empirically evaluate our approach in a mobile sensor domain, where mobile agents are used to monitor and predict the state of spatial phenomena (e.g., temperature or gas concentration). Such sensors need to coordinate their movements with their direct neighbours to maximise the collective information gain, while predicting measurements at unobserved locations. When applied in this domain, our approach is able to provide solutions which are guaranteed to be within 2% of the optimal solution. Moreover, the two pruning techniques are extremely effective in decreasing the computational effort of each agent by reducing the size of the search space by up to 92%. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we present a new algorithm to solve general linear fifth-order boundary value problems (BVPs) in the reproducing kernel space . Representation of the exact solution is given in the reproducing kernel space. Its approximate solution is obtained by truncating the -term of the exact solution. Some examples are displayed to demonstrate the computational efficiency of the method. [Copyright &y& Elsevier]

Abstract: In this paper, we consider single-machine scheduling problems under the job rejection constraint. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on the single machine. However, the total rejection penalty of the rejected jobs cannot exceed a given upper bound. The objective is to find a schedule such that a given criterion is minimized, where is a non-decreasing function on the completion times of the accepted jobs. We analyze the computational complexities of the problems for distinct objective functions and present pseudo-polynomial-time algorithms. In addition, we provide a fully polynomial-time approximation scheme for the makespan problem with release dates. For other objective functions related to due dates, we point out that there is no approximation algorithm with a bounded approximation ratio. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]