| 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)
|
|
| 11. |
- Chlebus, BS, et al.
(författare)
-
Performing work in broadcast networks
- 2006
-
Ingår i: Distributed Computing. - : Springer Science and Business Media LLC. - 0178-2770 .- 1432-0452. ; 18:6, s. 435-451
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the problem of how to schedule t similar and independent tasks to be performed in a synchronous distributed system of p stations communicating via multiple-access channels. Stations are prone to crashes whose patterns of occurrence are specified by adversarial models. Work, defined as the number of the available processor steps, is the complexity measure. We consider only reliable algorithms that perform all the tasks as long as at least one station remains operational. It is shown that every reliable algorithm has to perform work Omega(t + p root t) even when no failures occur. An optimal deterministic algorithm for the channel with collision detection is developed, which performs work O(t + p root t). Another algorithm, for the channel without collision detection, performs work O(t + p root t + p min {f, t}), where f < p is the number of failures. This algorithm is proved to be optimal, provided that the adversary is restricted in failing no more than f stations. Finally, we consider the question if randomization helps against weaker adversaries for the channel without collision detection. A randomized algorithm is developed which performs the expected minimum amount O(t + p root t) of work, provided that the adversary may fail a constant fraction of stations and it has to select failure-prone stations prior to the start of an execution of the algorithm.
|
|
| 12. |
- Christersson, M, et al.
(författare)
-
Gossiping with bounded size messages in ad hoc radio networks (Extended abstract)
- 2002
-
Ingår i: Automata, Languages and Programming / Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. ; 2380, s. 377-389
-
Konferensbidrag (refereegranskat)abstract
- We study deterministic algorithms for the gossiping problem in ad hoc radio networks under the assumption that each combined message contains at most b(n) single messages or bits of auxiliary information, where b is an integer function and n is the number of nodes in the network. We term such a restricted gossiping problem b(n) -gossiping. We show that rootn-gossiping in an ad hoc radio network on n nodes can be done deterministically in time (O) over tilde (n(3/2)) which asymptotically matches the best known upper bound on the time complexity of unrestricted deterministic gossiping(dagger). Our upper bound on rootn-gossiping is tight up to a poly-logarithmic factor and it implies similarly tight upper bounds on b(n)-gossiping where function b is computable and 1 less than or equal to b(n) : rootn holds. For symmetric ad hoc radio networks, we show that even 1-gossiping can be done deterministically in time (O) over tilde (n(3/2)). We also demonstrate that O(n(t))-gossiping in a symmetric ad hoc radio network on n nodes can be done in time O(n(2-t)). Note that the latter upper bound is o(n(3/2)) when the size of a combined message is w(n(1/2)). Furthermore, by adopting known results on repeated randomized broadcasting in symmetric ad hoc radio networks, we derive a randomized protocol for 1-gossiping in these networks running in time (O) over tilde (n) on the average. Finally, we observe that when a collision detection mechanism is available, even deterministic 1-gossiping in symmetric ad hoc radio networks can be performed in time (O) over tilde (n).
|
|
| 13. |
- Czumaj, Artur, et al.
(författare)
-
Approximation algorithms for buy-at-bulk geometric network design
- 2011
-
Ingår i: Algorithms and data structures / Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 3642033660 ; 5664, s. 1949-1969
-
Konferensbidrag (refereegranskat)abstract
- The buy-at-bulk network design problem has been extensively studied in the general graph model. In this paper we consider the geometric version of the problem, where all points in a Euclidean space are candidates for network nodes. We present the first general approach for geometric versions of basic variants of the buy-at-bulk network design problem. It enables us to obtain quasi-polynomial-time approximation schemes for basic variants of the buy-at-bulk geometric network design problem with polynomial total demand. Then, for instances with few sinks and low capacity links, we design very fast polynomial-time low-constant approximations algorithms.
|
|
| 14. |
- Czumaj, A, et al.
(författare)
-
Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
- 2005
-
Ingår i: Information Processing Letters. - : Elsevier BV. - 0020-0190. ; 94:2, s. 49-53
-
Tidskriftsartikel (refereegranskat)abstract
- We present a generic scheme for approximating NP-hard problems on graphs of treewidth k = omega (log n). When a tree-decomposition of width l is given, the scheme typically yields an l / log n-approximation factor; otherwise, an extra log k factor is incurred. Our method applies to several basic subgraph and partitioning problems, including the maximum independent set problem.
|
|
| 15. |
- Czumaj, Artur, et al.
(författare)
-
Fast approximation schemes for Euclidean multi-connectivity problems
- 2000
-
Ingår i: Automata, languages and programming / Lecture notes in computer science. - 3540677151 ; 1853, s. 856-868
-
Konferensbidrag (refereegranskat)abstract
- We present new polynomial-time approximation schemes (PTAS) for several basic minimum-cost multi-connectivity problems in geometrical graphs. We focus on low connectivity requirements. Each of our schemes either signifi- cantly improves the previously known upper time-bound or is the first PTAS for the considered problem. We provide a randomized approximation scheme for finding a biconnected graph spanning a set of points in a multi-dimensional Euclidean space and having the expected total cost within (1+") of the optimum. For any constant dimension and ", our scheme runs in time O(n log n). It can be turned into Las Vegas one without affecting its asymptotic time complexity, and also efficiently derandomized. The only previously known truly polynomial-time approximation (randomized) scheme for this problem runs in expected time n (log n)O((log log n)9) in the simplest planar case. The efficiency of our scheme relies on transformations of nearly optimal low cost special spanners into sub-multigraphs having good decomposition and approximation properties and a simple subgraph connectivity characterization. By using merely the spanner transformations, we obtain a very fast polynomial-time approximation scheme for finding a minimum-cost k-edge connected multigraph spanning a set of points in a multi-dimensional Euclidean space. For any constant dimension, ", and k, this PTAS runs in time O(n log n). Furthermore, by showing a low-cost transformation of a k-edge connected graph maintaining the k-edge connectivity and developing novel decomposition properties, we derive a PTAS for Euclidean minimum-cost k-edge connectivity. It is substantially faster than that previously known. Finally, by extending our techniques, we obtain the first PTAS for the problem of Euclidean minimum-cost Steiner biconnectivity. This scheme runs in time O(n log n) for any constant dimension and ". As a byproduct, we get the first known non-trivial upper bound on the number of Steiner points in an optimal solution to an instance of Euclidean minimum-cost Steiner biconnectivity.
|
|
| 16. |
- Czumaj, Artur, et al.
(författare)
-
Faster algorithms for finding lowest common ancestors in directed acyclic graphs
- 2007
-
Ingår i: Theoretical Computer Science. - : Elsevier BV. - 0304-3975. ; 380:1-2, s. 37-46
-
Tidskriftsartikel (refereegranskat)abstract
- We present two new methods for finding a lowest common ancestor (LCA) for each pair of vertices of a directed acyclic graph (dag) on n vertices and m edges. The first method is surprisingly natural and solves the all-pairs LCA problem for the input dag on n vertices and m edges in time 0 (n m). The second method relies on a novel reduction of the all-pairs LCA problem to the problem of finding maximum witnesses for Boolean matrix product. We solve the latter problem (and hence also the all-pairs LCA problem) in time 0 (n (2+lambda)), where A satisfies the equation to (1, lambda, I) = 1 + 2 lambda and w (1, lambda, 1) is the exponent of the multiplication of an n x n (lambda) matrix by an n (lambda) x n matrix. By the currently best known bounds on w 1, lambda, 1), the running time of our algorithm is O (n (2.575)). Our algorithm improves the previously known O (n (2.688)) time-bound for the general all-pairs LCA problem in dags by Bender et al. Our additional contribution is a faster algorithm for solving the all-pairs lowest common ancestor problem in dags of small depth, where the depth of a dag is defined as the length of the longest path in the dag. For all dags of depth at most h <= n alpha where alpha approximate to 0.294, our algorithm runs in a time that is asymptotically the same as that required for multiplying two n x n matrices, that is, O (n (w)); we also prove that this running time is optimal even for dags of depth 1. For dags with depth h > n (alpha) the running time of our algorithm is at most O (n (w) ho (0.468)). This algorithm is faster than our algorithm for arbitrary dags for all values of h <= n (0.42). (C) 2007 Elsevier B. V. All rights reserved.
|
|
| 17. |
- Czumaj, Artur, et al.
(författare)
-
Finding a heaviest triangle is no harder than matrix multiplication
- 2006
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- We show that for any 0, a maximum-weight triangle in an undirected graph with n vertices and real weights assigned to vertices can be found in time \O(n+n2+), where is the exponent of fastest matrix multiplication algorithm. By the currently best bound on , the running time of our algorithm is \O(n2376). Our algorithm substantially improves the previous time-bounds for this problem recently established by Vassilevska et al. (STOC 2006, \O(n2688)) and (ICALP 2006, \O(n2575)). Its asymptotic time complexity matches that of the fastest known algorithm for finding \emph{a} triangle (not necessarily a maximum-weight one) in a graph. By applying or extending our algorithm, we can also improve the upper bounds on finding a maximum-weight triangle in a sparse graph and on finding a maximum-weight subgraph isomorphic to a fixed graph established in the papers by Vassilevska et al. For example, we can find a maximum-weight triangle in a vertex-weighted graph with m edges in asymptotic time required by the fastest algorithm for finding \emph{any} triangle in a graph with m edges, i.e., in time \O(m141).
|
|
| 18. |
- Czumaj, Artur, et al.
(författare)
-
Finding a heaviest triangle is not harder than matrix multiplication
- 2007
-
Ingår i: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. - 9780898716245 ; , s. 986-994
-
Konferensbidrag (refereegranskat)abstract
- We show that for any ε > 0, a maximum-weight triangle in an undirected graph with n vertices and real weights assigned to vertices can be found in time O(nω + n2+ε), where ω is the exponent of fastest matrix multiplication algorithm. By the currently best bound on ω, the running time of our algorithm is O(n2.376). Our algorithm substantially improves the previous time-bounds for this problem recently established by Vassilevska et al. (STOC 2006, O(n2.688)) and (ICALP 2006, O(n2.575)). Its asymptotic time complexity matches that of the fastest known algorithm for finding a triangle (not necessarily a maximum-weight one) in a graph. By applying or extending our algorithm, we can also improve the upper bounds on finding a maximum-weight triangle in a sparse graph and on finding a maximum-weight subgraph isomorphic to a fixed graph established in the papers by Vassilevska et al. For example, we can find a maximum-weight triangle in a vertex-weighted graph with m edges in asymptotic time required by the fastest algorithm for finding any triangle in a graph with m edges, i.e., in time O(m1.41).
|
|
| 19. |
- Czumaj, Artur, et al.
(författare)
-
Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
- 2009
-
Ingår i: SIAM Journal on Computing. - : Society for Industrial & Applied Mathematics (SIAM). - 0097-5397 .- 1095-7111. ; 39:2, s. 431-444
-
Tidskriftsartikel (refereegranskat)abstract
- We show that a maximum-weight triangle in an undirected graph with n vertices and real weights assigned to vertices can be found in time O(n(omega) + n(2+o(1))), where omega is the exponent of the fastest matrix multiplication algorithm. By the currently best bound on omega, the running time of our algorithm is O(n(2.376)). Our algorithm substantially improves the previous time-bounds for this problem, and its asymptotic time complexity matches that of the fastest known algorithm for finding any triangle (not necessarily a maximum-weight one) in a graph. We can extend our algorithm to improve the upper bounds on finding a maximum-weight triangle in a sparse graph and on finding a maximum-weight subgraph isomorphic to a fixed graph. We can find a maximum-weight triangle in a vertex-weighted graph with m edges in asymptotic time required by the fastest algorithm for finding any triangle in a graph with m edges, i.e., in time O(m(1.41)). Our algorithms for a maximum-weight fixed subgraph (in particular any clique of constant size) are asymptotically as fast as the fastest known algorithms for a fixed subgraph.
|
|
| 20. |
- Czumaj, A, et al.
(författare)
-
Improved approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
- 2003
-
Ingår i: Lecture Notes in Computer Science (Algorithms and Computation). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783540206958 ; 2906, s. 544-553
-
Konferensbidrag (refereegranskat)abstract
- In this paper we present two novel generic schemes for approximation algorithms for optimization NP-hard graph problems constrained to partial k-trees. Our first scheme yields deterministic polynomial-time algorithms achieving typically an approximation factor of k/log(1-is an element of)n, where k = polylog(n). The second scheme yields randomized polynomial-time algorithms achieving an approximation factor of k/logn for k = Omega(logn). Both our approximation methods lead to the best known approximation guarantees for some basic optimization problems. In particular, we obtain best known polynomial-time approximation guarantees for the classical maximum independent set problem in partial trees.
|
|
| 21. |
- Czumaj, Artur, et al.
(författare)
-
Minimum k-connected geometric networks
- 2008
-
Ingår i: Encyclopedia of Algorithms. - Boston, MA : Springer US. - 9780387301624 ; , s. 536-538
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)
|
|
| 22. |
- Czumaj, Artur, et al.
(författare)
-
On parallel time in population protocols
- 2023
-
Ingår i: Information Processing Letters. - : Elsevier BV. - 0020-0190. ; 179
-
Tidskriftsartikel (refereegranskat)abstract
- The parallel time of a population protocol is defined as the average number of required interactions in which an agent in the protocol participates, i.e., the quotient between the total number of interactions required by the protocol and the total number n of agents, or just roughly the number of required rounds, where a round stands for a sequence of n consecutive interactions. This naming triggers an intuition that at least the expected number of parallel steps sufficient to implement a round is O(1). In a single parallel step only mutually independent interactions can be involved. We show that when the transition function of a population protocol is treated as a black box then the expected maximum number of parallel steps necessary to implement a round is [Formula presented]. We also provide a combinatorial argument for a matching upper bound on the expected number of parallel steps under additional assumptions. Further, we extend these bounds by showing that the situation changes dramatically for sequences of m=Ω(nlogn) interactions. Then, the expected number of parallel steps required to implement such sequences is [Formula presented] under the aforementioned additional assumptions. Thus, it asymptotically coincides with the notion of parallel time, i.e., [Formula presented], for sequences of interactions produced by protocols solving any non-trivial problems requiring Ω(nlogn) interactions.
|
|
| 23. |
- Czumaj, A, et al.
(författare)
-
Polynomial-time approximation schemes for the Euclidean survivable network design problem
- 2002
-
Ingår i: Automata, Languages and Programming / Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. ; 2380, s. 973-984
-
Konferensbidrag (refereegranskat)abstract
- The survivable network design problem is a classical problem in combinatorial optimization of constructing a minimum-cost subgraph satisfying predetermined connectivity requirements. In this paper we consider its geometric version in which the input is a complete Euclidean graph. We assume that each vertex v has been assigned a connectivity requirement r(upsilon).. The output subgraph is supposed to have the vertex- (or edge-, respectively) connectivity of at least min{r(upsilon), r(u)} for any pair of vertices upsilon, u. We present the first polynomial-time approximation schemes (PTAS) for basic variants of the survivable network design problem in Euclidean graphs. We first show a PTAS for the Steiner tree problem, which is the survivable network design problem with r(upsilon) is an element of {0, 1} for any vertex upsilon. Then, we extend it to include the most widely applied case where r(upsilon) is an element of {0, 1, 2} for any vertex upsilon. Our polynomial-time approximation schemes work for both vertex- and edge-connectivity requirements in time 0 (n log n), where the constants depend on the dimension and the accuracy of approximation. Finally, we observe that our techniques yield also a PTAS for the multigraph variant of the problem where the edge-connectivity requirements satisfy r(upsilon) is an element of {0, 1,..., k} and k = O(1).
|
|
| 24. |
- Dannenberg, Katharina, et al.
(författare)
-
The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets
- 2019
-
Ingår i: Discrete Applied Mathematics. - : Elsevier BV. - 0166-218X. ; 257, s. 101-114
-
Tidskriftsartikel (refereegranskat)abstract
- The NP-hard maximum rooted resolved triplets consistency problem (MRTC) takes as input a set [Formula presented] of leaf labels and a set [Formula presented] of resolved triplets over [Formula presented] and asks for a rooted phylogenetic tree that is consistent with the maximum number of elements in [Formula presented]. This article studies the approximability of a generalization of the problem called the maximum rooted triplets consistency problem (MTC) where in addition to resolved triplets, the input may contain fan triplets, forbidden resolved triplets, and forbidden fan triplets. To begin with, we observe that MTC admits a [Formula presented]-approximation in polynomial time. Next, we generalize Wu's exact exponential-time algorithm for MRTC (Wu, 2004) to MTC. Forcing the algorithm to always output a rooted [Formula presented]-ary phylogenetic tree for any specified [Formula presented] subsequently leads to an exponential-time approximation scheme (ETAS) for MTC. We then present a polynomial-time approximation scheme (PTAS) for complete instances of MTC (meaning that for every [Formula presented] with [Formula presented], [Formula presented] contains at least one rooted triplet involving the leaf labels in [Formula presented]), based on the techniques introduced by Jiang et al. (2001) for a related problem. We also study the computational complexity of MTC restricted to fan triplets and forbidden fan triplets. Finally, extensions to weighted instances are considered.
|
|
| 25. |
- Dereniowski, Dariusz, et al.
(författare)
-
Clearing directed subgraphs by mobile agents Variations on covering with paths
- 2019
-
Ingår i: Journal of computer and system sciences (Print). - : Elsevier. - 0022-0000 .- 1090-2724. ; 102, s. 57-68
-
Tidskriftsartikel (refereegranskat)abstract
- We study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H = (V-H, A(H)) of D such that (a) S subset of V-H, (b) H is the union of k directed walks in D, and (c) the underlying graph of H includes a Steiner tree for S in D. Since a directed walk is a not necessarily a simple directed path, the problem is actually on covering with paths. We provide several results on the polynomial time tractability, hardness, and parameterized complexity of the problem. Our main fixed-parameter algorithm is randomized. (C) 2018 Elsevier Inc. All rights reserved.
|
|
| 26. |
- Dereniowski, Dariusz, et al.
(författare)
-
The Snow Team Problem
- 2017
-
Ingår i: Fundamentals of Computation Theory. - Berlin, Heidelberg : Springer. - 9783662557501 - 9783662557518 ; , s. 190-203
-
Konferensbidrag (refereegranskat)abstract
- We study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset � of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph �=(��,��) of D such that (a) �⊆��, (b) H is the union of k directed walks in D, and (c) the underlying graph of H includes a Steiner tree for �. We provide several results on parameterized complexity and hardness of the problems.
|
|
| 27. |
- Dereniowski, Dariusz, et al.
(författare)
-
The snow team problem : (Clearing Directed subgraphs by mobile agents)
- 2017
-
Ingår i: Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Proceedings. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 9783662557501 ; 10472 LNCS, s. 190-203
-
Konferensbidrag (refereegranskat)abstract
- We study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H = (VH, AH) of D such that (a) S ⊆ VH, (b) H is the union of k directed walks in D, and (c) the underlying graph of H includes a Steiner tree for S. We provide several results on parameterized complexity and hardness of the problems.
|
|
| 28. |
- Dessmark, Anders, et al.
(författare)
-
On the approximability of maximum and minimum edge clique partition problems
- 2007
-
Ingår i: International Journal of Foundations of Computer Science. - 0129-0541. ; 18:2, s. 217-226
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the following clustering problems: given an undirected graph, partition its vertices into disjoint clusters such that each cluster forms a clique and the number of edges within the clusters is maximized (Max-ECP), or the number of edges between clusters is minimized (Min-ECP). These problems arise naturally in the DNA clone classification. We investigate the hardness of finding such partitions and provide approximation algorithms. Further, we show that greedy strategies yield constant factor approximations for graph classes for which maximum cliques can be found efficiently.
|
|
| 29. |
- Dessmark, Anders, et al.
(författare)
-
On the approximability of maximum and minimum edge clique partition problems
- 2006
-
Ingår i: Conferences in Research and Practice in Information Technology Series. - 1920682333 ; 168, s. 101-105
-
Konferensbidrag (refereegranskat)abstract
- We consider the following clustering problems: given a general undirected graph, partition its vertices into disjoint clusters such that each cluster forms a clique and the number of edges within the clusters is maximized (Max-ECP), or the number of edges between clusters is minimized (Min-ECP). These problems arise naturally in the DNA clone classification. We investigate the hardness of finding such partitions and provide approximation algorithms. Further, we show that greedy strategies yield constant factor approxi mations for graph classes for which maximum cliques can be found efficiently.
|
|
| 30. |
- Dessmark, Anders, et al.
(författare)
-
Polynomial-time algorithms for the ordered maximum agreement subtree problem
- 2007
-
Ingår i: Algorithmica. - : Springer Science and Business Media LLC. - 0178-4617 .- 1432-0541. ; 3109, s. 220-229
-
Tidskriftsartikel (refereegranskat)abstract
- For a set of rooted, unordered, distinctly leaf-labeled trees, the NP-hard maximum agreement subtree problem (MAST) asks for a tree contained (up to isomorphism or homeomorphism) in all of the input trees with as many labeled leaves as possible. We study the ordered variants of MAST where the trees are uniformly or non-uniformly ordered. We provide the first known polynomial-time algorithms for the uniformly and non-uniformly ordered homeomorphic variants as well as the uniformly and non-uniformly ordered isomorphic variants of MAST. Our algorithms run in time O(kn(3)), O (n(3) min{kn, n + log(k-1) n}), O(kn(3)), and O(n(3) min{kn, n + log(k-1) n)), respectively, where n is the number of leaf labels and k is the number of input trees.
|
|
| 31. |
- Dessmark, Anders, et al.
(författare)
-
Subexponential-time framework for optimal embeddings of graphs in integer lattices
- 2004
-
Ingår i: Algorithm Theory - SWAT 2004/Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783540223399 ; 3111, s. 248-259
-
Konferensbidrag (refereegranskat)abstract
- We present a general framework for computing various optimal embeddings of undirected and directed connected graphs in two and multi-dimensional integer lattices in time sub-exponential either in the minimum number n of lattice points used by such optimal embeddings or in the budget upper bound b on the number of lattice points that may be used in an embedding. The sub-exponential upper bounds in the two dimensional case and d-dimensional case are respectively of the form 2(O(rootln log n)), 2(Orootlb log b)) and 2(n)(O(dl1/d) ((d-1)/d)(log n)),2(O(dl l/d(d-1)/d) (log b),) where l stands for the degree of the allowed overlap. For the problem of minimum total edge length planar or multi-dimensional embedding or layout of a graph and the problem of an optimal protein folding in the so called HP model we obtain the upper bounds in terms of n. Note that in case of protein folding n is also the size of the input. The list of problems for which we can derive the upper bounds in terms of b includes among other things: 1. a minimum area planar embedding or layout of a graph, 2. a minimum bend planar or three dimensional embedding or layout, 3. a minimum maximum edge length planar or three dimensional embedding or layout.
|
|
| 32. |
- Dumitrescu, Adrian, et al.
(författare)
-
Finding Small Complete Subgraphs Efficiently
- 2023
-
Ingår i: Combinatorial Algorithms - 34th International Workshop, IWOCA 2023, Proceedings. - 1611-3349 .- 0302-9743. - 9783031343469 ; 13889 LNCS, s. 185-196
-
Konferensbidrag (refereegranskat)abstract
- (I) We revisit the algorithmic problem of finding all triangles in a graph G= (V, E) with n vertices and m edges. According to a result of Chiba and Nishizeki (1985), this task can be achieved by a combinatorial algorithm running in O(mα) = O(m3 / 2) time, where α= α(G) is the graph arboricity. We provide a new very simple combinatorial algorithm for finding all triangles in a graph and show that is amenable to the same running time analysis. We derive these worst-case bounds from first principles and with very simple proofs that do not rely on classic results due to Nash-Williams from the 1960s. (II) We extend our arguments to the problem of finding all small complete subgraphs of a given fixed size. We show that the dependency on m and α in the running time O(αℓ-2· m) of the algorithm of Chiba and Nishizeki for listing all copies of Kℓ, where ℓ≥ 3, is asymptotically tight. (III) We give improved arboricity-sensitive running times for counting and/or detection of copies of Kℓ, for small ℓ≥ 4. A key ingredient in our algorithms is, once again, the algorithm of Chiba and Nishizeki. Our new algorithms are faster than all previous algorithms in certain high-range arboricity intervals for every ℓ≥ 7.
|
|
| 33. |
- Ebbers-Baumann, A, et al.
(författare)
-
A fast algorithm for approximating the detour of a polygonal chain
- 2004
-
Ingår i: Computational Geometry. - 0925-7721. ; 27:2, s. 123-134
-
Tidskriftsartikel (refereegranskat)abstract
- Let C be a simple(1) polygonal chain of n edges in the plane, and let p and q be two arbitrary points on C. The detour of C on (p, q) is defined to be the length of the subchain of C that connects p with q, divided by the Euclidean distance between p and q. Given an epsilon >0, we compute in time O((1)/(epsilon) n log n) a pair of points on which the chain makes a detour at least 1/(1 + epsilon) times the maximum detour. (C) 2003 Elsevier B.V. All rights reserved.
|
|
| 34. |
- 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.
|
|
| 35. |
- Ebbers-Baumann, A, et al.
(författare)
-
Embedding point sets into plane graphs of small dilation
- 2005
-
Ingår i: Algorithms and Computation / Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 3540309357 ; 3827, s. 5-16
-
Konferensbidrag (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 into 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.
|
|
| 36. |
- Figueroa, Andres, et al.
(författare)
-
Approximate clustering of fingerprint vectors with missing values
- 2005
-
Ingår i: Proceedings of the 2005 Australasian symposium on Theory of computing. - 1445-1336. - 1920682236 ; , s. 57-60
-
Konferensbidrag (refereegranskat)abstract
- We study the problem of clustering fingerprints with at most p missing values (CMV (p) for short) naturally arising in oligonucleotide fingerprinting, which is an efficient method for characterizing DNA clone libraries.We show that already CMV(2) is NP-hard. We also show that a greedy algorithm yields a min(1 + ln n, 2+pln l) approximation for CMV(p), and can be implemented to run in O(nl2p) time. Furthermore, we introduce other variants of the problem of clustering fingerprints with at most p missing values based on slightly different optimization criteria and show that they can be approximated in polynomial time with ratios 22p-1 and 2(1 - [EQUATION]), respectively.
|
|
| 37. |
- Figueroa, Andres, et al.
(författare)
-
Approximate clustering of incomplete fingerprints
- 2008
-
Ingår i: Journal of Discrete Algorithms. - : Elsevier. - 1570-8667 .- 1570-8675. ; 6:1, s. 103-108
-
Tidskriftsartikel (refereegranskat)abstract
- We study the problem of clustering fingerprints with at most p missing values (CMV(p) for short) naturally arising in oligonucleotide fingerprinting, which is an efficient method for characterizing DNA clone libraries. We show that already CMV(2) is NP-hard. We also show that a greedy algorithm yields a min(1+ln n , 2+pln l) approximation for CMV(p), and can be implemented to run in O(nl2^p) time. We also introduce other variants of the problem of clustering incomplete fingerprints based on slightly different optimization criteria and show that they can be approximated in polynomial time with ratios 2^(2p−1) and 2(1-1/(2^(2p))), respectively.
|
|
| 38. |
- Floderus, Peter, et al.
(författare)
-
3D Rectangulations and Geometric Matrix Multiplication
- 2014
-
Ingår i: Algorithms and Computation, ISAAC 2014. - Cham : Springer International Publishing. - 1611-3349 .- 0302-9743. - 9783319130743 ; 8889, s. 65-78
-
Konferensbidrag (refereegranskat)abstract
- The problem of partitioning an input rectilinear polyhedron P into a minimum number of 3D rectangles is known to be NP-hard. We first develop a 4-approximation algorithm for the special case in which P is a 3D histogram. It runs in O(m log m) time, where m is the number of corners in P. We then apply it to compute the arithmetic matrix product of two n x n matrices A and B with nonnegative integer entries, yielding a method for computing A x B in (O) over tilde (n(2) + min{rArB, n min{rA, rB}}) time, where (O) over tilde suppresses polylogarithmic (in n) factors and where rA and rB denote the minimum number of 3D rectangles into which the 3D histograms induced by A and B can be partitioned, respectively.
|
|
| 39. |
- Floderus, Peter, et al.
(författare)
-
Detecting and Counting Small Pattern Graphs
- 2015
-
Ingår i: SIAM Journal on Discrete Mathematics. - : Society for Industrial & Applied Mathematics (SIAM). - 0895-4801 .- 1095-7146. ; 29:3, s. 1322-1339
-
Tidskriftsartikel (refereegranskat)abstract
- We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs. We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for nonidentity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs. Next, we derive new upper time bounds on counting the number of isomorphisms between a fixed pattern graph with an independent set of size s and a subgraph of the host graph. We also consider a weighted version of the counting problem, when one counts the number of isomorphisms between the pattern graph and lightest subgraphs, providing a slightly slower combinatorial algorithm.
|
|
| 40. |
- Floderus, Peter, et al.
(författare)
-
Detecting and Counting Small Pattern Graphs
- 2013
-
Ingår i: Algorithms and Computation. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. ; 8283, s. 547-557
-
Konferensbidrag (refereegranskat)abstract
- We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs. We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for non-identity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs. Next, we derive new upper time bounds on counting the number of isomorphisms between a fixed pattern graph with an independent set of size s and a subgraph of the host graph. We also consider a weighted version of the counting problem, when one counts the number of isomorphisms between the pattern graph and lightest subgraphs, providing a slightly slower combinatorial algorithm.
|
|
| 41. |
- Floderus, Peter, et al.
(författare)
-
Detecting monomials with k distinct variables
- 2015
-
Ingår i: Information Processing Letters. - : Elsevier. - 0020-0190 .- 1872-6119. ; 115:2, s. 82-86
-
Tidskriftsartikel (refereegranskat)abstract
- We study the complexity of detecting monomials with special properties in the sum-product expansion of a polynomial represented by an arithmetic circuit of size polynomial in the number of input variables and using only multiplication and addition. We focus on monomial properties expressed in terms of the number of distinct variables occurring in a monomial. Our first result is a randomized FPT algorithm for detection of a monomial having at least k distinct variables, parametrized with respect to k. For a more restricted class of circuits, we can also provide a deterministic FPT algorithm for detection of a monomial having at most k distinct variables parametrized by the degree of the polynomial represented by the input circuit. Furthermore, we derive several hardness results on detection of monomials with such properties within exact, parametrized and approximation complexity. In particular, we observe that the detection of a monomial having at most k distinct variables is W[2]-hard for the parameter k. (C) 2014 Elsevier B.V. All rights reserved.
|
|
| 42. |
- Floderus, Peter, et al.
(författare)
-
Induced subgraph isomorphism: Are some patterns substantially easier than others?
- 2015
-
Ingår i: Theoretical Computer Science. - : Elsevier BV. - 0304-3975. ; 605, s. 119-128
-
Tidskriftsartikel (refereegranskat)abstract
- The complexity of the subgraph isomorphism problem where the pattern graph is of fixed size is well known to depend on the topology of the pattern graph. Here, we present two results which, in contrast, provide evidence that no topology of an induced subgraph of fixed size can be substantially easier to detect or count than an independent set of related size. We show that any fixed pattern graph having a maximum independent set of size k that is disjoint from other maximum independent sets is not easier to detect as an induced subgraph than an independent set of size k. It follows in particular that an induced path on 2k-1 vertices is not easier to detect than an independent set on k vertices, and that an induced cycle on 2k vertices is not easier to detect than an independent set on k vertices. In view of linear time upper bounds on the detection of induced path of length two and three, our lower bound is tight. Similar corollaries hold for the detection of induced complete bipartite graphs and an induced paw and its generalizations. We show also that for an arbitrary pattern graph H on k vertices with no isolated vertices, there is a simple subdivision of H, resulting from splitting each edge into a path of length four and attaching a distinct path of length three at each vertex of degree one, that is not easier to detect or count than an independent set on k vertices, respectively. Next, we show that the so-called diamond and its generalizations on k vertices are not easier to detect as induced subgraphs than an independent set on three vertices or an independent set on k vertices, respectively. For C-4, we give a weaker evidence of its hardness in terms of an independent set on three vertices. Finally, we derive several results relating the complexity of the edge-colored variant of induced subgraph isomorphism to that of the standard variant. (C) 2015 Elsevier B.V. All rights reserved.
|
|
| 43. |
- Floderus, Peter, et al.
(författare)
-
Towards More Efficient Infection and Fire Fighting
- 2013
-
Ingår i: International Journal of Foundations of Computer Science. - : World Scientific. - 0129-0541. ; 24:1, s. 3-14
-
Tidskriftsartikel (refereegranskat)abstract
- The firefighter problem models the situation where an infection, a computer virus, an idea or fire etc. is spreading through a network and the goal is to save as many as possible nodes of the network through targeted vaccinations. The number of nodes that can be vaccinated at a single time-step is typically one, or more generally O(1). In a non-standard model, the so called spreading model, the vaccinations also spread in contrast to the standard model. Our main results are concerned with general graphs in the spreading model. We provide a very simple exact 2^(O(sqrt(n)log n))-time algorithm. In the special case of trees, where the standard and spreading model are equivalent, our algorithm is substantially simpler than that exact subexponential algorithm for trees presented in . On the other hand, we show that the firefighter problem on weighted directed graphs in the spreading model cannot be approximated within a constant factor better than 1 − 1/e unless NP ⊆ DTIME (n^(O(log log n))). We also present several results in the standard model. We provide approximation algorithms for planar graphs in case when at least two vaccinations can be performed at a time-step. We also derive trade-offs between approximation factors for polynomial-time solutions and the time complexity of exact or nearly exact solutions for instances of the firefighter problem for the so called directed layered graphs.
|
|
| 44. |
- Fomin, Fedor V., et al.
(författare)
-
Approximation algorithms for time-dependent orienteering
- 2002
-
Ingår i: Information Processing Letters. - 0020-0190. ; 83:2, s. 57-62
-
Tidskriftsartikel (refereegranskat)abstract
- The time-dependent orienteering problem is dual to the time-dependent traveling salesman problem. It consists of visiting a maximum number of sites within a given deadline. The traveling time between two sites is in general dependent on the starting time. For ε greater than or equal 0, we provide a (2+ ε)-approximation algorithm for the time-dependent orienteering problem which runs in polynomial time if the ratio between the maximum and minimum traveling time between any two sites is constant. No prior upper approximation bounds were known for this time-dependent problem.
|
|
| 45. |
|
|
| 46. |
- Galcík, Frantisek, et al.
(författare)
-
Efficient broadcasting in known toplogy radio networks with long-range interference
- 2009
-
Ingår i: PODC '09 proceedings of the 28th ACM symposium on principles of distributed computing. - New York, NY, USA : ACM. - 9781605583969 ; , s. 230-239
-
Konferensbidrag (refereegranskat)abstract
- We study broadcasting (one-to-all communication) in known topology radio networks modeled by graphs, where the interference range of a node is likely to exceed its transmission range. In this model, if two nodes are connected by a transmission edge they can communicate directly. On the other hand, if two nodes are connected by an interference edge their transmissions disable recipience of one another. For a network G, we term the smallest integer d, s.t., for any interference edge e there exists a simple path formed of at most d transmission edges connecting the endpoints of e as its interference distance dI. In this model the schedule of transmissions is precomputed in advance based on full knowledge about the size and the topology (including location of transmission and interference edges) of the network. We are interested in the design of fast broadcasting schedules that are energy efficient, i.e., based on limited number of transmissions at each node. In what follows we assume that n stands for the number of nodes, DT is the diameter of the subnetwork induced by the transmission edges, and Δ refers to the maximum combined degree formed of transmission and interference edges) of the network. We contribute the following new results: (1) We prove that even for networks with the interference distance dI = 2 any broadcasting schedule requires at least DT + Ω(Δ ∙ log n/log Δ) rounds. (2) We also provide for networks modeled by bipartite graphs an algorithm that computes 1-shot (each node is allowed to transmit at most once) broadcasting schedules of length O(Δ ∙ log n). Note that in this case the length of the broadcasting schedule is independent of the interference distance of the network. (3) The main result of the paper is an algorithm that computes a 1-shot broadcasting schedule of length at most 4 ∙ DT + O(Δ ∙ dI ∙ log4 n) for networks with arbitrary topology. Note that in view of the lower bound from (1) the broadcast schedule is almost optimal for dI polylogarithmic in n. Note also that by applying our algorithm to radio networks with no interference edges the time of the broadcasting schedule from [10] is improved in graphs with Δ = o(√n/log4 n). The 1-shot broadcasting algorithm proposed in [10] relies heavily on the concept of internal ranks that impose currently an Ω(√n)-time bottleneck in the broadcasting schedule.
|
|
| 47. |
- Galcik, Frantisek, et al.
(författare)
-
Efficient broadcasting in radio networks with long-range interference
- 2013
-
Ingår i: Distributed Computing. - : Springer Science and Business Media LLC. - 0178-2770 .- 1432-0452. ; 26:1, s. 59-74
-
Tidskriftsartikel (refereegranskat)abstract
- We study broadcasting, also known as one-to-all communication, in synchronous radio networks with known topology modeled by undirected (symmetric) graphs, where the interference range of a node is likely exceeding its transmission range. In this model, if two nodes are connected by a transmission edge they can communicate directly. On the other hand, if two nodes are connected by an interference edge they cannot communicate directly and transmission of one node disables recipience of any message at the other node. For a network we term the smallest integer , s.t., for any interference edge there exists a simple path formed of at most transmission edges connecting the endpoints of as its interference distance . In this model the schedule of transmissions is precomputed in advance. It is based on the full knowledge of the size and the topology (including location of transmission and interference edges) of the network. We are interested in the design of fast broadcasting schedules that are energy efficient, i.e., based on a bounded number of transmissions executed at each node. We adopt as the number of nodes, is the diameter of the subnetwork induced by the transmission edges, and refers to the maximum combined degree (formed of transmission and interference edges) of the network. We contribute the following new results: (1) We prove that for networks with the interference distance any broadcasting schedule requires at least rounds. (2) We provide for networks modeled by bipartite graphs an algorithm that computes -shot (each node transmits at most once) broadcasting schedules of length . (3) The main result of the paper is an algorithm that computes a -shot broadcasting schedule of length at most for networks with arbitrary topology. Note that in view of the lower bound from (1) if is poly-logarithmic in this broadcast schedule is a poly-logarithmic factor away from the optimal solution.
|
|
| 48. |
- Gasieniec, L, et al.
(författare)
-
An improved bound on Boolean matrix multiplication for highly clustered data
- 2003
-
Ingår i: Algorithms and Data Structures. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783540405450 ; 2748, s. 329-339
-
Konferensbidrag (refereegranskat)abstract
- We consider the problem of computing the product of two n x n Boolean matrices A and B. For two 0 - I strings s = s(1)s(2) .... s(m) and u = u(1)u(2) ... u(m), an extended Hamming distance, eh(s, u), between the strings, is defined by a recursive equation eh(s, u) = eh(s(l+1) ... s(m), u(l+1) ... u(m)) + (s(1) + u(1) mod 2), where l is the maximum number, s.t., s(j) = s, and u(j) = u(1) for j = For any n x n Boolean matrix C, let GC be a complete weighted graph on the rows of C, where the weight of an edge between two rows is equal to its extended Hamming distance. Next, let MWT(C) be the weight of a minimum weight spanning, tree of GC. WE! show that the product of A and B as well as the so called witnesses of the product can be computed in time (O) over bar (n(n + min{MWT(A), MWT(B-t)}))(1). Since the extended Hamming distance between two strings never exceeds the standard Hamming distance between them, our result subsumes an earlier similar result on the Boolean matrix product in terms of the Hamming distance due to Bjorklund and Lingas [4]. We also observe that min{MWT(A),MWT(B-t)} = O(min{r(A),r(B)}), where r(A) and r(B) reflect the minimum number of rectangles required to cover ls in A and B, respectively. Hence, our result also generalizes the recent upper bound on the Boolean matrix product in terms of r(A) and r(B), due to Lingas [12].
|
|
| 49. |
- Gasieniec, Leszek, et al.
(författare)
-
Approximation algorithms for Hamming clustering problems
- 2004
-
Ingår i: Journal of Discrete Algorithms. - 1570-8667. ; 2:2 spec. iss., s. 289-301
-
Tidskriftsartikel (refereegranskat)abstract
- We study Hamming versions of two classical clustering problems. The Hamming radius p-clustering problem (HRC) for a set S of k binary strings, each of length n, is to find p binary strings of length n that minimize the maximum Hamming distance between a string in S and the closest of the p strings; this minimum value is termed the p-radius of S and is denoted by varrho. The related Hamming diameter p-clustering problem (HDC) is to split S into p groups so that the maximum of the Hamming group diameters is minimized; this latter value is called the p-diameter of S. We provide an integer programming formulation of HRC which yields exact solutions in polynomial time whenever k is constant. We also observe that HDC admits straightforward polynomial-time solutions when k=O(logn) and p=O(1), or when p=2. Next, by reduction from the corresponding geometric p-clustering problems in the plane under the L1 metric, we show that neither HRC nor HDC can be approximated within any constant factor smaller than two unless P=NP. We also prove that for any var epsilon>0 it is NP-hard to split S into at most pk1/7−var epsilon clusters whose Hamming diameter does not exceed the p-diameter, and that solving HDC exactly is an NP-complete problem already for p=3. Furthermore, we note that by adapting Gonzalez' farthest-point clustering algorithm [T. Gonzalez, Theoret. Comput. Sci. 38 (1985) 293–306], HRC and HDC can be approximated within a factor of two in time O(pkn). Next, we describe a 2O(pvarrho/var epsilon)kO(p/var epsilon)n2-time (1+var epsilon)-approximation algorithm for HRC. In particular, it runs in polynomial time when p=O(1) and varrho=O(log(k+n)). Finally, we show how to find in Image time a set L of O(plogk) strings of length n such that for each string in S there is at least one string in L within distance (1+var epsilon)varrho, for any constant 0
|
|
| 50. |
- Gasieniec, Leszek, et al.
(författare)
-
Efficient Assignment of Identities in Anonymous Populations
- 2022
-
Ingår i: 25th International Conference on Principles of Distributed Systems (OPODIS 2021). - 9783959772198 ; 217, s. 1-21
-
Konferensbidrag (refereegranskat)abstract
- We consider the fundamental problem of assigning distinct labels to agents in the probabilistic model of population protocols. Our protocols operate under the assumption that the size n of the population is embedded in the transition function. Their efficiency is expressed in terms of the number of states utilized by agents, the size of the range from which the labels are drawn, and the expected number of interactions required by our solutions. Our primary goal is to provide efficient protocols for this fundamental problem complemented with tight lower bounds in all the three aspects. W.h.p. (with high probability), our labeling protocols are silent, i.e., eventually each agent reaches its final state and remains in it forever, and they are safe, i.e., never update the label assigned to any single agent. We first present a silent w.h.p. and safe labeling protocol that draws labels from the range [1,2n]. Both the number of interactions required and the number of states used by the protocol are asymptotically optimal, i.e., O(n log n) w.h.p. and O(n), respectively. Next, we present a generalization of the protocol, where the range of assigned labels is [1,(1+ε) n]. The generalized protocol requires O(n log n / ε) interactions in order to complete the assignment of distinct labels from [1,(1+ε) n] to the n agents, w.h.p. It is also silent w.h.p. and safe, and uses (2+ε)n+O(n^c) states, for any positive c < 1. On the other hand, we consider the so-called pool labeling protocols that include our fast protocols. We show that the expected number of interactions required by any pool protocol is ≥ (n²)/(r+1), when the labels range is 1,… , n+r < 2n. Furthermore, we provide a protocol which uses only n+5√ n +O(n^c) states, for any c < 1, and draws labels from the range 1,… ,n. The expected number of interactions required by the protocol is O(n³). Once a unique leader is elected it produces a valid labeling and it is silent and safe. On the other hand, we show that (even if a unique leader is given in advance) any silent protocol that produces a valid labeling and is safe with probability > 1-(1/n), uses ≥ n+√{(n-1)/2}-1 states. Hence, our protocol is almost state-optimal. We also present a generalization of the protocol to include a trade-off between the number of states and the expected number of interactions. Finally, we show that for any silent and safe labeling protocol utilizing n+t < 2n states, the expected number of interactions required to achieve a valid labeling is ≥ (n²)/(t+1).
|
|
