Ackermann, Marcel; Lammersen, Christiane; Märtens, Marcus; Raupach, Christoph; Sohler, Christian; Swierkot, Kamil
:
StreamKM++: A Clustering Algorithm for Data Streams.
Accepted at: Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX), 2010.
Ackermann, Marcel; Blömer, Johannes; Sohler,
Christian:
Clustering for Metric and Non-Metric Distance Measures.
Accepted at: ACM Transactions on Algorithms (Special issue SODA'08), 2009.
Czumaj, Artur; Sohler,
Christian:
Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time.
In: SIAM Journal on Computing 39(3), S.904-922, 2009.
Batu, Tugkan; Berenbrink, Petra; Sohler,
Christian:
A sublinear-time approximation scheme for bin packing.
To appear in: Theoretical Computer Science, 2009.
Lammersen, Christiane; Sidiropulos, Anastasios; Sohler,
Christian:
Streaming Embeddings with Slack.
In: Proceedings of the 11th Algorithms and Data Structures Symposium, S.483-494, 2009.
Czumaj, Artur; Sohler,
Christian:
Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs.
In: SIAM Journal on Computing 38(6): 2499-2510 (2009)
Ganguly, Sumit; Sohler,
Christian:
d-dimensional Knapsack in the Streaming Model.
In: Proceedings of the 17th European Symposium on Algorithms (ESA), 2009.
Czumaj, Artur; Sohler,
Christian:
Small Space Representations for Metric Min-sum k-Clustering and Their Applications.
To appear in: Theory of Computing Systems (Special issue STACS'07), 2009.
2008:
Lammersen, Christiane; Sohler,
Christian: Facility Location
in Dynamic Geometric Data Streams. In: Proceedings of the 16th European Symposium on Algorithms (ESA), S. 660-671, 2008.
Ackermann, Marcel; Blömer, Johannes; Sohler,
Christian:
Clustering for metric and non-metric distance measures.
In: Proceedings of the 18th Symposium on Discrete Algorithms (SODA), S. 799-808, 2008.
Czumaj, Artur; Sohler, Christian
:
Testing Euclidean minimum spanning trees in the plane.
In: ACM Transactions on Algorithms 4(3): (2008)
Frahling, Gereon; Indyk, Piotr; Sohler, Christian
:
Sampling in Dynamic Data Streams and Applications.
In: Int. J. Comput. Geometry Appl. 18(1/2): 3-28 (2008)
Frahling, Gereon; Sohler, Christian
:
A Fast k-Means Implementation Using Coresets.
In: Int. J. Comput. Geometry Appl. 18(6): 605-625 (2008).
2007:
Lammersen, Christiane; Sohler,
Christian: StrSort
Algorithms for Geometric Problems. In: Proceedings of the 23rd European
Workshop on Computational Geometry (EWCG), S. 69-72, Jan. 2007
Czumaj, Artur; Sohler,
Christian:
Sublinear-time approximation algorithms for clustering via random sampling.
Random Structures & Algorithms, 30(1-2): S. 226 -- 256, Jan.
2007
Czumaj,
Artur; Sohler,
Christian:
On Testable Properties in Bounded Degree Graphs. In: Proceedings of the
17th ACM-SIAM Symposium on Discrete Algorithms (SODA'07), S. 494-501, Jan.
2007
Czumaj, Artur; Sohler, Christian: Small Space Representations for Metric Min-Sum
k-Clustering and their Applications. In: Proceedings of the 24th
International Symposium on Theoretical Aspects of Computer Science (STACS'07),
S. 536-548, Jan. 2007
Feldman, Dan; Monemizahdeh, Morteza; Sohler, Christian: A PTAS for k-means clustering based on weak
coresets. In: Proceedings of the 23rd annual symposium on computational
geometry (SoCG'07), S. 11-18, Jan. 2007
Czumaj, Artur; Frahling,
Gereon; Sohler,
Christian: Efficient
kinetic data structures for MaxCut. In: Proceedings of the 19th Canadian
Conference on Computational Geometry (CCCG), S. 157-160, Jan. 2007
Buriol, Luciana; Frahling, Gereon; Leonardi, Stefano; Sohler,
Christian: Estimating
Clustering Indexes in Data Streams. In: Proceedings of the 15th European
Symposium on Algorithms (ESA), S. 816-632, Jan. 2007
Czumaj, Artur Sohler,
Christian: Testing
Expansion in Bounded-Degree Graphs. In: Proceedings of the 48th Annual
IEEE Symposium on Foundations of Computer Science (FOCS), S. 570 - 578, Jan.
2007
2006:
Frahling, Gereon; Sohler,
Christian: A Fast
k-Means Implementation Using Coresets. In: ACM Symposium on Computational
Geometry, S. 135-143 2006
Buriol, Luciana; Frahling, Gereon; Leonardi, Stefano; Marchetti-Spaccamela, Alberto; Sohler, Christian: Computing Clustering Coefficients in Data Streams. In:
Proceedings of the European Conference on Complex Systems (ECCS'06), Jan.
2006
Gehweiler, Joachim; Lammersen,
Christiane; Sohler,
Christian: A Distributed
O(1)-Approximation Algorithm for the Uniform Facility Location Problem. In:
Proceeedings of 18th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA), S. 237-243, Jan. 2006
Buriol, Luciana; Frahling, Gereon; Leonardi, Stefano; Marchetti-Spaccamela, Alberto; Sohler, Christian: Counting Triangles in Data Streams. In: Proceedings of
the 25th ACM Symposium on Principles of Database Systems (PODS), Jan. 2006
(Details)
2005:
Frahling, Gereon; Indyk, Piotr; Sohler, Christian: Sampling in Dynamic Data Streams and Applications. In:
Proceedings of the 21st Annual ACM Symposium on Computational Geometry (SoCG),
S. 142-149 2005
Czumaj, Artur; Sohler,
Christian: Abstract
Combinatorial Programs and Efficient Property Testers. SIAM Journal on
Computing, 34(3): S. 580-615 2005
Frahling, Gereon; Sohler,
Christian: Coresets in
Dynamic Geometric Data Streams. In: Proceedings of the 37th ACM Symposium on
Theory of Computing (STOC), S. 209-217 2005
Badoiu, M.; Czumaj, Artur;
Indyk, Piotr; Sohler, Christian: Facility Location in Sublinear Time.. In:
Proc. of the 32nd International Colloquium on Automata, Languages and
Programming (ICALP), S. 866-877 2005
Czumaj, Artur; Ergun, Funda; Fortnow, Lance; Magen,
Avner; Newman, Ilan; Rubinfeld, Ronitt; Sohler,
Christian: Approximating
the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time. SIAM Journal on
Computing, 35(1): S. 91-109, Jan. 2005
Bienkowski, Marcin; Damerow,
Valentina; Meyer auf der Heide,
Friedhelm; Sohler,
Christian: Average Case
Complexity of Voronoi Diagrams of n Sites from the Unit Cube. In: Proceedings
of the 21st European Workshop on Computational Geometry (EWCG'05), S. 167 -
170, , Jan. 2005
2004:
Czumaj, Artur; Sohler,
Christian: Estimating
the Weight of Metric Minimum Spanning Trees in Sublinear Time. In: Proc. 36th
ACM Symposium on Theory of Computing (STOC) 2004
Czumaj, Artur; Sohler,
Christian:
Sublinear-Time Approximation for Clustering via Random Sampling. In: Automata,
Languages and Programming (ICALP), LNCS 3142, Nr.1, S. 396-407
2004
Krokowski, Jens; R/auml;cke,
Harald; Sohler, Christian; Westermann, Matthias: Reducing State Changes with a Pipeline
Buffer. In: Proceedings of the 9th International Fall Workshop Vision,
Modeling, and Visualization 2004
Damerow, Valentina; Sohler,
Christian: Extreme
Points under Random Noise. In: Proceedings of the 12th European Symposium on
Algorithms (ESA'04), S. 264 - 274, 2004
Damerow, Valentina; Sohler,
Christian: Smoothed
Number of Extreme Points under Uniform Noise. In: Proceedings of the 20th
European Workshop on Computational Geometry (EWCG'04), S. 93 - 96,
2004
Bansal, Vikas; Meyer auf der Heide,
Friedhelm; Sohler,
Christian: Labeling
Smart Dust. In: 12th Annual European Symposium on Algorithms (ESA 2004), Jun.
2004
2003:
Adler, Micah; Räcke,
Harald; Sivadasan, Naveen; Sohler,
Christian; Vöcking,
Berthold: Randomized
Pursuit-Evasion in Graphs. Combinatorics, Probability & Computing, 12(3):
S. 225-244 2003
Sohler,
Christian: Property Testing and
Geometry. Dissertation, Universität Paderborn, Heinz Nixdorf Institut,
Theoretische Informatik, HNI-Verlagsschriftenreihe, Paderborn, Band 119
2003
Czumaj, Artur; Ergun, Funda; Fortnow, Lance; Magen,
Avner; Newman, Ilan; Rubinfeld, Ronitt; Sohler,
Christian: Sublinear
Approximation of Euclidean Minimum Spanning Tree. In: Proceedings of the 14th
ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), S. 813-822
2003
Damerow, Valentina; Meyer auf
der Heide, Friedhelm; Räcke,
Harald; Scheideler,
Christian; Sohler,
Christian: Smoothed
Motion Complexity. In: Proceedings of the 11th Annual European Symposium on
Algorithms (ESA'03), S. 161 - 171, 2003
2002:
Adler, Micah; Räcke,
Harald; Sivadasan, Naveen; Sohler,
Christian; Vöcking,
Berthold: Randomized
Pursuit-Evasion in Graphs. In: Proceedings of the 29th International
Colloquium on Automata, Languages and Programming
2002
Czumaj, Artur; Sohler,
Christian: Abstract
Combinatorial Programs and Efficient Property Testers. Proceedings of the 43th
Symposium on Foundations of Computer Science (FOCS): S. 83-92 2002
2001:
Czumaj, Artur; Sohler,
Christian: Soft Kinetic
Data Structures. In: Proceedings of the 12th ACM-SIAM Symposium on Discrete
Algorithms, S. 865-872, 1. Mai 2001
Czumaj, Artur; Sohler,
Christian: Property
Testing with Geometric Queries.. Proceedings of the 9th Annual European
Symposium on Algorithms (ESA`01): S. 266-277 2001
Czumaj, Artur; Sohler,
Christian: Testing
Hypergraph Coloring. Proceedings of the 28th International Colloquium on
Automata, Languages and Programming (ICALP): S. 493-505
2001
2000:
Czumaj, Artur; Sohler,
Christian; Ziegler,
Martin: Property Testing
in Computational Geometry. In: Paterson, Mike (Hrsg.) Proceedings of the 8th
Annual European Symposium on Algorithms (ESA'00), Lecture Notes in Computer
Science, Band 1879, S. 155-166 2000
Sohler, Christian; Ziegler,
Martin: Computing Cut
Numbers. In: Proceedings of the 12th Canadian Conference on Computational
Geometry (CCCG'00), S. 73-79 2000
1999:
Sohler,
Christian: Generating Random
Star-Shaped Polygons. In: Proceedings of the 11th Canadian Conference on
Computational Geometry ('CCCG'99), S. 174-177 1999
Sohler,
Christian: Fast Reconstruction
of Delaunay Triangulations. In: Proceedings of the 11th Canadian Conference on
Computational Geometry ( CCCG'99), S. 136-141 1999
1997:
Denny, Markus;
Sohler, Christian: Encoding a Triangulation as a
Permutation of its Point Set. In: Proceedings of the 9th Canadian Conference
on Computational Geometry, S. 39-43 1997