Artur Czumaj

How to Increase the Acceptance Ratios of Top Conferences? (2008)

a maximum-weight vertex-weighted triangle is not

Graham Cormode, Artur Czumaj, S. Muthukrishnan

In the beginning was the pub. This work was triggered by a pub conversation where the authors observed that many resumés list acceptance ratios of conferences where their papers appear 4, boasting...

ABSTRACT Selfish Traffic Allocation for Server Farms ∗ (2008)

The min-sum k-clustering problem is to partition a metric space (P,d) into k clusters C1,...,Ck ⊆ P such that �k � i=1 d(p,q) is minimized. We show the first efficient construction of a coreset...

Computing Equilibria for Congestion Games (2008)

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...

Rene Beier, Artur Czumaj

with (Im)perfect Information

Property Testing in Computational Geometry (Extended Abstract) (2008)

ABSTRACT Selfish Traffic Allocation for Server Farms (2008)

Abstract. We consider the notion of property testing as applied to computational geometry. We aim at developing efficient algorithms which determine whether a given (geometrical) object has a...

Property Testing with Geometric Queries (Extended Abstract) ⋆ (2008)

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...

Testing Geometric Properties (2008)

Abstract. This paper investigates geometric problems in the context of property testing algorithms. Property testing is an emerging area in computer science in which one is aiming at verifying...

Testing hereditary properties of non-expanding bounded-degree graphs (2008)

In this paper we study property testing for basic geometric properties. We aim at developing efficient algorithms which determine whether a given (geometrical) object has a predetermined property Q...

Artur Czumaj, Asaf Shapira, Christian Sohler

We study graph properties which are testable for bounded degree graphs in time independent of the input size. Our goal is to distinguish between graphs having a predetermined graph property and...

Abstract Efficient kinetic data structures for MaxCut (2008)

Artur Czumaj, Gereon Frahling, Christian Sohler

We develop a randomized kinetic data structure that maintains a partition of the moving points into two sets such that the corresponding cut is with probability at least 1−ϱ a...

Approximation algorithms for optimization problems in (2008)

We consider the problem of testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion: an α-expander is a graph G = (V, E) in which every subset U ⊆ V of at most |V|/2...

Artur Czumaj, Magnús M. Halldórsson, Andrzej Lingas, Johan Nilsson

graphs with superlogarithmic treewidth

(Draft – not for distribution) On the Expected Payment of Mechanisms for Task Allocation (2008)

Artur Czumaj, Amir Ronen

We study a representative task allocation problem called shortest paths: Let G be a graph in which the edges are owned by self interested agents. The cost of each edge is privately known to its...

Computing Equilibria for Congestion Games (2008)

Rene Beier, Artur Czumaj

with (Im)perfect Information

Abstract Computing Equilibria for Congestion Games with (Im)perfect Information ∗ (2008)

Rene Beier, Artur Czumaj, Piotr Krysta, Berthold Vöcking

We study algorithmic questions concerning a basic microeconomic congestion game in which there is a single provider that offers a service to a set of potential customers. Each customer has a...

Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time (2008)

Artur Czumaj, Ilan Newman, Funda Ergün, Ronitt Rubinfeld, Lance Fortnow, Avner Magen, ...

We consider the problem of computing the weight of a Euclidean minimum spanning tree for a ¦ set of §© ¨ points in. We focus on the setting where the input point set is supported by certain basic...

ABSTRACT Balanced Allocations: The Heavily Loaded Case (2008)

Petra Berenbrink, Artur Czumaj

We investigate load balancing processes based on the multiplechoice paradigm. In these randomized processes ¤ balls are inserted into ¥ bins. In the classical single-choice variant each ball is...

Artur Czumaj, Mirosław Kowaluk, Andrzej Lingas

We present a novel analysis of a random sampling approach for four clustering problems in metric spaces: k-median, k-means, min-sum k-clustering, and balanced k-median. For all these problems we...

in (2008)

algorithms for finding lowest common ancestors

Abstract Sublinear-Time Approximation of Euclidean Minimum Spanning Tree (2008)

We present a new algorithm for solving the all-pairs lowest common ancestor problem in directed acyclic graphs (dags). Our algorithm runs in time O(n 2+λ), where λ satisfies the equation ω(1, λ,...

Artur Czumaj, Funda Ergün, Ronitt Rubinfeld

We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of ¦ points in §© ¨. We focus on the situation when the input point set is supported by certain...

ABSTRACT Selfish Traffic Allocation for Server Farms ∗ (2008)

Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time ∗ (2008)

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...

Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, ...

We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in R d. We focus on the setting where the input point set is supported by certain basic (and...

Computing Equilibria for a Service Provider Game with (Im)perfect Information ∗ (2008)

Rene Beier, Artur Czumaj, Piotr Krysta, Berthold Vöcking

We study fundamental algorithmic questions concerning the complexity of market equilibria under perfect and imperfect information by means of a basic microeconomic game. Suppose a provider offers a...

Approximation Schemes for Minimum-Cost k-Connectivity (2008)

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...

Problems In Geometric, Artur Czumaj, Andrzej Lingas

this paper. Note that, in particular, this includes the Steiner tree problem (see, e.g., [2]), in which {0, 1} for any vertex v V . It also includes the most widely applied variant of the...

Estimating the Weight of Metric Minimum Spanning (2008)

Finding a Heaviest Triangle is not Harder than (2008)

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...

Matrix Multiplication Artur, Artur Czumaj, Andrzej Lingas

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 is the exponent of fastest matrix...

Computing Equilibria for Congestion Games (2008)

With Im Perfect, Rene Beier, Artur Czumaj, Piotr Krysta, Berthold Vöcking

We study algorithmic questions concerning a basic microeconomic congestion game in which there is a single provider that offers a service to a set of potential customers. Each customer has a...

Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time (2008)

Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, ...

We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in R^d. We focus on the setting where the input point set is supported by certain basic (and...

08341 Executive Summary -- Sublinear Algorithms (2008)

Czumaj, Artur, Muthukrishnan, S. Muthu, Rubinfeld, Ronitt, Sohler, Christian

This report summarizes the content and structure of the Dagstuhl seminar `Sublinear Algorithms', which was held from 17.8.2008 to 22.8.2008 in Schloss Dagstuhl, Germany.

08341 Abstracts Collection -- Sublinear Algorithms (2008)

Czumaj, Artur, Muthukrishnan, S. Muthu, Rubinfeld, Ronitt, Sohler, Christian

From August 17 to August 22, 2008, the Dagstuhl Seminar 08341 ``Sublinear Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar,...

and (2007)

Dany Breslauer, Artur Czumaj, Devdatt P. Dubhashi

Most of the work was done at the University of Paderborn. In this paper we study the problem of simulating shared memory on the Distributed Memory Machine (DMM). Our approach uses multiple copies of...

yx-- (2007)

zx--This note provides general transformations of lower bounds in Valiant's parallel comparison decision tree model to lower bounds in the priority concurrent-read concurrent-write...

Randomized Allocation Processes (EXTENDED ABSTRACT) (2007)

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...

2 (2007)

Property Testing in Computational Geometry (Extended Abstract) (2007)

Abstract. We consider the problem of simulating a PRAM on a distributed memory machine (DMM). Our main result is a randomized algorithm that simulates each step of an n-processor CRCW PRAM on an...

Authors ' Addresses (2007)

Abstract. We consider the notion of property testing as applied to computational geometry. We aim at developing efficient algorithms which determine whether a given (geometrical) object has a...

Berthold Vocking, Artur Czumaj, Artur Czumaj, Piotr Krysta, Piotr Krysta

We study the price of selfish routing in non-cooperative networks like the Internet. In particular, we investigate the price of selfish routing using the coordination ratio and other (e.g.,...

y (2007)

Artur Czumaj, Funda Ergun, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, ...

We consider the problem of estimating the weight of a Euclidean minimum spanning tree for a set of n points in R

y Max-Planck-Institut fur Informatik (2007)

Artur Czumaj, Berthold V Ocking

The coordination ratio is a game theoretic measure that aims to reflect the price of selfish routing in a network. We show that the worst-case coordination ratio on m parallel links (of possibly...

Science thesis: Analysis of Parallel Algorithms for Dynamic Programming Problem (2007)

Artur Czumaj, Personal Full, Name Artur, Piotr Czumaj

in Computer Graduated with honors (summa cum laude)

y Max-Planck-Institut fur Informatik (2007)

Artur Czumaj, Berthold V Ocking

The coordination ratio is a game theoretic measure that aims to reflect the price of selfish routing in a network. We show that the worst-case coordination ratio on m parallel links (of possibly...

Problem (2007)

Artur Czumaj, Education M. Sc

Research interest

!2E Pr[f!g]. (2007)

Euclidean graphs in R (2007)

Basic facts from probability theory This note presents basic facts from probability theory. We do not want to give here formal description and shall not pretend for completeness. For a more complete...

Fast approximation schemes for Euclidean minimum-cost multi-connectivity (2007)

We present the first truly polynomial-time approximation scheme (PTAS) for the minimum-cost k-vertex- (or, k-edge-) connected spanning subgraph problem for complete

Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time (2007)

We present fast approximation algorithms for various variants of the minimum-cost k-connected spanning subgraph problem in geometrical graphs. We provide a randomized approximation scheme for nding a...

Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, ...

We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in R . We focus on the setting where the input point set is supported by certain basic (and...

How to Increase the Acceptance Ratios of Top Conferences? (2007)

Graham Cormode, Artur Czumaj, S. Muthukrishnan

In the beginning was the pub. This work was triggered by a pub conversation where the authors observed that many resumes list acceptance ratios of conferences where their papers appear, boasting the...

Testing Euclidean minimum spanning trees in the plane (2007)

Testing Euclidean Minimum Spanning Trees in the Plane + (2007)

Given a Euclidean graph G over a set P of n points in the plane, we are interested in verifying whether G is a Euclidean minimum spanning tree (EMST) of P or G differs from it in more than ǫn edges....

Towards Generic Low Payment Mechanisms for Task (2006)

Given a Euclidean graph G over a set P of n points in the plane, we are interested in verifying whether G is an Euclidean minimum spanning tree (EMST) of P or G differs from it in more than # n...

Abstract (2007)

Artur Czumaj, Xin Wang

The line-of-sight networks is a network model introduced recently by Frieze et al. (SODA’07). It considers scenarios of wireless networks in which the underlying environment has a large number of...

Allocation Artur Czumaj, Artur Czumaj, Amir Ronen

We study the problem of procuring a cheap path in a graph in which the edges are owned by selfinterested agents. We focus on basic properties of a class of generalized Vickrey-Clarke mechanisms for...

Sublinear-time algorithms (2006)

Computing Equilibria for a Service Provider Game with (Im)perfect Information (2006)

In this paper we survey recent advances in the area of sublinear-time algorithms. 1

Beier, René, Czumaj, Artur, Krysta, Piotr, Vöcking, Berthold

We study fundamental algorithmic questions concerning the complexity of market equilibria under perfect and imperfect information by means of a basic microeconomic game. Suppose a provider offers a...

05291 Abstracts Collection -- Sublinear Algorithms (2006)

Czumaj, Artur, Muthukrishnan, S. Muthu, Rubinfeld, Ronitt, Sohler, Christian

From 17.07.05 to 22.07.05, the Dagstuhl Seminar 05291 ``Sublinear Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several...

Approximation Schemes for Minimum 2-Connected Spanning Subgraphs in Weighted Planar Graphs (2005)

Berger, Andre, Czumaj, Artur, Grigni, Michelangelo, Zhao, Hairong

Approximation schemes for minimum 2-connected spanning subgraphs in weighted planar graphs (2005)

André Berger, Artur Czumaj, Michelangelo Grigni, Hairong Zhao

Abstract. We present new approximation schemes for various classical problems of finding the minimum-weight spanning subgraph in edge-weighted undirected planar graphs that are resistant to edge or...

Facility location in sublinear time (2005)

Mihai Bădoiu, Artur Czumaj, Piotr Indyk, Christian Sohler

Abstract. In this paper we present a randomized constant factor approximation algorithm for the problem of computing the optimal cost of the metric Minimum Facility Location problem, in the case of...

Approximation schemes for minimum 2-connected spanning subgraphs in weighted planar graphs (2005)

André Berger, Artur Czumaj, Michelangelo Grigni, Hairong Zhao

Abstract. We present new approximation schemes for various classical problems of finding the minimum-weight spanning subgraph in edge-weighted undirected planar graphs that are resistant to edge or...

Computing Equilibria for Congestion Games with (Im)perfect Information (2004)

Beier,Rene, Krysta,Piotr, Czumaj,Artur, Vöcking,Berthold

We study algorithmic questions concerning a basic microeconomic congestion game in which there is a single provider that offers a service to a set of potential customers. Each customer has a...

Computing Equilibria for Congestion Games with (Im)perfect Information (2004)

Beier, Rene, Krysta, Piotr, Czumaj, Artur, Vöcking, Berthold

We study algorithmic questions concerning a basic microeconomic congestion game in which there is a single provider that offers a service to a set of potential customers. Each customer has a...

Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs (2004)

Artur Czumaj, Michelangelo Grigni, Papa Sissokho, Hairong Zhao

Given an undirected graph, finding either a minimum 2-edge-connected spanning subgraph or a minimum 2vertex-connected (biconnected) spanning subgraph is MaxSNP-hard. We show that for planar graphs,...

Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs (2004)

Artur Czumaj, Michelangelo Grigni, Papa Sissokho, Hairong Zhao

Given an undirected graph, finding either a minimum 2-edge-connected spanning subgraph or a minimum 2vertex-connected (biconnected) spanning subgraph is MaxSNP-hard. We show that for planar graphs,...

On the Expected Payment of Mechanisms for Task Allocation (2004)

Artur Czumaj, Amir Ronen

We study a generic task allocation problem called shortest paths: Let G be a directed graph in which the edges are owned by self interested agents. Each edge has an associated cost that is privately...

Approximation Schemes for Minimum 2-Edge-Connected and (2004)

Biconnected Subgraphs In, Artur Czumaj, Michelangelo Grigni, Papa Sissokho, Hairong Zhao

Given an undirected graph, finding either a minimum 2-edge-connected spanning subgraph or a minimum 2vertex -connected (biconnected) spanning subgraph is MaxSNP-hard. We show that for planar graphs,...

Selfish routing on the Internet (2004)

Sublinear-Time Approximation for Clustering via (2004)

In large-scale communication networks, like the Internet, it is usually impossible to globally manage network traffic. In the absence of global control it is typically assumed in traffic modeling...

Random Sampling Artur, Artur Czumaj, Christian Sohler

In this paper we present a novel analysis of a random sampling approach for three clustering problems in metric spaces: k-median, min-sum k- clustering, and balanced k-median. For all these problems...

On the Expected Payment of Mechanisms for Task Allocation (2004)

Artur Czumaj, Amir Ronen

We study a generic task allocation problem called shortest paths: Let G be a directed graph in which the edges are owned by self interested agents. Each edge has an associated cost that is privately...

Approximate minimum 2-connected subgraphs in weighted planar graphs (2004)

Andre Berger, André Berger, Artur Czumaj, Artur Czumaj, Michelangelo Grigni, Michelangelo Grigni, ...

We consider the problems of finding the minimum-weight 2-connected spanning subgraph in edge-weighted planar graphs and its variations. We first give a PTAS for the problem of finding minimum-weight...

Sublinear-time approximation for clustering via random sampling (2004)

Computing Equilibria for Congestion Games with (Im)perfect Information (2004)

Abstract. In this paper we present a novel analysis of a random sampling approach for three clustering problems in metric spaces: k-median, min-sum kclustering, and balanced k-median. For all these...

Beier, Rene, Krysta, Piotr, Czumaj, Artur, Vöcking, Berthold

We study algorithmic questions concerning a basic microeconomic congestion game in which there is a single provider that offers a service to a set of potential customers. Each customer has a...

Improved approximation algorithms for optimization problems in graphs with superlogarithmic treewidth (2003)

Artur Czumaj, Andrzej Lingas, Johan Nilsson

In this paper we present two novel generic schemes for approximation algorithms for optimization to partial k-trees. Our first scheme yields deterministic polynomialtime algorithms achieving...

Perfectly Balanced Allocation (2003)

Artur Czumaj, Chris Riley, Christian Scheideler

We investigate randomized processes underlying load balancing based on the multiple-choice paradigm: m balls have to be placed in n bins, and each ball can be placed into one out of 2 randomly...

Broadcasting Algorithms in Radio Networks with Unknown Topology (2003)

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...

Broadcasting Algorithms in Radio Networks with (2003)

Unknown Topology Artur, 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...

Perfectly Balanced Allocation (2003)

Artur Czumaj, Chris Riley, Christian Scheideler

We investigate randomized processes underlying load balancing based on the multiple-choice paradigm: m balls have to be placed in n bins, and each ball can be placed into one out of 2 randomly...

Sublinear-Time Approximation of Euclidean Minimum Spanning Tree (2003)

Artur Czumaj, Funda Ergun, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, ...

We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in R^d. We focus on the situation when the input point set is supported by certain basic...

Broadcasting algorithms in radio networks with unknown topology (2003)

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...

Abstract (2003)

Artur Czumaj, Hairong Zhao

We present two new results about vertex and edge fault-tolerant spanners in Euclidean spaces. We describe the first construction of vertex and edge fault-tolerant spanners having optimal bounds for...

Abstract (2003)

Selfish Traffic Allocation for Server Farms (2002)

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...

Czumaj,Artur, Krysta,Piotr, Vöcking,Berthold

Tight bounds for worst-case equilibria (2002)

Czumaj,Artur, Vöcking,Berthold

Selfish Traffic Allocation for Server Farms (2002)

Czumaj, Artur, Krysta, Piotr, Vöcking, Berthold

Tight bounds for worst-case equilibria (2002)

Czumaj, Artur, Vöcking, Berthold

Polynomial-time approximation schemes for the Euclidean survivable network design problem (2002)

Artur Czumaj, Andrzej Lingas, Hairong Zhao

Abstract. The survivable network design problem is a classical problem in combinatorial optimization of constructing a minimum-cost subgraph satisfying predetermined connectivity requirements. In...

Selfish traffic allocation for server farms (2002)

Artur Czumaj, Piotr Krysta, Berthold V Ocking

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...

Tight Bounds for Worst-Case Equilibria (2002)

Artur Czumaj New, Artur Czumaj, Berthold Vöcking

We study the problem of traffic routing in non-cooperative networks. In such networks, users may follow selfish strategies to optimize their own performance measure and therefore their behavior does...

Tight Bounds for Worst-Case Equilibria (2002)

Artur Czumaj, Berthold Vöcking

We study the problem of traffic routing in non-cooperative networks. In such networks, users may follow selfish strategies to optimize their own performance measure and therefore their behavior does...

Abstract combinatorial programs and efficient property testers (2002)

Tight Bounds for Worst-Case Equilibria (2002)

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...

Testing hypergraph coloring (2001)

The coordination ratio is a game theoretic measure that aims to reflect the price of selfish routing in a network. We show that the worst-case coordination ratio on ¢ parallel links (of possibly...

Property testing with geometric queries (2001)

Abstract. In this paper we initiate the study 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...

Testing hypergraph coloring (2001)

This paper investigates geometric problems in the context of property testing algorithms. Property testing is an emerging area in computer science in which one is aiming at verifying whether a given...

Artur Czumaj, Artur Czumaj, Christian Sohler, Christian Sohler

1

Switching Networks for Generating Random Permutations (2001)

Artur Czumaj, Przemka Kanarek, Krzysztof Lorys, Mirosław Kutyłowski

Soft Kinetic Data Structures (2001)

Testing Hypergraph Coloring (2001)

We introduce the framework of soft kinetic data structures (SKDS). A soft kinetic data structure is an approximate data structure that can be used to answer queries on a set of moving objects with...

Artur Czumaj, Christian Sohler, Contact Christian Sohler, Artur Czumaj, Christian Sohler

In this paper we initiate the study 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...

Fast Approximation Schemes for Euclidean Multi-Connectivity Problems (2000)

Czumaj, Artur, Lingas, Andrzej

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...

Coloring Nonuniform Hypergraphs: A New Algorithmic Approach to the General (2000)

Balanced Allocations: The Heavily Loaded Case (2000)

The Lovasz Local Lemma is a sieve method to prove the existence of certain structures with certain prescribed properties. In most of its applications the Lovasz Local Lemma does not supply a...

Petra Berenbrink, Artur Czumaj, Angelika Steger, Berthold V Ocking

x We investigate load balancing processes based on the multiplechoice paradigm. In these randomized processes m balls are inserted into n bins. In the classical single-choice variant each ball is...

Infinite Parallel Job Allocation (Extended Abstract) (2000)

Petra Berenbrink, Artur Czumaj, Tom Friedetzky, Nikita D. Vvedenskaya

) Petra Berenbrink Dept. of Mathematics & Computer Science Paderborn University D-33095 Paderborn, Germany pebe@uni-paderborn.de Artur Czumaj y Department of Computer and Information Science New...

A New Algorithmic Approach to the General Lovász Local Lemma with Applications to Scheduling and Satisfiability Problems (Extended Abstract) (2000)

On the Complexity of Determining the Period of a String (2000)

] y Artur Czumaj z Dept. of Computer and Information Science New Jersey Institute of Technology University Heights Newark, NJ 07102-1982, USA czumaj@cis.njit.edu Christian Scheideler Dept. of...

Artur Czumaj, Leszek Gasieniec

. We study the complexity of a classical combinatorial problem of computing the period of a string. We investigate both the average- and the worst-case complexity of the problem. We deliver almost...

Coloring Non-uniform Hypergraphs: A New Algorithmic Approach to the General Lovász Local Lemma (2000)

Balanced Allocations: The Heavily Loaded Case (2000)

The Lovasz Local Lemma is a sieve method to prove the existence of certain structures with certain prescribed properties. In most of its applications the Lovasz Local Lemma does not supply a...

Petra Berenbrink, Artur Czumaj, Angelika Steger, Berthold Vöcking

We investigate load balancing processes based on the multiplechoice paradigm. In these randomized processes m balls are inserted into n bins. In the classical single-choice variant each ball is...

An Algorithmic Approach to the General Lovász Local Lemma with Applications to Scheduling and Satisfiability Problems (2000)

Coloring Non-uniform Hypergraphs: A New Algorithmic Approach to the General Lovász Local Lemma (2000)

The Lovasz Local Lemma (LLL) is a powerful tool that is increasingly playing a valuable role in computer science. It has led to solutions for numerous problems in many different areas, reaching from...

Testing Convex Position (2000)

The Lovász Local Lemma (LLL) is a sieve method to prove the existence of certain structures with certain prescribed properties. In most of its applications the LLL does not supply a polynomial-time...

Artur Czumaj, Martin Ziegler, Heinz Nixdorf, Christian Sohler

In this paper we present a property tester for the convex position property of points sets.

An algorithmic approach to the general Lovász Local Lemma with applications to scheduling and satisfiability problems (2000)

An Algorithmic Approach to the General Lovász Local Lemma with Applications to Scheduling and Satisfiability Problems (2000)

The Lovász Local Lemma (LLL) is a powerful tool that is increasingly playing a valuable role in computer science. It has led to solutions for numerous problems in many different areas, reaching from...

Coloring Nonuniform Hypergraphs: A New Algorithmic Approach to the General (2000)

The Lovasz Local Lemma (LLL) is a powerful tool that is increasingly playing a valuable role in computer science. It has led to solutions for numerous problems in many different areas, reaching from...

Delayed path coupling and generating random permutations via distributed stochastic processes (1999)

ABSTRACT: The Lovász local lemma is a sieve method to prove the existence of certain structures with certain prescribed properties. In most of its applications the Lovász local lemma does not...

Artur Czumaj, Przemka Kanarek

We analyze various stochastic processes for generating permutations almost uniformly at random in distributed and parallel systems. All our protocols are simple, elegant and are based on performing...

Delayed Path Coupling and Generating Random Permutations via Distributed Stochastic Processes (1999)

Artur Czumaj, Przemka Kanarek, Miroslaw Kutylowski, Krzysztof Lorys

We analyze various stochastic processes for generating permutations almost uniformly at random in distributed and parallel systems. All our protocols are simple, elegant and are based on performing...

Efficient Web Searching Using Temporal Factors (1999)

Artur Czumaj, Ian Finch, Leszek Gasieniec, Alan Gibbons, Paul Leng, Wojciech Rytter, ...

We study the issues involved in the design of algorithms for performing information gathering more eciently, by taking advantage of anticipated variations in access times in dierent regions at...

Algorithms for the Parallel Alternating Direction Access Machine (1999)

Bogdan S. Chlebus, Artur Czumaj, Leszek Gasieniec, Miroslaw 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...

On Approximability of the Minimum-Cost k-Connected Spanning Subgraph Problem (1999)

Efficient Web Searching Using Temporal Factors (1999)

We present the first truly polynomial-time approximation scheme (PTAS) for the minimum-cost k-vertex- (or, k- edge-) connected spanning subgraph problem for complete Euclidean graphs in R d :...

Artur Czumaj, Ian Finch, Leszek Gasieniec, Alan Gibbons, Paul Leng, Wojciech Rytter, ...

Web traversal robots are used by search engines and in other applications to gather information periodically from large numbers of documents distributed throughout the Web. In this paper we study the...

Fast Generation of Random Permutations via Networks Simulation (1998)

Artur Czumaj, Przemyslawa Kanarek, Miroslaw Kutylowski, Krzysztof Lorys

. We consider the classical problem of generating random permutations with the uniform distribution. That is, we require that for an arbitrary permutation ß of n elements, with probability 1=n! the...

A Polynomial Time Approximation Scheme for Euclidean Minimum Cost k-Connectivity (1998)

Fast Generation of Random Permutations via Networks Simulation (1998)

. We present polynomial-time approximation schemes for the problem of finding a minimum-cost k-connected Euclidean graph on a finite point set in R d : The cost of an edge in such a graph is equal to...

Artur Czumaj Przemys, Artur Czumaj

We consider the problem of generating random permutations with the uniform distribution. That is, we require that for an arbitrary permutation of n elements, with probability 1=n! the machine halts...

Recovery Time of Dynamic Allocation Processes (1998)

Preliminary Version Extended, Artur Czumaj

) Artur Czumaj Heinz Nixdorf Institute and Department of Mathematics & Computer Science University of Paderborn D-33095 Paderborn, Germany (artur@uni-paderborn.de) May 1, 1998 Abstract Many...

Time and Cost Trade-Offs in Gossiping (1998)

Artur Czumaj, Andrzej Pelc

Each of n processors has a value which should be transmitted to all other processors. This fundamental communication task is called gossiping. In a unit of time every processor can communicate with...

Fast Generation of Random Permutations via Networks Simulation (1998)

Recovery Time of Dynamic Allocation Processes (1998)

. We consider the classical problem of generating random permutations with the uniform distribution. That is, we require that for an arbitrary permutation ß of n elements, with probability 1=n! the...

Time and Cost Trade-Offs in Gossiping (1998)

Many distributed protocols arising in applications in online load balancing and dynamic resource allocation can be modeled by dynamic allocation processes related to the "balls into bin"...

Artur Czumaj, Leszek Gasieniec, Andrzej Pelc

Each of n processors has a value which should be transmitted to all other processors. This fundamental communication task is called gossiping. In a unit of time every processor can communicate with...

Fast Generation of Random Permutations via Networks Simulation (1998)

Artur Czumaj, Przemyslawa Kanarek, Miroslaw Kutylowski, Krzysztof Lorys

We consider the problem of generating random permutations with the uniform distribution. That is, we require that for an arbitrary permutation ß of n elements, with probability 1=n! the machine...

Parallel Alternating-Direction Access Machine (1997)

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

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

Bounded Degree Spanning Trees (1997)

Work done at the University of Paderborn We consider randomized simulations of shared memory on a distributed memory machine (DMM) where the n processors and the n memory modules of the DMM are...

Artur Czumaj, Willy-b. Strothmann

. Given a connected graph G, let a \Delta T -spanning tree of G be a spanning tree of G of maximum degree bounded by \Delta T . It is well known that for each \Delta T 2 the problem of deciding...

Routing on the PADAM: Degrees of Optimality (1997)

Bogdan S. Chlebus, Artur Czumaj, Jop F. Sibeyn

Routing problems are studied for the Parallel Alternating-Direction Access Machine. The goal is to investigate what level of optimality can be achieved depending on loads of packets per memory unit....

Routing on the PADAM: Degrees of Optimality (1997)

Bogdan Chlebus, Artur Czumaj, Jop F. Sibeyn

Routing problems are studied for the Parallel Alternating-Direction Access Machine. The goal is to investigate what level of optimality can be achieved depending on loads of packets per memory unit....

Routing on the PADAM: Degrees of Optimality (1997)

Bogdan Chlebus, Artur Czumaj, Jop F. Sibeyn

Routing problems are studied for the Parallel Alternating-Direction Access Machine. The goal is to investigate what level of optimality can be achieved depending on loads of packets per memory unit....

Bounded Degree Spanning Trees (1997)

Artur Czumaj, Willy-b. Strothmann

. Given a connected graph G, let a \Delta T -spanning tree of G be a spanning tree of G of maximum degree bounded by \Delta T . It is well known that for each \Delta T 2 the problem of deciding...

Bounded Degree Spanning Trees (Extended abstract) (1997)

Artur Czumaj, Willy-B. Strothmann

. Given a connected graph G, let a \Delta T -spanning tree of G be a spanning tree of G of maximum degree bounded by \Delta T . It is well known that for each \Delta T 2 the problem of deciding...

Parallel Alternating-Direction Access Machine (1996)

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

. 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...

Parallel Alternating-Direction Access Machine (1996)

Bogdan Chlebus, Artur Czumaj, Wojciech Pl

. 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...

Parallel Maximum Independent Set In Convex Bipartite Graphs (1996)

Artur Czumaj, Instytut Informatyki, Uniwersytet Warszawski, Teresa M. Przytycka

A bipartite graph G = (V; W;E) is called convex if the vertices in W can be ordered in such a way that the elements of W adjacent to any vertex v 2 V form an interval (i.e. a sequence consecutively...

Parallel Maximum Independent Set In Convex Bipartite Graphs (1996)

Artur Czumaj, Krzysztof Diks, Instytut Informatyki, Uniwersytet Warszawski, Teresa M. Przytyc

this paper we address the problem of finding in parallel a maximum independent set in a special class of graphs --- convex bipartite graphs.

Parallel algorithmic techniques : PRAM algorithms and PRAM simulations / (1995)

Czumaj, Artur.

Zugl.: Paderborn, Univ.-Gesamthochsch., Diss., 1995.

Parallel Algorithmic Techniques: PRAM Algorithms And PRAM Simulations (1995)

Artur Czumaj, Im Fachbereich Mathematik/informatik

PRAM , which is the Priority CRCW PRAM in which each processor can perform arbitrary complex local operations in a single step. Clearly the Abtract PRAM is stronger than the Priority CRCW PRAM, and...

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

Lower Bound for String Matching on PRAM (1995)

We consider randomized simulations of shared memory on a distributed memory machine (DMM) where the n processors and the n memory modules of the DMM are connected via a reconfigurable architecture....

Parallel and Sequential Approximations of Shortest Superstrings (1994)

Breslauer and Galil have shown that the string matching problem requires \Theta(d n p e + log log d1+p=ne 2p) rounds in the parallel comparison tree model with p comparisons in each round. In this...

Artur Czumaj, Wojciech Rytter

Abstract. Superstrings have many applications in data compression and genetics. However the decision version of the shortest superstring problem is N P�complete. In this paper we examine the...

Parallel and Sequential Approximation of Shortest Superstrings (1994)

Artur Czumaj, Leszek Gasieniec, Marek Piotrow, Wojciech Rytter

. Superstrings have many applications in data compression and genetics. However the decision version of the shortest superstring problem is NP-complete. In this paper we examine the complexity of...

Sequential and Parallel Approximation of Shortest Superstrings (1994)

Artur Czumaj, Leszek GÄsieniec, Marek PiotrÃ³w, Wojciech Rytter

Superstrings have many applications in data compression and genetics. However the decision version of the shortest superstring problem is NP-complete. In this paper we examine the complexity of...

Parallel Algorithm for the Matrix Chain Product and the Optimal Triangulation Problems (Extended Abstract) (1993)

Fast Practical Multi-Pattern Matching (1993)

This paper considers the problem of finding an optimal order of the multiplication chain of matrices and the problem of finding an optimal triangulation of a convex polygon. For both these problems...

Maxime Crochemore, Artur CZUMAJ, Leszek Gasieniec, Stefan Jarominek, Thierry Lecroq, Wojciech PLANDOWSKI, ...

The main result of the paper is the construction of a very fast multi-pattern matching algorithm, called in the paper DAWG-MATCH. The algorithm is of Boyer-Moore type. Previous algorithm of this type...

An Optimal Parallel Algorithm for Computing a Near-Optimal Order of Matrix Multiplications (1992)

Contention Resolution in Hashing Based Shared Memory Simulations

This paper considers the computation of matrix chain products of the form M1 \Theta M2 \Theta \Delta \Delta \Delta \Theta Mn\Gamma1 . The order in which the matrices are multiplied affects the number...

Contention Resolution in Hashing Based Shared Memory Simulations

. In this paper we study the problem of simulating shared memory on the Distributed Memory Machine (DMM). Our approach uses multiple copies of shared memory cells, distributed among the memory...