| 1. |
- Adamaszek, Anna, et al.
(author)
-
Approximation schemes for capacitated geometric network design
- 2018
-
In: SIAM Journal on Discrete Mathematics. - 0895-4801. ; 32:4, s. 2720-2746
-
Journal article (peer-reviewed)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.
|
|
| 2. |
- Adamaszek, Anna, et al.
(author)
-
PTAS for k-tour cover poblem on the plane for moderately large values of k
- 2010
-
In: International Journal of Foundations of Computer Science. - 0129-0541. ; 21:6, s. 893-904
-
Journal article (peer-reviewed)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.
|
|
| 3. |
|
|
| 4. |
- Czumaj, Artur, et al.
(author)
-
Approximation algorithms for buy-at-bulk geometric network design
- 2011
-
In: Algorithms and data structures / Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 3642033660 ; 5664, s. 1949-1969
-
Conference paper (peer-reviewed)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.
|
|
| 5. |
- Czumaj, Artur, et al.
(author)
-
Fast approximation schemes for Euclidean multi-connectivity problems
- 2000
-
In: Automata, languages and programming / Lecture notes in computer science. - 3540677151 ; 1853, s. 856-868
-
Conference paper (peer-reviewed)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.
|
|
| 6. |
- Czumaj, Artur, et al.
(author)
-
Faster algorithms for finding lowest common ancestors in directed acyclic graphs
- 2007
-
In: Theoretical Computer Science. - : Elsevier BV. - 0304-3975. ; 380:1-2, s. 37-46
-
Journal article (peer-reviewed)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.
|
|
| 7. |
- Czumaj, Artur, et al.
(author)
-
Finding a heaviest triangle is no harder than matrix multiplication
- 2006
-
Reports (other academic/artistic)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).
|
|
| 8. |
- Czumaj, Artur, et al.
(author)
-
Finding a heaviest triangle is not harder than matrix multiplication
- 2007
-
In: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. - 9780898716245 ; , s. 986-994
-
Conference paper (peer-reviewed)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).
|
|
| 9. |
- Czumaj, Artur, et al.
(author)
-
Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
- 2009
-
In: SIAM Journal on Computing. - : Society for Industrial & Applied Mathematics (SIAM). - 0097-5397 .- 1095-7111. ; 39:2, s. 431-444
-
Journal article (peer-reviewed)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.
|
|
| 10. |
- Czumaj, Artur, et al.
(author)
-
Minimum k-connected geometric networks
- 2008
-
In: Encyclopedia of Algorithms. - Boston, MA : Springer US. - 9780387301624 ; , s. 536-538
-
Book chapter (other academic/artistic)
|
|
