We consider a natural basic model for conflict-free routing of a group of k vehicles, a problem frequently encountered in many applications in transportation and logistics. There is a large gap between currently emplo...
详细信息
ISBN:
(纸本)9783642237195
We consider a natural basic model for conflict-free routing of a group of k vehicles, a problem frequently encountered in many applications in transportation and logistics. There is a large gap between currently employed routing schemes and the theoretical understanding of the problem. Previous approaches have either essentially no theoretical guarantees, or suffer from high running times, severely limiting their usability. So far, no efficient algorithm is known with a sub-linear (in k) approximation guarantee and without restrictions on the graph topology. We show that the conflict-free vehicle routing problem is hard to solve to optimality, even on paths. Building on a sequential routing scheme, we present an algorithm for trees with makespan bounded by O(OPT) + k. Combining this result with ideas known from packet routing, we obtain a first efficient algorithm with sub-linear approximation guarantee, namely an O(root k)-approximation. Additionally, a randomized algorithm leading to a makespan of O(polylog(k)). OPT + k is presented that relies on tree embedding techniques applied to a compacted version of the graph to obtain an approximation guarantee independent of the graph size.
The power dominating set (PDS) problem is the following extension of the well-known dominating set problem: find a smallest-size set of nodes S that power dominates all the nodes, where a node v is power dominated if ...
详细信息
ISBN:
(纸本)9783540742074
The power dominating set (PDS) problem is the following extension of the well-known dominating set problem: find a smallest-size set of nodes S that power dominates all the nodes, where a node v is power dominated if (1) v is in S or v has a neighbor in S, or (2) v has a neighbor omega such that w and all of its neighbors except v are power dominated. Note that rule (1) is the same as for the dominating set problem, and that rule (2) is a type of propagation rule that applies iteratively. We use n to denote the number of nodes. We show a hardness of approximation threshold of 2(log1-e) n in contrast to the logarithmic hardness for dominating set. This is the first result separating these two problem. We give an O(root n) approximation algorithm for planar graphs, and show that our methods cannot improve on this approximation guarantee. We introduce an extension of PDS called l-round PDS;for l = 1 this is the dominating set problem, and for >= n - 1 this is the PDS problem. Our hardness threshold for PDS also holds for l-round PDS for all l >= 4. We give a PTAS for the l-round PDS problem on planar graphs, for l = O(log n/log lon n). We study variants of the greedy algorithm, which is known to work well on covering problems, and show that the approximation guarantees can be circle minus(n), even on planar graphs. Finally, we initiate the study of PDS on directed graphs, and show the same hardness threshold of 2(log1-e) n for directed acyclic graphs.
This paper discusses new approximation algorithms for computing the Gromov hyperbolicity of an n-point discrete metric space. We give a (1 + epsilon)-approximation algorithm with running time (O) over tilde(epsilon (1...
详细信息
ISBN:
(纸本)9783642544231
This paper discusses new approximation algorithms for computing the Gromov hyperbolicity of an n-point discrete metric space. We give a (1 + epsilon)-approximation algorithm with running time (O) over tilde(epsilon (1)n(1 vertical bar omega)), where O(n(omega)) = O(n(2.373)) is the time complexity of matrix multiplications. Here an alpha-approximation delta' means delta' <= delta' <= alpha delta' for the Gromov hyperbolicity delta*. We also give a (2 + epsilon)-approximation algorithm with running time (O) over tilde(epsilon(-1)n(omega)). These are faster than the previous O(n((5+omega)/2))-time algorithm for the exact solution and the O(n((3+omega)/2))-time algorithm for a 2-approximation [Fournier, Ismail and Vigneron 2012], which directly perform (max, min)-product of matrices.
Genome rearrangements are events that affect large portions of a genome. When using the rearrangement distance to compare two genomes, one wants to find a minimum cost sequence of rearrangements that transforms one in...
详细信息
Genome rearrangements are events that affect large portions of a genome. When using the rearrangement distance to compare two genomes, one wants to find a minimum cost sequence of rearrangements that transforms one into another. Since we represent genomes as permutations, we can reduce this problem to the problem of sorting a permutation with a minimum cost sequence of rearrangements. In the traditional approach, we consider that all rearrangements are equally likely to occur and we set a unitary cost for all rearrangements. However, there are two variations of the problem motivated by the observation that rearrangements involving large segments of a genome rarely occur. The first variation adds a restriction to the rearrangement's length. The second variation uses a cost function based on the rearrangement's length. In this work, we present approximation algorithms for five problems combining both variations, that is, problems with a length-limit restriction and a cost function based on the rearrangement's length.
A fundamental issue in Web search is ranking search results based on user logs, since different users may have different preferences and intents with regards to a search query. Also, in many search query applications,...
详细信息
ISBN:
(纸本)9783642141614
A fundamental issue in Web search is ranking search results based on user logs, since different users may have different preferences and intents with regards to a search query. Also, in many search query applications, users tend to look at only the top part of the ranked result list in order to find relevant documents. The setting we consider contains various types of users, each of which is interested in a subset of the search results. The goal is to rank the search results of a query providing highly ranked relevant results. Our performance measure is the discounted cumulative gain which offers a graded relevance scale of documents in a search engine result set, and measures the usefulness (gain) of a document based on its position in the result list. Based on this measure, we suggest a general approach to developing approximation algorithms for ranking search results that captures different aspects of users' intents. We also take into account that the relevance of one document cannot be treated independently of the relevance of other documents in a collection returned by a search engine. We first consider the scenario where users are interested in only a single search result (e.g., navigational queries). We then develop a polynomial time approximation scheme for this case. We further consider the general case where users have different requirements on the number of search results, and develop efficient approximation algorithms. Finally, we consider the problem of choosing the top k out of n search results and show that for tins problem (1 - 1/e) is indeed the best approximation factor achievable, thus separating the approximability of the two versions of the problem.
The asymmetric postman problem is a generalization of the Chinese postman problem in which the edge-traversal costs are asymmetric. The problem is to compute a shortest tour that traverses every edge of a given graph ...
详细信息
ISBN:
(纸本)0898714346
The asymmetric postman problem is a generalization of the Chinese postman problem in which the edge-traversal costs are asymmetric. The problem is to compute a shortest tour that traverses every edge of a given graph at least once, and it is known to be NP-hard. An approximation algorithm with a performance ratio of 3/2 for the asymmetric postman problem is presented.
This paper considers the problem of finding the shortest tour to cover a given set of inverted cone views with apex angle a and height H when their apex points lie on a planar surface. This is a novel variant of the 3...
详细信息
ISBN:
(纸本)9781538630815
This paper considers the problem of finding the shortest tour to cover a given set of inverted cone views with apex angle a and height H when their apex points lie on a planar surface. This is a novel variant of the 3D Traveling Salesman Problem with intersecting Neighborhoods (TSPN) called Cone-TSPN. When the cones are allowed to tilt by an angle epsilon we have the tilted Cone-TSPN problem, to which we present an algorithm that returns a solution with an approximation ratio of O (1+tan alpha / 1-tan epsilon tan alpha (1 + log max(H)/min(H)). We demonstrate through simulations that our algorithm can be implemented in a practical way and by exploiting the structure of the cones we can achieve shorter tours. Finally, we present results from covering a reflective surface (lake area) that shows the importance of selecting different view angles under strong sunlight specularities.
We prove that the edges of every graph of bounded (Euler) genus can be partitioned into any prescribed number k of pieces such that contracting any piece results in a graph of bounded treewidth (where the bound depend...
详细信息
ISBN:
(纸本)9780898716245
We prove that the edges of every graph of bounded (Euler) genus can be partitioned into any prescribed number k of pieces such that contracting any piece results in a graph of bounded treewidth (where the bound depends on k). This decomposition result parallels an analogous, simpler result for edge deletions instead of contractions, obtained in [Bak94, Epp00, DDO(+)04, DHK05], and it generalizes a similar result for "compression" (a variant of contraction) in planar graphs [Kle05]. Our decomposition result is a powerful tool for obtaining PTASs for contraction-closed problems (whose optimal solution only improves under contraction), a much more general class than minor-closed problems. We prove that any contraction-closed problem satisfying just a few simple conditions has a PTAS in bounded-genus graphs. In particular, our framework yields PTASs for the weighted Traveling Salesman Problem and for minimum-weight c-edge-connected submultigraph on bounded-genus graphs, improving and generalizing previous algorithms of [GKP95, AGK(+)98, Kle05, Gri00, CGSZ04, BCGZ05]. We also highlight the only main difficulty in extending our results to general H-minor-free graphs.
We consider the problem of embedding general metrics into trees. We give the first non-trivial approximation algorithm for minimizing the multiplicative distortion. Our algorithm produces an embedding with distortion ...
详细信息
ISBN:
(纸本)9780898716245
We consider the problem of embedding general metrics into trees. We give the first non-trivial approximation algorithm for minimizing the multiplicative distortion. Our algorithm produces an embedding with distortion (clog n)(O(root log Delta)), where c is the optimal distortion, and A is the spread of the metric (i.e. the ratio of the diameter over the minimum distance). We give an improved O(1)-approximation algorithm for the case where the input is the shortest path metric over an unweighted graph. Moreover, we show that by composing our approximation algorithm for embedding general metrics into trees, with the approximation algorithm of [BCIS05] for embedding trees into the line, we obtain an improved approximation algorithm for embedding general metrics into the line. We also provide almost tight bounds for the relation between embedding into trees and embedding into spanning subtrees. We show that for any unweighted graph G, the ratio of the distortion required to embed G into a spanning subtree, over the distortion of an optimal tree embedding of G, is at most O(log n). We complement this bound by exhibiting a family of graphs for which the ratio is Omega(log n/log log n).
Noncommutative constraint satisfaction problems (CSPs) are higher-dimensional operator extensions of classical CSPs. Their approximability remains largely unexplored. A notable example of a noncommutative CSP that is ...
详细信息
ISBN:
(纸本)9798331516758;9798331516741
Noncommutative constraint satisfaction problems (CSPs) are higher-dimensional operator extensions of classical CSPs. Their approximability remains largely unexplored. A notable example of a noncommutative CSP that is not solvable in polynomial time is NC-Max-3-Cut. We present a 0.864-approximation algorithm for this problem. Our approach extends to a broader class of both classical and noncommutative CSPs. We introduce three key concepts: approximate isometry, relative distribution, and generalized anticommutation, which may be of independent interest.
暂无评论