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...
Smoothed Motion Complexity Valentina Damerow (2009)
Christian Scheideler, Christian Sohler
Abstract. We propose a new complexity measure for moving objects, the smoothedmotion complexity. Many applications, e.g., GPS, are based on algorithms dealing with moving objects, but usually data...
Artur Czumaj, Christian Sohler, Heinz Nixdorf
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...
Dissertation Algorithms for Dynamic Geometric Data Streams (2008)
Dipl. –math Gereon Frahling, Reviewers Jun, Prof Dr, Christian Sohler, Prof Dr, ...
First of all I would like to thank my advisor Christian Sohler for his great support. It was not always easy to keep pace with his great ability to find interesting problems and develop new ideas to...
Property Testing in Computational Geometry (Extended Abstract) (2008)
Artur Czumaj, Christian Sohler, Martin Ziegler
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)
Artur Czumaj, Christian Sohler
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 Geometric Properties (2008)
Artur Czumaj, Christian Sohler, Martin Ziegler
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...
Testing hereditary properties of non-expanding bounded-degree graphs (2008)
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 Reducing State Changes with a Pipeline Buffer ∗ (2008)
Jens Krokowski, Harald Räcke, Christian Sohler, Matthias Westermann
A limiting factor in the performance of a rendering system is the number of state changes, i.e., changes of the attributes material, texture, shader program, etc., in the stream of rendered...
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...
Computing Clustering Coefficients in Data Streams ∗ (2008)
Lucian Salete, Buriol Gereon, Frahling Stefano Leonardi, Alberto Marchetti-spaccamela, Christian Sohler
We present random sampling algorithms that with probability at least 1 − δ compute a (1 ± ǫ)approximation of the clustering coefficient, the transitivity coefficient, and of the number of...
Artur Czumaj, Christian Sohler
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...
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...
Artur Czumaj, Christian Sohler, Heinz Nixdorf
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...
Abstract Generating Random Star-Shaped Polygons (Extended Abstract) (2008)
In this paper we deal with two problems on star-shaped polygons. At rst, we present a Las-Vegas algorithm that uniformly at random creates a star-shaped polygon whose vertices are given by apoint set...
Luciana S. Buriol, Stefano Leonardi, Gereon Frahling, Christian Sohler
We present random sampling algorithms that with probability at least 1 − δ compute a (1 ± ɛ)approximation of the clustering coefficient and of the number of bipartite clique subgraphs of a graph...
ABSTRACT Coresets in Dynamic Geometric Data Streams (2008)
Gereon Frahling, Christian Sohler
A dynamic geometric data stream consists of a sequence of m insert/delete operations of points from the discrete space {1,..., ∆} d [26]. We develop streaming (1 + ɛ)-approximation algorithms for...
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...
Artur Czumaj, Christian Sohler, Heinz Nixdorf
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...
Estimating the Weight of Metric Minimum Spanning (2008)
Artur Czumaj, Christian Sohler, Heinz Nixdorf
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...
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,...
Property Testing in Computational Geometry (Extended Abstract) (2007)
Artur Czumaj, Christian Sohler, Martin Ziegler
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...
Generating Random Star-Shaped Polygons (Extended Abstract) (2007)
) Christian Sohler Heinz Nixdorf Institute and Dept. of Mathematics and Computer Science, University of Paderborn, D-33095 Paderborn, Germany e-mail: csohler@uni-paderborn.de Abstract In this paper...
Harald Rcke, Christian Sohler, Matthias Westermann
Abstract. We introduce the online scheduling problem for sorting buffers. A service station and a sorting buffer are given. An input sequence of items which are only characterized by a specific...
Micah Adler, Harald Racke, Naveen Sivadasan, Christian Sohler, Berthold Vocking
Abstract. We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let G be any connected, undirected graph with n nodes. The game is played...
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
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time (2007)
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...
Valentina Damerow, Harald Racke, Christian Scheideler, Christian Sohler
Abstract. We propose a new complexity measure for movement of objects, the smoothed motion complexity. Many applications are based on algorithms dealing with moving objects, but usually data of...
Testing Euclidean minimum spanning trees in the plane (2007)
Artur Czumaj, Christian Sohler, Martin Ziegler
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....
Testing Euclidean Minimum Spanning Trees in the Plane + (2007)
Artur Czumaj, Christian Sohler, Martin Ziegler
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...
Sublinear-time algorithms (2006)
Artur Czumaj, Christian Sohler
In this paper we survey recent advances in the area of sublinear-time algorithms. 1
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...
Marcin Bienkowski, Valentina Damerow, Christian Sohler
Average case complexity of Voronoi diagrams of n sites from the unit
Fast reconstruction of delaunay triangulations (2005)
We present a new O(n) algorithm to compute good orders for the point set of a Delaunay triangulation of n points in the plane. Such a good order makes reconstruction in O(n) time with a simple...
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...
Sublinear-Time Approximation for Clustering via (2004)
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...
Sublinear-time approximation for clustering via random sampling (2004)
Artur Czumaj, Christian Sohler
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...
Randomized Pursuit-Evasion in Graphs (2003)
Adler,Micah, Räcke,Harald, Sivadasan,Naveen, Sohler,Christian, Vöcking,Berthold
Randomized Pursuit-Evasion in Graphs (2003)
Adler, Micah, Räcke, Harald, Sivadasan, Naveen, Sohler, Christian, Vöcking, Berthold
Smoothed motion complexity (2003)
Valentina Damerow, Harald Räcke, Christian Scheideler, Christian Sohler
Abstract. We propose a new complexity measure for movement of objects, the smoothed motion complexity. Many applications are based on algorithms dealing with moving objects, but usually data of...
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...
Artur Czumaj, Christian Sohler, Heinz Nixdorf
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...
Randomized Pursuit-Evasion in Graphs (2002)
Adler,Micah, Räcke,Harald, Sivadasan,Naveen, Sohler,Christian, Vöcking,Berthold
{ We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a {\em hunter} and a {\em rabbit}. Let $G$ be any connected, undirected graph with $n$ nodes. The game is...
Randomized Pursuit-Evasion in Graphs (2002)
Adler, Micah, Räcke, Harald, Sivadasan, Naveen, Sohler, Christian, Vöcking, Berthold, Widmayer, Peter, ...
{ We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a {\em hunter} and a {\em rabbit}. Let $G$ be any connected, undirected graph with $n$ nodes. The game is...
Randomized pursuit-evasion in graphs (2002)
Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking
We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let G be any connected, undirected graph with n nodes. The game is played in rounds...
Online scheduling for sorting buffers (2002)
Harald Räcke, Christian Sohler, Matthias Westermann
Abstract. We introduce the online scheduling problem for sorting buffers. A service station and a sorting buffer are given. An input sequence of items which are only characterized by a specific...
Randomized Pursuit-Evasion in Graphs (2002)
Micah Adler Harald, Harald Racke, Naveen Sivadasan, Christian Sohler, Berthold Vocking
We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let G be any connected, undirected graph with n nodes. The game is played in rounds...
Randomized pursuit-evasion in graphs (2002)
Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking
Abstract. We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let G be any connected, undirected graph with n nodes. The game is played...
Randomized pursuit-evasion in graphs (2002)
Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking
ns,voecking� Abstract. We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let � be any connected, undirected graph with � nodes....
Randomized pursuit-evasion in graphs (2002)
Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking
Abstract. We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let G be any connected, undirected graph with n nodes. The game is played...
Property testing and geometry / (2002)
Paderborn, University, Diss., 2002 (Nicht für den Austausch).
Property testing and geometry [Elektronische Ressource] / (2002)
Paderborn, University, Diss., 2002.
Randomized pursuit-evasion in graphs (2002)
Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking
We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let be any connected, undirected graph with nodes. The game is played in rounds and...
Testing hypergraph coloring (2001)
Artur Czumaj, Christian Sohler
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...
Property testing with geometric queries (2001)
Artur Czumaj, Christian Sohler
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...
Soft Kinetic Data Structures (2001)
Artur Czumaj, Christian Sohler
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...
Testing Hypergraph Coloring (2001)
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...
Testing Convex Position (2000)
Artur Czumaj, Martin Ziegler, Heinz Nixdorf, Christian Sohler
In this paper we present a property tester for the convex position property of points sets.
Fast Reconstruction of Delaunay Triangulations (1999)
We present a new O(n) algorithm to compute good orders for the point set of a Delaunay triangulation of n points in the plane. Such a good order makes reconstruction in O(n) time with a simple...