| 1. |
- Berman, Piotr, et al.
(författare)
-
Exact and approximation algorithms for geometric and capacitated set cover problems
- 2012
-
Ingår i: Computing and Combinatorics / Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783642140310 ; 6196, s. 295-310
-
Konferensbidrag (refereegranskat)abstract
- First, we study geometric variants of the standard set cover motivated by assignment of directional antenna and shipping with deadlines, providing the first known polynomial-time exact solutions. Next, we consider the following general (non-necessarily geometric) capacitated set cover problem. There is given a set of elements with real weights and a family of sets of the elements. One can use a set if it is a subset of one of the sets in the family and the sum of the weights of its elements is at most one. The goal is to cover all the elements with the allowed sets. We show that any polynomial-time algorithm that approximates the uncapacitated version of the set cover problem with ratio r can be converted to an approximation algorithm for the capacitated version with ratio r + 1.357. The composition of these two results yields a polynomial-time approximation algorithm for the problem of covering a set of customers represented by a weighted n-point set with a minimum number of antennas of variable angular range and fixed capacity with ratio 2.357.
|
|
| 2. |
- Ebbers-Baumann, Annette, et al.
(författare)
-
Embedding point sets into plane graphs of small dilation
- 2007
-
Ingår i: International Journal of Computational Geometry and Applications. - 0218-1959. ; 17:3, s. 201-230
-
Tidskriftsartikel (refereegranskat)abstract
- Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on the circle, this question seems hard to answer; it is not even clear if there exists a lower bound > 1. In this paper we provide the first upper and lower bounds for the embedding problem. 1. Each finite point set can be embedded in to the vertex set of a finite triangulation of dilation <= 1.1247. 2. Each embedding of a closed convex curve has dilation >= 1.00157. 3. Let P be the plane graph that results from intersecting n infinite families of equidistant, parallel lines in general position. Then the vertex set of P has dilation >= 2/root 3 approximate to 1.1547.
|
|
| 3. |
- Karpinski, Marek, et al.
(författare)
-
A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set
- 2015
-
Ingår i: Automata, Languages, and Programming/Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783662476710 ; 9134, s. 785-796
-
Konferensbidrag (refereegranskat)abstract
- The number of triangulations of a planar n point set S is known to be c^n, where the base c lies between 2.43 and 30. Similarly, the number of spanning trees on S is known to be d^n, where the base d lies between 6.75 and 141.07. The fastest known algorithm for counting triangulations of S runs in O^∗(2^n) time while that for counting spanning trees runs in O^∗(7.125^n) time. The fastest known arbitrarily close approximation algorithms for the base of the number of triangulations of S and the base of the number of spanning trees of S, respectively, run in time subexponential in n. We present the first quasi-polynomial approximation schemes for the base of the number of triangulations of S and the base of the number of spanning trees on S, respectively.
|
|
| 4. |
- Karpinski, Marek, et al.
(författare)
-
A QPTAS for the base of the number of crossing-free structures on a planar point set
- 2018
-
Ingår i: Theoretical Computer Science. - : Elsevier BV. - 0304-3975. ; 711, s. 56-65
-
Tidskriftsartikel (refereegranskat)abstract
- The number of triangulations of a planar n point set S is known to be cn, where the base c lies between 2.43 and 30. Similarly, the number of crossing-free spanning trees on S is known to be dn, where the base d lies between 6.75 and 141.07. The fastest known algorithm for counting triangulations of S runs in 2(1+o(1))nlog n time while that for counting crossing-free spanning trees runs in O (7.125n) time. The fastest known, non-trivial approximation algorithms for the number of triangulations of S and the number of crossing-free spanning trees of S, respectively, run in time subexponential in n. We present the first non-trivial approximation algorithms for these numbers running in quasi-polynomial time. They yield the first quasi-polynomial approximation schemes for the base of the number of triangulations of S and the base of the number of crossing-free spanning trees on S, respectively.
|
|
| 5. |
- Karpinski, Marek, et al.
(författare)
-
Optimal cuts and partitions in tree metrics in polynomial time
- 2013
-
Ingår i: Information Processing Letters. - : Elsevier BV. - 0020-0190. ; 113:12, s. 447-451
-
Tidskriftsartikel (refereegranskat)abstract
- We present a polynomial time dynamic programming algorithm for optimal partitions in the shortest path metric induced by a tree. This resolves, among other things, the exact complexity status of the optimal partition problems in one-dimensional geometric metric settings. Our method of solution could be also of independent interest in other applications. We discuss also an extension of our method to the class of metrics induced by the bounded treewidth graphs. (C) 2013 Elsevier B.V. All rights reserved.
|
|
