| 1. |
- Dessmark, Anders, et al.
(författare)
-
Trade-offs between load and degree in virtual path layouts
- 2003
-
Ingår i: Parallel Processing Letters. - 1793-642X. ; 13:3, s. 485-496
-
Tidskriftsartikel (refereegranskat)abstract
- We study virtual path layouts in ATM networks. Packets are routed along virtual paths in the network by maintaining a routing field whose subfields determine intermediate destinations of the packet, i.e., the endpoints of virtual paths on its way to the final destination. Most of the research on virtual path layouts has focused on tradeoffs between load (i.e., the maximum number of virtual paths passing through a link) and the hop number of the layout (i.e., the maximum number of virtual paths needed to travel between any two nodes). There is however another important limitation on construction of layouts, resulting from technological properties of switches situated at nodes. This bound is the degree of the layout (i.e., the maximum number of virtual paths with a common endpoint). In this paper we study relations between these three parameters of virtual path layouts, for the all-to-all problem. For any integer h, we show tradeoffs between load and degree of h-hop layouts in the ring and in the mesh by establishing upper and lower bounds on these parameters. Our bounds on the degree of an h-hop layout of given load are asymptotically tight and the bounds on the load of an h-hop layout of given degree are asymptotically tight for constant h.
|
|
| 2. |
- Adamaszek, Anna, et al.
(författare)
-
Approximation schemes for capacitated geometric network design
- 2018
-
Ingår i: SIAM Journal on Discrete Mathematics. - 0895-4801. ; 32:4, s. 2720-2746
-
Tidskriftsartikel (refereegranskat)abstract
- We study a capacitated network design problem in a geometric setting. The input consists of an integral edge capacity k and two sets of points on the Euclidean plane, sources, and sinks, with an integral demand for each point. The demand of each source specifies the amount of flow that has to be shipped from the source, and the demand of each sink specifies the amount of flow that has to be shipped to the sink. The goal is to construct a minimum-length network that allows one to route the requested flow from the sources to the sinks and where each edge in the network has capacity k. The vertices of the network are not constrained to the sets of sinks and sources-any point on the Euclidean plane can be used as a vertex. The flow is splittable and parallel edges are allowed. The capacitated geometric network design problem generalizes, among others, the geometric Steiner tree problem, and as such it is NP-hard. We show that if the demands are polynomially bounded and the edge capacity k is not too large, the single-sink capacitated geometric network design problem admits a polynomial time approximation scheme. If the capacity is arbitrarily large, then we design a quasi-polynomial time approximation scheme for the capacitated geometric network design problem allowing for an arbitrary number of sinks. Our results rely on a derivation of an upper bound on the number of vertices different from sources and sinks (the so-called Steiner vertices) in an optimal network. The bound is polynomial in the total demand of the sources.
|
|
| 3. |
- Adamaszek, Anna, et al.
(författare)
-
PTAS for k-tour cover poblem on the plane for moderately large values of k
- 2010
-
Ingår i: International Journal of Foundations of Computer Science. - 0129-0541. ; 21:6, s. 893-904
-
Tidskriftsartikel (refereegranskat)abstract
- Let P be a set of n points in the Euclidean plane and let O be the origin point in the plane. In the k-tour cover problem (called frequently the capacitated vehicle routing problem), the goal is to minimize the total length of tours that cover all points in P, such that each tour starts and ends in O and covers at most k points from P. The k-tour cover problem is known to be NP-hard. It is also known to admit constant factor approximation algorithms for all values of k and even a polynomial-time approximation scheme (PTAS) for small values of k, k = circle divide (log n/ log log n). In this paper, we significantly enlarge the set of values of k for which a PTAS is provable. We present a new PTAS for all values of k <= 2(log delta n), where delta = delta(epsilon). The main technical result proved in the paper is a novel reduction of the k-tour cover problem with a set of n points to a small set of instances of the problem, each with circle divide((k/epsilon)(circle divide(1))) points.
|
|
| 4. |
|
|
| 5. |
- Alon, Noga, et al.
(författare)
-
Approximating the maximum clique minor and some subgraph homeomorphism problems.
- 2007
-
Ingår i: Theoretical Computer Science. - : Elsevier BV. - 0304-3975. ; 374:1-3, s. 149-158
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the “minor” and “homeomorphic” analogues of the maximum clique problem, i.e., the problems of determining the largest h such that the input graph (on n vertices) has a minor isomorphic to Kh or a subgraph homeomorphic to Kh, respectively, as well as the problem of finding the corresponding subgraphs. We term them as the maximum clique minor problem and the maximum homeomorphic clique problem, respectively. We observe that a known result of Kostochka and Thomason supplies an O(sqrt n) source bound on the approximation factor for the maximum clique minor problem achievable in polynomial time. We also provide an independent proof of nearly the same approximation factor with explicit polynomial-time estimation, by exploiting the minor separator theorem of Plotkin et al. Next, we show that another known result of Bollobás and Thomason and of Komlós and Szemerédi provides an O(sqrt n) source bound on the approximation factor for the maximum homeomorphic clique achievable in polynomial time. On the other hand, we show an Ω(n1/2−O(1/(logn)γ)) lower bound (for some constant γ, unless NP subset ZPTIME(2^(logn)^O(1)) on the best approximation factor achievable efficiently for the maximum homeomorphic clique problem, nearly matching our upper bound. Finally, we derive an interesting trade-off between approximability and subexponential time for the problem of subgraph homeomorphism where the guest graph has maximum degree not exceeding three and low treewidth.
|
|
| 6. |
- Antoniadis, Antonios, et al.
(författare)
-
Approximability of edge matching puzzles
- 2010
-
Ingår i: SOFSEM 2010: Theory and Practice of Computer Science / Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 9783642112669 ; 5901, s. 153-164
-
Konferensbidrag (refereegranskat)
|
|
| 7. |
- 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.
|
|
| 8. |
- Björklund, Andreas, et al.
(författare)
-
Fast Boolean matrix multiplication for highly clustered data
- 2001
-
Ingår i: Algorithms and data structures : 7th International Workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001 : proceedings. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 3540424237 ; LNCS 2125, s. 258-263
-
Konferensbidrag (refereegranskat)abstract
- We consider the problem of computing the product of two n×n Boolean matrices A and B. For an n×n Boolean matrix C, let GC be the complete weighted graph on the rows of C where the weight of an edge between two rows is equal to its Hamming distance, i.e., the number of entries in the first row having values different from the corresponding entries in the second one. Next, letMWT(C) be the weight of a minimum weight spanning tree of GC. We show that the product of A with B as well as the so called witnesses of the product can be computed in time (n(n + min{MWT(A),MWT(Bt)})) ˜O
|
|
| 9. |
- Bohler, Cecilia, et al.
(författare)
-
Forest-like abstract Voronoi diagrams in linear time
- 2018
-
Ingår i: Computational Geometry: Theory and Applications. - : Elsevier BV. - 0925-7721. ; 68, s. 134-145
-
Tidskriftsartikel (refereegranskat)abstract
- Abstract Voronoi diagrams are a general framework covering many types of concrete diagrams for different types of sites or distance measures. Generalizing a famous result by Aggarwal et al. we prove the following. Suppose it is known that inside a closed domain D the Voronoi diagram V(S) is a tree, and for each subset S'⊂S, a forest with one face per site. If the order of Voronoi regions of V(S) along the boundary of D is given, then V(S) inside D can be constructed in linear time.
|
|
| 10. |
- Carlsson, Svante, et al.
(författare)
-
Foreword
- 1993. - 1
-
Ingår i: Automata, Languages and Programming. - : Springer Verlag. - 3540569391 - 0387569391 ; , s. v-
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)
|
|
