Arrow Research search

Author name cluster

Artur Czumaj

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

49 papers
2 author rows

Possible papers

49

TCS Journal 2026 Journal Article

Parallel derandomization for coloring

  • Sam Coy
  • Artur Czumaj
  • Peter Davies-Peck
  • Gopinath Mishra

Graph coloring problems are among the most fundamental problems in parallel and distributed computing, and have been studied extensively in both settings. In this context, designing efficient deterministic algorithms for these problems has been found particularly challenging. In this work we consider this challenge, and design a novel framework for derandomizing algorithms for coloring-type problems in the Massively Parallel Computation (MPC) model with sublinear space. We give an application of this framework by showing that a recent ( d e g r e e + 1 ) -list coloring algorithm by Halldórsson, Kuhn, Nolin, and Tonoyan (STOC’22) in the LOCAL model of distributed computation can be translated to the MPC model and efficiently derandomized. Our algorithm runs in O(log log log n) rounds, which matches the complexity of the state of the art algorithm for the ( Δ + 1 ) -coloring problem.

Details DOI

TCS Journal 2024 Journal Article

Routing schemes for hybrid communication networks

  • Sam Coy
  • Artur Czumaj
  • Christian Scheideler
  • Philipp Schneider
  • Julian Werthmann

We consider the problem of computing routing schemes in the HYBRID model of distributed computing where nodes have access to two fundamentally different communication modes. In this problem nodes have to compute small labels and routing tables that allow for efficient routing of messages in the local network, which typically offers the majority of the throughput. Recent work has shown that using the HYBRID model admits a significant speed-up compared to what would be possible if either communication mode were used in isolation. Nonetheless, if general graphs are used as the input graph the computation of routing schemes still takes polynomial rounds in the HYBRID model. We bypass this lower bound by restricting the local graph to unit-disc-graphs and solve the problem deterministically with running time O ( | H | 2 + log ⁡ n ), label size O ( log ⁡ n ), and size of routing tables O ( | H | 2 ⋅ log ⁡ n ) where | H | is the number of “radio holes” in the network. Our work builds on recent work by Coy et al. , who obtain this result in the much simpler setting where the input graph has no radio holes. We develop new techniques to achieve this, including a decomposition of the local graph into path-convex regions, where each region contains a shortest path for any pair of nodes in it.

Details DOI

MFCS Conference 2023 Conference Paper

Modern Parallel Algorithms (Invited Talk)

  • Artur Czumaj

Recent advances in the design of efficient parallel algorithms have been largely focusing on the nowadays classical model of parallel computing called Massive Parallel Computation (MPC), which follows the framework of MapReduce systems. In this talk we will survey recent advances in the design of algorithms for graph problems for the MPC model and will mention some interesting open questions in this area.

Details

STOC Conference 2022 Conference Paper

Deterministic massively parallel connectivity

  • Sam Coy
  • Artur Czumaj

We consider the problem of designing fundamental graph algorithms on the model of Massive Parallel Computation (MPC). The input to the problem is an undirected graph G with n vertices and m edges, and with D being the maximum diameter of any connected component in G . We consider the MPC with low local space , allowing each machine to store only Θ( n δ ) words for an arbitrary constant δ>0, and with linear global space (which is the number of machines times the local space available), that is, with optimal utilization. In a recent breakthrough, Andoni et al. (FOCS’18) and Behnezhad et al. (FOCS’19) designed parallel randomized algorithms that in O (log D + loglog n ) rounds on an MPC with low local space determine all connected components of a graph, improving on the classic bound of O (log n ) derived from earlier works on PRAM algorithms. In this paper, we show that asymptotically identical bounds can be also achieved for deterministic algorithms: we present a deterministic MPC low local space algorithm that in O (log D + loglog n ) rounds determines connected components of the input graph. Our result matches the complexity of state of the art randomized algorithms for this task. The techniques developed in our paper can be also applied to several related problems, giving new deterministic MPC algorithms for problems like finding a spanning forest, minimum spanning forest, etc. We complement our upper bounds by extending a recent lower bound for connectivity on an MPC conditioned on the 1-vs-2-cycles conjecture (which requires D ≥ log 1+Ω(1) n ), by showing a related conditional hardness of Ω(log D ) MPC rounds for the entire spectrum of D , covering a particularly interesting range when D ≤ O (log n ).

Details

FOCS Conference 2022 Conference Paper

Streaming Facility Location in High Dimension via Geometric Hashing

  • Artur Czumaj
  • Shaofeng H. -C. Jiang
  • Robert Krauthgamer
  • Pavel Veselý 0001
  • Mingwei Yang 0002

In Euclidean Uniform Facility Location, the input is a set of clients in $\mathrm{R}^{d}$ and the goal is to place facilities to serve them, so as to minimize the total cost of opening facilities plus connecting the clients. We study the classical setting of dynamic geometric streams, where the clients are presented as a sequence of insertions and deletions of points in the grid $\{1, ldots\, \Delta \}^{d}$, and we focus on the high-dimensional regime, where the algorithm’s space complexity must be polynomial (and certainly not exponential) in $d \cdot \log \Delta$. We present a new algorithmic framework, based on importance sampling from the stream, for $O(1)$-approximation of the optimal cost using only poly $(d\cdot\log\Delta)$ space. This framework is easy to implement in two passes, one for sampling points and the other for estimating their contribution. Over random-order streams, we can extend this to a one-pass algorithm by using the two halves of the stream separately. Our main result, for arbitrary-order streams, computes $O(d^{1. 5})$-approximation in one pass by using the new framework but combining the two passes differently. This improves upon previous algorithms that either need space exponential in d or only guarantee $O(d\cdot\log^{2}\Delta)$-approximation, and therefore our algorithms for high-dimensional streams are the first to avoid the $O(\log\Delta)$ factor in approximation that is inherent to the widely-used quadtree decomposition. Our improvement is achieved by employing a geometric hashing scheme that maps points in $\mathbb{R}^{d}$ into buckets of bounded diameter, with the key property that every point set of small-enough diameter is hashed into at most poly $(d)$ distinct buckets. Finally, we complement our results with a proof that every streaming 1. 085-approximation algorithm requires space exponential in poly $(d \cdot log \Delta)$, even for insertion-only streams.

Details

FOCS Conference 2019 Conference Paper

A Characterization of Graph Properties Testable for General Planar Graphs with one-Sided Error (It's all About Forbidden Subgraphs)

  • Artur Czumaj
  • Christian Sohler

The problem of characterizing testable graph properties (properties that can be tested with a number of queries independent of the input size) is a fundamental problem in the area of property testing. While there has been some extensive prior research characterizing testable graph properties in the dense graphs model and we have good understanding of the bounded degree graphs model, no similar characterization has been known for general graphs, with no degree bounds. In this paper we take on this major challenge and consider the problem of characterizing all testable graph properties in general planar graphs. We consider the model in which a general planar graph can be accessed by the random neighbor oracle that allows access to any given vertex and access to a random neighbor of a given vertex. We show that, informally, a graph property P is testable with one-sided error for general planar graphs if and only if testing P can be reduced to testing for a finite family of finite forbidden subgraphs. While our presentation focuses on planar graphs, our approach extends easily to general minor-free graphs. Our analysis of the necessary condition relies on a recent construction of canonical testers in the random neighbor oracle model that is applied here to the one-sided error model for testing in planar graphs. The sufficient condition in the characterization reduces the problem to the task of testing H-freeness in planar graphs, and is the main and most challenging technical contribution of the paper: we show that for planar graphs (with arbitrary degrees), the property of being H-free is testable with one-sided error for every finite graph H, in the random neighbor oracle model.

Details

TCS Journal 2019 Journal Article

Leader election in multi-hop radio networks

  • Artur Czumaj
  • Peter Davies

In this paper we present a framework for leader election in multi-hop radio networks which yield randomized leader elections taking O ( broadcasting time ) in expectation, and another which yields algorithms taking fixed time of the order of O ( log ⁡ n ) -times broadcasting time. Both succeed with high probability. We show how to implement these frameworks in radio networks without collision detection, and in networks with collision detection (in fact in the strictly weaker beep model). In doing so, we obtain the first optimal expected-time leader election algorithms in both settings, and also improve the worst-case running time in directed networks without collision detection by an O ( log ⁡ n ) factor.

Details DOI

STOC Conference 2018 Conference Paper

Round compression for parallel matching algorithms

  • Artur Czumaj
  • Jakub Lacki
  • Aleksander Madry
  • Slobodan Mitrovic
  • Krzysztof Onak
  • Piotr Sankowski

For over a decade now we have been witnessing the success of massive parallel computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture the nature of large-scale computation. In particular, compared to the classic distributed algorithms or PRAM models, these frameworks allow for much more local computation. The fundamental question that arises in this context is though: can we leverage this additional power to obtain even faster parallel algorithms?

Details

STOC Conference 2016 Conference Paper

Relating two property testing models for bounded degree directed graphs

  • Artur Czumaj
  • Pan Peng 0001
  • Christian Sohler

We study property testing algorithms in directed graphs (digraphs) with maximum indegree and maximum outdegree upper bounded by d . For directed graphs with bounded degree, there are two different models in property testing introduced by Bender and Ron (2002). In the bidirectional model , one can access both incoming and outgoing edges while in the unidirectional model one can only access outgoing edges. In our paper we provide a new relation between the two models: we prove that if a property can be tested with constant query complexity in the bidirectional model, then it can be tested with sublinear query complexity in the unidirectional model. A corollary of this result is that in the unidirectional model (the model allowing only queries to the outgoing neighbors), every property in hyperfinite digraphs is testable with sublinear query complexity.

Details

IJCAI Conference 2015 Conference Paper

Approximate Nash Equilibria with Near Optimal Social Welfare

  • Artur Czumaj
  • Michail Fasoulakis
  • Marcin Jurdzinski

It is known that Nash equilibria and approximate Nash equilibria not necessarily optimize social optima of bimatrix games. In this paper, we show that for every fixed ε > 0, every bimatrix game (with values in [0, 1]) has an ε-approximate Nash equilibrium with the total payoff of the players at least a constant factor, (1 − √ 1 − ε)2, of the optimum. Furthermore, our result can be made algorithmic in the following sense: for every fixed 0 ≤ ε∗ < ε, if we can find an ε∗ -approximate Nash equilibrium in polynomial time, then we can find in polynomial time an ε-approximate Nash equilibrium with the total payoff of the players at least a constant factor of the optimum. Our analysis is especially tight in the case when ε ≥ 1 2. In this case, we show that for any bimatrix game there is an ε-approximate Nash equilibrium with constant size support whose social welfare is at least 2 √ ε − ε ≥ 0. 914 times the optimal social welfare. Furthermore, we demonstrate that our bound for the social welfare is tight, that is, for every ε ≥ 1 2 there is a bimatrix game for which every ε-approximate Nash equilibrium has social welfare at most 2 √ ε − ε times the optimal social welfare.

PDF Details

STOC Conference 2015 Conference Paper

Random Permutations using Switching Networks

  • Artur Czumaj

We consider the problem of designing a simple, oblivious scheme to generate (almost) random permutations. We use the concept of switching networks and show that almost every switching network of logarithmic depth can be used to almost randomly permute any set of (1-ε) n elements with any ε > 0 (that is, gives an almost (1-ε) n$-wise independent permutation). Furthermore, we show that the result still holds for every switching network of logarithmic depth that has some special expansion properties, leading to an explicit construction of such networks. Our result can be also extended to an explicit construction of a switching network of depth O(log 2 n) and with O(n log n) switches that almost randomly permutes any set of n elements. We also discuss basic applications of these results in cryptography. Our results are obtained using a non-trivial coupling approach to study mixing times of Markov chains which allows us to reduce the problem to some random walk-like problem on expanders.

Details

STOC Conference 2015 Conference Paper

Testing Cluster Structure of Graphs

  • Artur Czumaj
  • Pan Peng 0001
  • Christian Sohler

We study the problem of recognizing the cluster structure of a graph in the framework of property testing in the bounded degree model. Given a parameter ε, a d-bounded degree graph is defined to be (k, φ) -clusterable, if it can be partitioned into no more than k parts, such that the (inner) conductance of the induced subgraph on each part is at least φ and the (outer) conductance of each part is at most c d,k ε 4 φ 2 , where c d,k depends only on d,k. Our main result is a sublinear algorithm with the running time ~O(√n ⋅ poly(φ,k,1/ε)) that takes as input a graph with maximum degree bounded by d, parameters k, φ, ε, and with probability at least 2/3, accepts the graph if it is (k,φ)-clusterable and rejects the graph if it is ε-far from (k, φ*)-clusterable for φ* = c' d,k φ 2 ε 4 }/log n, where c' d,k depends only on d,k. By the lower bound of Ω(√n) on the number of queries needed for testing graph expansion, which corresponds to k=1 in our problem, our algorithm is asymptotically optimal up to polylogarithmic factors.

Details

SODA Conference 2013 Conference Paper

(1+ Є)-approximation for facility location in data streams

  • Artur Czumaj
  • Christiane Lammersen
  • Morteza Monemizadeh
  • Christian Sohler

We consider the Euclidean facility location problem with uniform opening cost. In this problem, we are given a set of n points P sube ℝ 2 and an opening cost f ∊ ℝ +, and we want to find a set of facilities F ⊆ ℝ 2 that minimizes where d ( p, q ) is the Euclidean distance between p and q. We obtain two main results: A (1 + ε)-approximation algorithm with running time which is ( n log 2 n log log n ) for any constant ε. The first (1 + ε)-approximation algorithm for the cost of the facility location problem for dynamic geometric data streams, i. e. , when the stream consists of insert and delete operations of points from a discrete space {1, …, Δ} 2. The streaming algorithm uses space. Our PTAS is significantly faster than any previously known (1 + ε)-approximation algorithm for the problem, and is also relatively simple. Our algorithm for dynamic geometric data streams is the first (1 + ε)-approximation algorithm for the cost of the facility location problem with polylogarithmic space, and it resolves an open problem in the streaming area. Both algorithms are based on a novel and simple decomposition of an input point set P into small subsets P i, such that: the cost of solving the facility location problem for each P i is small (which means that for each P i one needs to open only a small, polylogarithmic number of facilities), Σ i OPT( P i ) ≤ (1 + ε) · OPT( P ), where for a point set P, OPT( P ) denotes the cost of an optimal solution for P. The decomposition can be used directly to obtain the PTAS by splitting the point set in the subsets and efficiently solve the problem for each subset independently. By combining our partitioning with techniques to process dynamic data streams of sampling from the cells of the partition and estimating the cost from the sample, we obtain our data streaming algorithm.

Details

STOC Conference 2012 Conference Paper

Optimal online buffer scheduling for block devices

  • Anna Adamaszek
  • Artur Czumaj
  • Matthias Englert
  • Harald Räcke

We introduce a buffer scheduling problem for block operation devices in an online setting. We consider a stream of items of different types to be processed by a block device. The block device can process all items of the same type in a single step. To improve the performance of the system a buffer of size k is used to store items in order to reduce the number of operations required. Whenever the buffer becomes full a buffer scheduling strategy has to select one type and then a block operation on all elements with this type that are currently in the buffer is performed. The goal is to design a scheduling strategy that minimizes the number of block operations required. In this paper we consider the online version of this problem, where the buffer scheduling strategy must make decisions without knowing the future items that appear in the input stream. Our main result is the design of an O(log log k)-competitive online randomized buffer scheduling strategy. The bound is asymptotically tight. As a byproduct of our LP-based techniques, we obtain a randomized offline algorithm that approximates the optimal number of block operations to within a constant factor.

Details

STOC Conference 2011 Conference Paper

Almost tight bounds for reordering buffer management

  • Anna Adamaszek
  • Artur Czumaj
  • Matthias Englert
  • Harald Räcke

We give almost tight bounds for the online reordering buffer management problem on the uniform metric. Specifically, we present the first non-trivial lower bounds for this problem by showing that deterministic online algorithms have a competitive ratio of at least Ω(√{log k/log log k}) and randomized online algorithms have a competitive ratio of at least Ω(log log k), where k denotes the size of the buffer. We complement this by presenting a deterministic online algorithm for the reordering buffer management problem that obtains a competitive ratio of O(√log k), almost matching the lower bound. This improves upon an algorithm by Avigdor-Elgrabli and Rabani (SODA 2010) that achieves a competitive ratio of O(log k/ log log k).

Details

FOCS Conference 2011 Conference Paper

Planar Graphs: Random Walks and Bipartiteness Testing

  • Artur Czumaj
  • Morteza Monemizadeh
  • Krzysztof Onak
  • Christian Sohler

We initiate the study of the testability of properties in arbitrary planar graphs. We prove that bipartiteness can be tested in constant time. The previous bound for this class of graphs was O(√n), and the constant-time testability was only known for planar graphs with bounded degree. Previously used transformations of unbounded-degree sparse graphs into bounded- degree sparse graphs cannot be used to reduce the problem to the testability of bounded-degree planar graphs. Our approach extends to arbitrary minor-free graphs. Our algorithm is based on random walks. The challenge here is to analyze random walks for a class of graphs that has good separators, i. e. , bad expansion. Standard techniques that use a fast convergence to a uniform distribution do not work in this case. Roughly speaking, our analysis technique self-reduces the problem of finding an odd-length cycle in a multigraph G induced by a collection of cycles to another multigraph G' induced by a set of shorter odd-length cycles, in such a way that when a random walks finds a cycle in G' with probability p >; 0, then it does so with probability λ(p) >; 0 in G. This reduction is applied until the cycles collapse to self-loops that can be easily detected.

Details

SODA Conference 2010 Conference Paper

Testing Monotone Continuous Distributions on High-dimensional Real Cubes

  • Michal Adamaszek
  • Artur Czumaj
  • Christian Sohler

We study the task of testing properties of probability distributions. We consider a scenario in which we have access to independent samples of an unknown distribution with infinite (perhaps even uncountable) support. Our goal is to test whether has a given property or it is ε-far from it (in the statistical distance, with the L 1 -distance measure). It is not difficult to see that for many natural distributions on infinite or uncountable domains, no testing algorithm can exist and the central objective of our study is to understand if there are any nontrivial distributions that can be efficiently tested. For example, it is easy to see that there is no testing algorithm that tests if a given probability distribution on [0, 1] is uniform. We show however, that if some additional information about the input distribution is known, testing uniform distribution is possible. We extend the recent result about testing uniformity for monotone distributions on Boolean n -dimensional cubes by Rubinfeld and Servedio (STOC'2005) to the case of continuous [0, l] n cubes. We show that if a distribution on [0, l] n is monotone, then one can test if is uniform with the sample complexity ( n /ε 2 ). This result is optimal up to a polylogarithmic factor.

Details

TCS Journal 2007 Journal Article

Faster algorithms for finding lowest common ancestors in directed acyclic graphs

  • Artur Czumaj
  • Mirosław Kowaluk
  • Andrzej Lingas

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 O ( 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 O ( n 2 + λ ), where λ satisfies the equation ω ( 1, λ, 1 ) = 1 + 2 λ and ω ( 1, λ, 1 ) is the exponent of the multiplication of an n × n λ matrix by an n λ × n matrix. By the currently best known bounds on ω ( 1, λ, 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 α, where α ≈ 0. 294, our algorithm runs in a time that is asymptotically the same as that required for multiplying two n × n matrices, that is, O ( n ω ); we also prove that this running time is optimal even for dags of depth 1. For dags with depth h > n α, the running time of our algorithm is at most O ( n ω ⋅ h 0. 468 ). This algorithm is faster than our algorithm for arbitrary dags for all values of h ≤ n 0. 42.

Details DOI

FOCS Conference 2007 Conference Paper

Testing Expansion in Bounded-Degree Graphs

  • Artur Czumaj
  • Christian Sohler

We consider the problem of testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion: an alpha-expander is a graph G = (V, E) in which even-subset U sube V of at most |V|/2 vertices has a neighborhood of size at least alphaldr|U|. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time O tilde(radicn). We prove that the property testing algorithm proposed by Goldreich and Ron (2000) with appropriately set parameters accepts every alpha-expander with probability at least 2/3 and rejects every graph that is epsiv-far from an alpha*-expander with probability at least 2/3, where alpha*=Theta(alpha 2 /(d 2 log (n/epsiv))) and d is the maximum degree of the graphs. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is O(d 2 (radicn log (n/epsiv))/alpha 2 epsiv 3 ).

Details

TCS Journal 2005 Journal Article

Testing hypergraph colorability

  • Artur Czumaj
  • Christian Sohler

We study the problem of testing properties of hypergraphs. The goal of property testing is to distinguish between the case whether a given object has a certain property or is “far away” from the property. We prove that the fundamental problem of ℓ -colorability of k-uniform hypergraphs can be tested in time independent of the size of the hypergraph. We present a testing algorithm that examines only ( k ℓ / ε ) O ( k ) entries of the adjacency matrix of the input hypergraph, where ε is a distance parameter independent of the size of the hypergraph. The algorithm tests only a constant number of entries in the adjacency matrix provided that ℓ, k, and ε are constants. This result is a generalization of previous results about testing graph colorability.

Details DOI

STOC Conference 2004 Conference Paper

Estimating the weight of metric minimum spanning trees in sublinear-time

  • Artur Czumaj
  • Christian Sohler

In this paper we present a sublinear time (1 + ε)-approximation randomized algorithm to estimate the weight of the minimum spanning tree of an n -point metric space. The running time of the algorithm is Û ( n /ε O(1) ). Since the full description of an n -point metric space is of size Θ( n 2 ), the complexity of our algorithm is sublinear with respect to the input size. Our algorithm is almost optimal as it is not possible to approximate in o ( n ) time the weight of the minimum spanning tree to within any factor. Furthermore, it has been previously shown that no o ( n 2 ) algorithm exists that returns a spanning tree whose weight is within a constant times the optimum.

Details

FOCS Conference 2003 Conference Paper

Broadcasting Algorithms in Radio Networks with Unknown Topology

  • Artur Czumaj
  • Wojciech Rytter

In this paper we present new randomized and deterministic algorithms for the classical problem of broadcasting in radio networks with unknown topology. We consider directed n-node radio networks with specified eccentricity D (maximum distance from the source node to any other node). Our first main result closes the gap between the lower and upper bound: we describe an optimal randomized broadcasting algorithm whose running time complexity is O(D log(n/D) + log/sup 2/n), with high probability. In particular, we obtain a randomized algorithm that completes broadcasting in any n-node radio network in time O(n), with high probability. The main source of our improvement is a better "selecting sequence" used by the algorithm that brings some stronger property and improves the broadcasting time. Next, we demonstrate how to apply our approach to deterministic broadcasting, and describe a deterministic oblivious algorithm that completes broadcasting in almost optimal time O(n log/sup 2/D). Finally, we show how our randomized broadcasting algorithm can be used to improve the randomized complexity of the gossiping problem.

Details

TCS Journal 2003 Journal Article

On polynomial-time approximation algorithms for the variable length scheduling problem

  • Artur Czumaj
  • Leszek Ga̧sieniec
  • Daya Ram Gaur
  • Ramesh Krishnamurti
  • Wojciech Rytter
  • Michele Zito

This paper may be viewed as a corrigendum as well as an extension of the paper by (Czumaj et al. , Theoret. Comput. Sci. 262 (1–2), (2001) 569–582) where they deal with the variable length scheduling problem (VLSP) with parameters k 1, k 2, denoted VLSP(k 1, k 2). In the current paper, we first discuss an error in the analysis of one of the approximation algorithms described in (Czumaj et al. , Theoret. Comput. Sci. 262 (1–2), (2001) 569–582), where an approximation algorithm for VLSP(k 1, k 2), k 1<k 2, was presented and it was claimed that the algorithm achieves the approximation ratio of 1+(k 1(k 2−k 1))/k 2. In this paper we give a problem instance for which the same algorithm obtains the approximation ratio ≈ k2 k1. We then present two simple approximation algorithms, one for the case k1 =1 with an approximation ratio of 2, and one for the case k 1>1 with an approximation ratio of 2+(k 2/2k 1). This corrects the result claimed in (Czumaj et al. , Theoret. Comput. Sci. 262 (1–2), (2001) 569–582).

Details DOI

FOCS Conference 2002 Conference Paper

Abstract Combinatorial Programs and Efficient Property Testers

  • Artur Czumaj
  • Christian Sohler

Property testing is a relaxation of classical decision problems which aims at distinguishing between functions having a predetermined property and functions being far from any function having the property. In this paper we present a novel framework for analyzing property testing algorithms with one-sided error. Our framework is based on a connection of property testing and a new class of problems which we call abstract combinatorial programs. We show that if the problem of testing a property can be reduced to an abstract combinatorial program of small dimension, then the property has an efficient tester. We apply our framework to a variety of classical combinatorial problems. Among others, we present efficient property testing algorithms for geometric clustering problems, the reversal distance problem, and graph and hypergraph coloring problems. We also prove that, informally, any hereditary graph property can be efficiently tested if and only if it can be reduced to an abstract combinatorial program of small size. Our framework allows us to analyze all our testers in a unified way and the obtained complexity bounds either match or improve the previously known bounds. We believe that our framework will help to better understand the structure of efficiently testable properties.

Details

STOC Conference 2002 Conference Paper

Selfish traffic allocation for server farms

  • Artur Czumaj
  • Piotr Krysta
  • Berthold Vöcking

We investigate the price of selfish routing in non-cooperative networks in terms of the coordination and bicriteria ratios in the recently introduced game theoretic network model of Koutsoupias and Papadimitriou. We present the first thorough study of this model for general, monotone families of cost functions and for cost functionsm from Queueing Theory. Our main results can be summarized as follows. We give a precise characterization of cost functions having a bounded/unbounded coordination ratio. For example, cost functions that describe the expected delay in queueing systems have an unbounded coordination ratio.

Details

TCS Journal 2001 Journal Article

Efficient web searching using temporal factors

  • Artur Czumaj
  • Ian Finch
  • Leszek Ga̧sieniec
  • Alan Gibbons
  • PAUL LENG
  • Wojciech Rytter
  • Michele Zito

We study the issues involved in the design of algorithms for performing information gathering more efficiently, by taking advantage of anticipated variations in access times in different regions at different times of the day or week. We look at the problem theoretically, as a generalisation of single processor sequencing with release times and deadlines, in which performance times (lengths) of the tasks can change in time. The new problem is called Variable Length Sequencing Problem (VLSP). We show that although the decision version of VLSP seems to be intractable in the general case, it can be solved optimally for lengths 1 and 2. This result opens the possibility of practicable algorithms to schedule searches efficiently when expected access times can be categorised as either slow or fast. Some algorithms for more general cases are examined and complexity results derived.

Details DOI

TCS Journal 2000 Journal Article

Algorithms for the parallel alternating direction access machine

  • Bogdan S. Chlebus
  • Artur Czumaj
  • Leszek Ga̧sieniec
  • Mirosław Kowaluk
  • Wojciech Plandowski

We describe a number of algorithms for the model for parallel computation called parallel alternating-direction access machine (padam). This model has the memory modules of the global memory arranged as a two-dimensional array, with each processor assigned to a row and a column, the processors can switch synchronously between row and column access modes. We study the issues of inter-processor communication and of efficient use of memory on the padam, and develop: an optimal routing scheme among memory modules, algorithms enhancing random access of processors to all memory blocks, and general simulations of shared memory machines. Finally, we present optimal algorithms for the problems of selection, merging, and sorting.

Details DOI

FOCS Conference 1997 Conference Paper

Randomized Allocation Processes

  • Artur Czumaj
  • Volker Stemann

We investigate various randomized processes allocating balls into bins that arise in applications in dynamic resource allocation and on-line load balancing. We consider the scenario when m balls arriving sequentially are to be allocated into n bins on-line and without using a global controller. Traditionally, the main aim of allocation processes is to place the balls into bins to minimize the maximum load in bins. However in many applications it is equally important to minimize the number of trails performed by the balls (the allocation time). We study adaptive allocation schemes that achieve optimal tradeoffs between the maximum load, the maximum allocation time, and the average allocation time. We investigate allocation processes that may reallocate the balls. We provide a tight analysis of the maximum load of processes that during placing a new ball may reassign the balls in up to d randomly chosen bins. We study infinite processes, in which in each step a random ball is removed and a new ball is placed according to some scheduling rule. We present a novel approach that establishes a tight estimation of the time needed for the infinite process to be in the state near to its equilibrium. Finally, we provide a tight analysis of the maximum load of the off-line process in which each ball may be placed into one of d randomly chosen bins. We apply this result to competitive analysis of on-line load balancing processes.

Details

I&C Journal 1997 Journal Article

Simulating Shared Memory in Real Time: On the Computation Power of Reconfigurable Architectures

  • Artur Czumaj
  • Friedhelm Meyer auf der Heide
  • Volker Stemann

We consider randomized simulations of shared memory on a distributed memory machine (DMM) where thenprocessors and thenmemory modules of the DMM are connected via a reconfigurable architecture. We first present a randomized simulation of a CRCW PRAM on a reconfigurable DMM having a complete reconfigurable interconnection. It guarantees delay O (log*n), with high probability. Next we study a reconfigurable mesh DMM (RM-DMM). Here thenprocessors andnmodules are connected via ann×nreconfigurable mesh. It was already known that ann×mreconfigurable mesh can simulate in constant time ann-processor CRCW PRAM with shared memory of sizem. In this paper we present a randomized step by step simulation of a CRCW PRAM with arbitrarily large shared memory on an RM-DMM. It guarantees constant delay with high probability, i. e. , it simulates in real time. Finally we prove a lower bound showing that sizeΩ(n 2) for the reconfigurable mesh is necessary for real time simulations.

Details DOI

TCS Journal 1996 Journal Article

Guthrie's problem: new equivalences and rapid reductions

  • Artur Czumaj
  • Alan Gibbons

In 1977, Appel and Haken proved that every planar graph is four vertex colourable which finally proved Guthrie's conjecture of circa 1852 that four colours are always sufficient. Their proof is very long and the implicit algorithm for four colouring is rather impractical. This paper provides a new characterisation of the four-colour problem by showing that it is equivalent (by an optimally fast reduction) to a simply stated problem of 3-edge colouring pairs of trees. This new problem, in turn, is equivalent to nontrivial subclasses of other problems in mathematics and computer science of which we describe three. These are problems of intersection of regular languages, of integer linear equations and of algebraic expressions. In the general case, all these problems require exponential time to solve. We show that if these problems are defined on pairs of trees, then polynomial time is sufficient. In addition, these problems offer enticing opportunities in the search for a shorter proof of the four-colour theorem and for more practical algorithms for four-colouring planar graphs.

Details DOI

MFCS Conference 1996 Conference Paper

Parallel Alternating-Direction Access Machine

  • Bogdan S. Chlebus
  • Artur Czumaj
  • Leszek Gasieniec
  • Miroslaw Kowaluk
  • Wojciech Plandowski

Abstract This paper presents a theoretical study of a model of parallel computations called Parallel Alternating-Direction Access Machine ( Padam ). Padam is an abstraction of the multiprocessor computers Adena /adenart and a prototype architecture usc/omp. The main feature of Padam is the organization of access to the global memory: (1) the memory modules are arranged as a 2-dimensional array, (2) each processor is assigned to a row and a column, (3) the processors switch synchronously between row and column access modes, and can access any of the assigned modules in each mode without conflicts. Since the padam processors have such a restricted access to the partially shared memory, developing tools to enhance flexibility of access to the memory is important. The paper concentrates on these issues.

Details
v2026.09.13