Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
|
Institut für Theoretische Informatik Departement Informatik ETH Zürich CH-8092 Zürich |
phone +41-44-632 73 92 fax +41-44-632 10 63 |
| Quick Links: | Personnel, Guests, Grants, Publications, Lectures, Courses, Workshops, Dissertations, Master Theses, Semester Theses, Miscellaneous |
Fukuda, Komei
(1/3 appointment)
Welzl, Emo
Berke, Robert
Csorba, Péter (until Aug 31)
Fischer, Kaspar
Gärtner, Bernd, Dr.
Giesen, Joachim, Dr.
Hoffmann, Michael, Dr.
Lakshminarayanan, Shankar Ram (since Sep 1)
Mitsche, Dieter
Okamoto, Yoshio (until Mar 31)
Razen, Andreas (since Apr 1)
Rüst, Leo
Scheder, Dominik (since Oct 17)
Schuberth, Eva
Stojakovic, Milos (until Sep 30)
Szabó, Tibor, Dr.
Wessendorp, Frans (until Sep 30)
Zumstein, Philipp (since Mar 21)
Penny
Haxell, University of Waterloo, Canada (Jan 11 - Feb 17)
Ramsey Numbers for Hypergraph Cycles (Mittagsseminar,
Feb 3, 2005)
Erik D. Demaine,
Massachusetts Institute of Technology (MIT),
Cambridge, USA (Jan 19 - 22)
Origami, Polyhedra, and Linkages: Folding with Algorithms
(Mittagsseminar,
Jan 21, 2005)
Nir Halman, Technion, Haifa, Israel (Jan 24 - 26)
On the Power of Discrete Helly Theorems and Lexicographic Helly Theorems
(Mittagsseminar,
Jan 24, 2005)
Kevin Buchin, Berlin Free University, Germany (Jan 31 - May 13)
Incremental Construction along Space-Filling Curves
(Mittagsseminar,
Apr 7, 2005)
Maike Buchin, Berlin Free University, Germany (Jan 31 - May 13)
Semi-Computability of the Fréchet Distance between Surfaces
(Mittagsseminar,
Apr 12, 2005)
Dan Hefetz,
Tel Aviv Univiversity, Tel Aviv, Israel,
(Apr 17-22)
Avoider-Enforcer Games,
(Mittagsseminar,
Apr 19, 2005)
Uli Wagner,
Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Israel (Apr 16-24)
k-Sets and Topological Invariants of Plane Curves
(Mittagsseminar,
Apr 22, 2005)
Uwe Schöning, Ulm University, Ulm, Germany (Apr 21)
Algorithmics in Exponential Time,
(Seminar SAT,
Apr 21, 2005)
Quest for the Fastest SAT Algorithm,
(Mittagsseminar,
Apr 21, 2005)
Gyula Károlyi,
Eötvös University, Budapest, Hungary (May)
Structure Theorems for Set Addition: the Power of the Combinatorial Nullstellensatz
(Workshop
on Geometric Combinatorics and Optimization,
May 24, 2005)
Set Addition in Noncommutative Groups,
(Mittagsseminar,
May 26, 2005)
Shakhar Smorodinsky, Courant Institute for Mathematical Sciences,
New York University, USA (May 5-8)
On the Chromatic Number of Some Geometric Hypergraphs,
(Mittagsseminar,
May 6, 2005)
János Barát,
TU Lyngby, Denmark (May 8-13)
The Slope Parameter of Graphs
(Mittagsseminar,
May 10, 2005)
Takeaki Uno,
National Institute of Informatics, Tokyo, Japan (since May 9)
Tree Enumeration Algorithms (Mittagsseminar, Jul 26, 2005)
Enumerating Dense Subgraphs (Mittagsseminar, Dec 1, 2005)
Michael Joswig, Technische Universität Darmstadt, Germany
(May 9)
Polytope Propagation
(Optimisation Seminar,
May 9, 2005)
Jiří Matoušek, Charles University, Prague, Czech Republic (May 15 - July 8)
Voronoi Diagrams with Neutral Zones
(Workshop
on Geometric Combinatorics and Optimization,
May 24, 2005)
New Badly Embeddable Spaces (presenting work of Subhash Khot and Assaf Naor)
(Mittagsseminar,
Jun 23, 2005)
András Recski,
Budapest University of Technology and Economics
(May 23-24)
Some Applications of Combinatorial Optimization in Statics (Mittagsseminar,
May 24, 2005)
Takashi Horiyama, School of Informatics and Mathematical Science, Kyoto University, Japan (Jun 9-10)
Edgar Ramos, University of Illinois at Urbana-Champaign, USA
(Jun 11-18)
Manifold Reconstruction from Point Samples
(Mittagsseminar,
Jun 15, 2005)
Ron Aharoni,
Technion - Israel Institute of Technology,
Haifa, Israel
(Jun 12-19)
The Erdös-Menger Conjecture
(Mittagsseminar,
Jun 14, 2005)
Pankaj K. Agarwal,
Duke University, Durham, USA
(Jun 13-16)
Optimal Coresets for Approximating the Extent of Shallow Levels
(Mittagsseminar,
Jun 15, 2005)
Csaba D. Tóth,
Massachusetts Institute of Technology, Cambridge, USA
(Jun 18-22)
A Vertex-Face Assignment for Plane Graphs
(Mittagsseminar,
Jun 21, 2005)
Avi Wigderson, Institute for Advanced Study, Princeton, USA
(Jun 27)
Zigzag Products, Expander Constructions, Connections and Applications
(Colloquium
Department of Computer Science, Jun 27, 2005)
Bettina Speckmann, TU Eindhoven, The Netherlands
(Jul 2-6)
On Rectangular Cartograms
(Mittagsseminar,
Jul 6, 2005)
Yoshio Okamoto,
Toyohashi University of Technology, Japan
(Jul 3-6)
All-Pairs Shortest Paths with Real Weights in O(n^3 /log n) Time
(Mittagsseminar,
Jul 7, 2005)
Maike Buchin, Berlin Free University, Germany
(Jul 3-9)
Minimizing the Total Absolute Gaussian Curvature in a Terrain is Hard
(Mittagsseminar,
Jul 7, 2005)
Kevin Buchin, Berlin Free University, Germany
(Jul 3-9)
The Flow Complex: General Structure and Algorithm
(Mittagsseminar,
Jul 7, 2005)
Hans-Martin Will, Rosetta Inpharmatics Inc., Seattle, USA
(Jul 3-9)
Challenges and Opportunities in the Post-Genome Era - An Introduction to Functional Genomics and Proteomics
(Mittagsseminar,
Jul 19, 2005)
Masashi Kiyomi, National Institute of Informatics (NII), Japan (Jun 28 - Jul 28)
Efficient Algorithms for the Electric Power Transaction Problem
(Mittagsseminar,
Jul 21, 2005)
Berit Johannes (since Aug 1)
Earliest Start Time Scheduling in AND/OR-graphs - An Introduction (Mittagsseminar,
Oct 18, 2005)
Andreas S. Schulz, Massachusetts Institute of Technology, Cambridge, MA (since Aug 1)
Single-Machine Scheduling with Precedence Constraints (Optimization and Applications Seminar, Nov 14, 2005)
How many diamonds can be packed in a Chinese checkerboard? (Mittagsseminar, Dec 6, 2005)
Games in Networks, and the Price of Anarchy (Informatik Kolloquium, Dec 19, 2005)
Mutsunori Yagiura, Kyoto University, Japan (Aug 16-22)
Exact Algorithms for Two-Dimensional Strip Packing Problems
(Mittagsseminar, Aug 18, 2005)
Karl Lieberherr, Northeastern University, Boston (Aug 23)
Algorithmic Problems Related to the Tyranny of the Dominant Decomposition
(Mittagsseminar, Aug 23, 2005)
Michael Krivelevich, Tel Aviv University, Tel Aviv, Israel
(Sep 17-24)
Property Testing in Graphs of General Density
(Mittagsseminar,
Sep 21, 2005)
József Beck, Rutgers University, New Brunswick, USA
(Sep 22-25)
Every Finite Point Set in the Plane is a Weak Winner!
(Mittagsseminar,
Sep 22, 2005)
Ken Satoh, National Institute of Informatics, Japan (Oct 6-11)
Enumerating Minimally Revised Specifications using Dualization
(Mittagsseminar, Oct 11, 2005)
Mitsuo Motoki, Japan Advanced Institute for Science and Technology, Japan (Oct 7-8)
Test Instance Generation for MAX 2SAT
(Mittagsseminar, Oct 7, 2005)
Micha Sharir, Tel Aviv University, Tel Aviv, Israel (Oct 6-26)
On the ICP Algorithm (Mittagsseminar,
Oct 12, 2005)
Uli Wagner, Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Israel (Oct 23-28)
Ryuhei Uehara, Japan Advanced Institute of Science and Technology, Japan (Oct 24 - Nov 23)
Efficient Algorithms for the Longest Path Problem
(Mittagsseminar,
Oct 25, 2005)
Ulrike von Luxburg, Fraunhofer IPSI, Darmstadt, Germany
(Nov 3-4)
Convergence of Random Graph Laplacians
(Mittagsseminar,
Nov 3, 2005)
Volker Kaibel, Zuse-Institut Berlin, Germany
(Dec 5-7)
Breaking Symmetries by Orbitopes
(Optimisation
Seminar, Dec 5, 2005)
Rahul Savani, London School of Economics, London, UK
(Dec 12-16)
Hard-to-Solve Bimatrix Games (Mittagsseminar, Dec 13, 2005)
Bernhard von Stengel, London School of Economics, London, UK
(Dec 12-16)
Strategic Characterization of the Index of an Equilibrium (Mittagsseminar, Dec 15, 2005)
(Financed by the Swiss National Science Foundation.)
Proper coloring of graphs and the chromatic number (the smallest number of colors which allow a proper coloring) are among the most important concepts of graph theory.
Numerous problems of pure mathematics and theoretical computer science require the study of proper colorings and
even more real-life problems require the calculation or at least
an estimation of the chromatic number. Nevertheless, there is the discouraging
fact that the calculation of the chromatic number of a graph or the task of finding an optimal proper coloring are both
famous intractable problems, even fast approximation is probably not possible.
This is one of our motivations to study relaxations of proper coloring, because in some theoretical or practical situations
a small deviation from proper is still acceptable, while the problem
could become tractable.
Another reason for the introduction of relaxed colorings is that
in certain problems the use of the full strength of proper coloring is an ``overkill''. Often a weaker concept suffices and provides better overall results.
In the project we study a relaxation of proper coloring, which allows
the presence of some small level of conflicts in the color assignment.
Our approach relies heavily on the theory of transversals.
A set of vertices in a partitioned graph is called a transversal if
it contains exactly one vertex from each class. Transversals with
special properties surface in many different problems of combinatorics
and theoretical computer science, when an appropriate auxiliary graph is
constructed and a transversal of a certain kind is sought after. In particular independent transversals
saw numerous applications in the study of list chromatic number,
the satisfiability of boolean formulas, the linear arboricity of graphs and
relaxed colorings of graphs. The quest for transversal results also inspired a great
methodological advance in the field of combinatorics, as beautiful proofs
applying combinatorial topology appeared.
(Contact: T.
Szabó)
(European Project.)
Increasingly demanding applications of geometric computing, for example in
CAD/CAM, computer aided surgery, realistic virtual environments, robotics, and
molecular modeling in drug design and structural biology, require efficient
and robust methods for computing with complex shapes. This project aims at
advancing the state of the art in this field. Current technology can cope
well with curves in the plane and smooth surfaces in three-dimensional
space. We want to deal with a larger class of shapes, including piecewise
smooth and singular surfaces.
Topics that we address are shape approximation (including meshing and
simplification), shape learning (including reconstruction and feature
extraction), as well as robust modeling (including boolean operations). Our
work on these topics will be closely intertwined with basic research on shape
representations, certified geometric calculus and algorithms producing output
with guaranteed topology.
A distinctive feature is the design and implementation of novel algorithmic
solutions with certified topology and numerics as an alternative for
heuristics and ad hoc methods, and the development of an experimental geometry
kernel
for modeling and computing with complex shapes as a proof-of-concept
justifying our approach. The results of this project should be directly
useful to the application areas mentioned above. We intend to disseminate our
work by publication in the appropriate applied research forums, by organizing
multidisciplinary workshops aimed at exchange of knowledge and discussion of
our work. Moreover, we aim at transferring our new technology by producing
high quality software, demonstrating the feasibility of our techniques in
practice. Cooperation with our industrial partner includes the assessment,
trial, validation and packaging of the software developed in the project, thus
guaranteeing a smooth transfer of new technology to application areas.
At ETH, we focus on new geometric data structures and optimization-based
primitives to deal with shapes, and we provide according software
components, building on our experience with reconstruction
and optimization software for various tasks.
(Contact:
B. Gärtner,
J. Giesen)
(Financed by the Swiss National Science Foundation.)
Manifold learning is the problem
of computing a model of a k-dimensional manifold embedded non-linearly
in d-dimensional
Euclidean space only from a finite set of sample points. Typically k is
very small
compared to d. The importance of the problem can be stressed by its many
applications,
e.g. in speech recognition, weather forecasting and economic prediction.
Special cases of the manifold learning problem in low dimensions
received a lot of
attention in recent years. Most prominent is the surface reconstruction
problem where
a two-dimensional manifold embedded in three-dimensional space has to be
learned.
Some of the proposed algorithms for surface reconstruction come with the
guarantee
that the computed model is a manifold homeomorphic and geometrically
close to the
unknown manifold provided some sampling condition is fulfilled. Almost
all known
provable algorithms for surface reconstruction use the Delaunay
triangulation of the
sample points as basic data structure. Unfortunately the time to compute
the Delaunay
triangulation is prohibitive in higher dimensions.
In this project we plan to investigate provable methods for manifold
learning in
high dimensions. Starting point should be a sampling condition similar
to the
one used in the proofs for surface reconstruction. The most important
task in
extending theoretical guarantees known from surface reconstruction to
higher
dimensions is to replace the Delaunay triangulation with other proximity
data structures.
(Contact: J.
Giesen)
(Financed by the Swiss National Science Foundation.)
Linear programming, as well as several other geometric optimization problems
do have polynomial-time algorithms in the bit model,
i.e. when the input size is measured by the bit complexity of the
actual numbers in the data. It
is not known, however, whether there are strongly polynomial algorithms,
whose performance is quantified in terms of arithmetic operations on
input numbers, independently from their bit complexity.
The goal of the project is to find, study, and algorithmically
exploit combinatorial models for certain discrete geometric optimization
problems. Our main motivation is to enhance our understanding of
the combinatorics behind linear programming and related - mostly
geometric - optimization problems, improve on the performance
guarantees of existing algorithms, and possibly discover novel,
more efficient approaches.
Classical such models are matroids,
oriented matroids and submodular
functions.
Within the last ten years, the concept of LP-type problems has
become a recognized combinatorial model for linear programming and many
other important geometric optimization problems. For many
problems in the class, the currently best (or even optimal) combinatorial
algorithm is an algorithm for general LP-type problems.
In the last couple of years new exciting
combinatorial models for geometric optimization problems
have emerged, such as unique-sink orientations of cubes and
strong LP-type problems. Just like LP-type problems ten years
ago, these new combinatorial abstractions had immediate consequences;
they provide the only available algorithms
for certain linear complementarity problems with
nontrivial running time guarantees.
Within this new project, we plan to explore unique-sink orientations,
strong LP-type problems, their relations to each other and
to other known combinatorial models, as well
as algorithms for problems fitting into the respective models.
(Contact: B. Gärtner,
T. Szabó)
(Financed by the
Eidgenössische Materialprüfungs- und Forschungsanstalt, EMPA.)
The set of colors that can be represented or reproduced by some device
or process is called a gamut. In general different devices
have different gamuts. Hence, when processing images from some
input device to some output device one often faces the problem that
the gamut changes, often the size of the gamut of the output device is the
bottleneck in the transition and information gets lost. The challenge is
to define and compute good (tailored) gamut mappings.
The problem of defining and computing gamut mappings is amenable to
methods from low dimensional computational geometry, because in color
spaces like CIELAB a gamut is represented as a three-dimensional
polytope.
The purpose of this project is to develop fast and robust methods for
computing gamuts and gamut mappings.
(Contact: J.
Giesen, ETHZ, and K. Simon, EMPA)
(Financed by the Swiss National Science Foundation.)
Estimating product preferences of individuals by means
of questionnaires is daily practice in market research. Under the name of
conjoint analysis a whole family of methods has been developed
and used to estimate the preferences of individuals. Conjoint analysis
started in 1964 with the seminal paper by Luce and Tukey and was introduced
to the marketing literature by Green and Rao in 1971. Since then conjoint
analysis has received much attention from practitioners in market research
as well as from researchers in academia. Its importance can be stressed by
its many applications, e.g. in new product planning, product
improvement, pricing, advertising, distribution and market segmentation
and simulation.
In this project we study a variant of conjoint analysis which is called
choice based conjoint analysis (CBC). In CBC product preferences
of an individual are learned from a sequence of pairwise product comparisons.
In each comparison the respondent only has to state which out of the two
products she prefers. The comparisons are used to estimate parameters in
a utility function that is defined over the product space. We focus on two
questions. First, how many comparisons have to be performed by the respondent
at least in order to get optimal knowledge on the parameters. Second, we
want to find a strategy to present product pairs to the respondent such
that one gets optimal knowledge on the parameters by presenting only the
minimum number of product pairs necessary. That is, we want to determine
the intrinsic complexity of CBC. The first problem asks for a lower bound
on this complexity whereas the second problem asks for an upper bound.
(Contact: J.
Giesen)
(Financed by the Swiss National Science Foundation.) This project concerns research themes that interlink four domains in mathematics: combinatorics, algebra, geometry and optimization. We address fundamental questions and applications that rely crucially on this fusion. Our strong drive for this fusion of the established research domains comes from the observation that several fundamental problems spreading over these domains are closely interlinked: a solution to one of the problems often leads to a solution for another one in a different domain. More precisely, we propose to study the following four specific research themes (with its principal domain).
Each of the four themes has a long history of earlier investigations in its
principal domain. With these themes studied extensively for many years,
it is becoming increasing evident that these four themes are closely related
and inseparable.
In fact, there are underlying mathematical structures, convex polytopes, matroids and
polynomials common to all these themes.
Our belief is that it makes much more sense to investigate them
together. Our research team consists of active researchers, each with
at least two domains of competence and strong interests in
making this nontrivial fusion.
(Contact: E. Feichtner, ETHZ,
K. Fukuda, ETHZ and EPFL,
P. Parrilo, ETHZ, and
R. Thomas, University of Washington)
J. E. Goodman, J. Pach, E. Welzl (Eds.), Combinatorial and Computational Geometry, Mathematical Sciences Research Institute Publications, Cambridge University Press (2005).
N. Alon, M. Krivelevich, J. Spencer, T. Szabó, Discrepancy games, Electronic Journal of Combinatorics 12 (2005) R51.
I. Bárány, K. Fukuda, A case when the union of polytopes is convex, Linear Algebra and its Applications 397 (2005) 381 - 388.
P. Csorba, On the biased n-in-a-row game, Discrete Mathematics, 305:1-3 (2005) 100-111.
S. Felsner, B. Gärtner, F. Tschirschnitz, Grid orientations, (d,d+2)-polytopes, and arrangements of pseudolines, Discrete & Computational Geometry 34 (2005) 411-437.
A. Frieze, M. Krivelevich, O. Pikhurko, T. Szabó, The game of JumbleG, Combinatorics, Probability and Computing 14 (2005) 783-793.
M. Hoffmann, A simple linear algorithm for rectilinear 3-centers, Computational Geometry - Theory and Applications 31:3 (2005) 150-165.
K. Kashiwabara, M. Nakamura, Y. Okamoto, The affine representation theorem for abstract convex geometries, Computational Geometry - Theory and Applications 30 (2005) 129-144.
B. Speckmann, Cs. D. Tóth, Allocating vertex pi-guards in simple polygons via pseudo-triangulations, Discrete & Computational Geometry 33 (2005) 345-364.
M. Stojakovic, T. Szabó, Positional games on random graphs, Random Structures & Algorithms 26 (2005) 204-223.
B. Sudakov, T. Szabó, V. Vu, A generalization of Turán's Theorem, Journal of Graph Theory 49:3 (2005) 187-195.
T. Szabó, V. Vu, Exact k-wise intersection theorems, Graphs and Combinatorics 21:2 (2005) 247-261.
U. Adamy, Th. Erlebach, D. Mitsche, I. Schurr, B. Speckmann, E. Welzl, Off-line admission control for advance reservations in star networks, Proc. 2nd Workshop on Approximation and Online Algorithms (WAOA`04), Lecture Notes in Computer Science 3351 (2005) 211-224.
B. Aronov, S. Smorodinsky, On geometric permutations induced by lines transversal through a fixed point, Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2005) 251-256.
Z. Beerliova, F. Eberhard, Th. Erlebach, A. Hall, M. Hoffmann, M. Mihalak, L. Shankar Ram, Network discovery and verification, Proc. Graph Theoretic Concepts in Computer Science (WG), Lecture Notes in Computer Science 3787 (2005) 127-138.
R. Berke, T. Szabó, Relaxed coloring of cubic graphs, European Conference on Combinatorics, Graph Theory, and Applications (EUROCOMB) (2005) 341-344.
M. Bläser, L. Shankar Ram, An improved approximation for TSP with distances one and two, Proc. 15th International Symposium on Fundamentals of Computation Theory (FCT), Lecture Notes in Computer Science 3623 (2005) 504-515.
M. Bläser, L. Shankar Ram, Approximate fair cost allocation in metric TSP games, Proc. 3rd Workshop on Approximation and Online Algorithms (WAOA), Lecture Notes in Computer Science 3879 (2005) 82-95.
M. Bläser, L. Shankar Ram, M. Sviridenko, Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems, Proc. Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science 3608 (2005) 350-359.
F. Cazals, J. Giesen, M. Pauly, A. Zomorodian, Conformal alpha shapes, Proc. 2nd Symposium on Point Based Graphics (SPBG) (2005) 55-61.
T.K. Dey, J. Giesen, S. Goswami, Delaunay triangulation approximates anchor hull, Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2005) 1028-1037.
T.K. Dey, J. Giesen, E. Ramos, B. Sadri, Critical points of the distance to an epsilon-sampling on a surface and flow complex reconstruction, Proc. 21st Annual ACM Symposium on Computational Geometry (SOCG) (2005) 218-227.
A. Fiat, M. Levy, J. Matoušek, E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, U. Wagner, E. Welzl, Online conflict-free coloring for intervals, Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2005) 545-554.
B. Gärtner, W. D. Morris Jr., L. Rüst, Unique sink orientations of grids, Proc. 11th Conference on Integer Programming and Combinatorial Optimization (IPCO), Lecture Notes in Computer Science 3509 (2005) 210-224.
B. Gärtner, L. Rüst, Simple stochastic games and P-matrix generalized linear complementarity problems, Proc. 15th International Symposium on Fundamentals of Computation Theory (FCT), Lecture Notes in Computer Science 3623 (2005) 209-220.
J. Giesen, D. Mitsche, Boosting spectral partitioning by sampling and iteration, Proc. 16th Annual International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science 3827 (2005) 473-482.
J. Giesen, D. Mitsche, Bounding the misclassification error in spectral partitioning in the planted partition model, Proc. 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Lecture Notes in Computer Science 3787 (2005) 409-420.
J. Giesen, D. Mitsche, Reconstructing many partitions using spectral techniques , Proc. 15th International Symposium on Fundamentals of Computation Theory (FCT), Lecture Notes in Computer Science 3623 (2005) 433-444.
J. Giesen, E. Schuberth, K. Simon, P. Zolliker, Toward interactive image-dependent gamut mapping: Fast and accurate gamut boundary determination, Proc. IS&T/SPIE Symposium on Electronic Imaging (2005) 201-210.
M. Hoffmann, Cs. D. Toth, Pointed and colored binary encompassing trees, Proc. 21st Annual ACM Symposium on Computational Geometry (SOCG) (2005) 81-90.
F. Kuhn, P. von Rickenbach, R. Wattenhofer, E. Welzl, A. Zollinger, Interference in cellular networks: The minimum membership set cover problem, Proc. 11th Annual International Computing and Combinatorics Conference (COCOON), Lecture Notes in Computer Science 3595 (2005) 188-198.
M. Marciniszyn, D. Mitsche, M. Stojakovic, Balanced avoidance games on random graphs, Proc. European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB); Discrete Mathematics & Theoretical Computer Science (2005) 329-334.
M. Pauly, N. Mitra, J. Giesen, L. Guibas, M. Gross, Example-based 3D scan completion, Proc. 3rd Symposium on Geometry Processing (SGP) (2005) 23-32.
T Szabó, I. Schurr, Jumping doesn't help in abstract cubes, Proc. 11th Conference on Integer Programming and Combinatorial Optimization (IPCO) (2005) 225-235.
K. Buchin, J. Giesen, Flow complex: General structure and algorithm, Proc. 17th Canadian Conference on Computational Geometry (CCCG) (2005) 270-273.
M. Buchin, J. Giesen, Minimizing the total absolute Gaussian curvature in a terrain is hard, Proc. 17th Canadian Conference on Computational Geometry (CCCG) (2005) 192-195.
M. Henk, J. Matousek, E. Welzl (Eds.), Discrete Geometry, Report No. 17/2005, Oberwolfach Reports 2:2 (2005) 925-994.
M. Hoffmann, Cs. D. Tóth, Pointed binary encompassing trees: Simple and optimal, Abstracts 21st European Workshop on Computational Geometry (EuroCG) (2005) 93-96.
R. BERKE
"Relaxed Coloring of Cubic Graphs",
3rd European
Conference on Combinatorics, Graph Theory and Applications
(Eurocomb),
Berlin, Germany
(Sep 9, 2005).
"Transversals on Abstract Graphs",
5th
Annual Workshop on Combinatorics, Geometry, and Computation (CGC),
Hiddensee, Germany
(Sep 26, 2005).
P. CSORBA
"The Universality and Other Properties of Homomorphism Complexes",
Trends in Topological Combinatorics,
KTH-Stockholm, and the Royal Swedish Academy of Sciences (KVA),
Stockholm, Sweden
(Feb 14, 2005).
"The Universality and Other Properties of Homomorphism Complexes",
Arrangements of Hyperplanes - Algebra, Combinatorics, Geometry, and Topology,
Centro Stefano Franscini,
Ascona, Switzerland
(May 16, 2005).
B. GÄRTNER
"Linear Programming and Unique Sink Orientations",
Joint Meeting of AMS, DMV, and ÖMG,
Johannes Gutenberg University,
Mainz, Germany
(Jun 18, 2005).
J. GIESEN
"Conformal Alpha Shapes",
Upper Rhine Algorithms Workshop (URAW),
Tübingen, Germany (Jul 18, 2005).
"ETH Zürich: Site Presentation",
ACS Kickoff Meeting, Zürich, Switzerland
(Sep 20, 2005).
"Collaborative Sorting",
University of Illinois, Urbana Champaign (Oct 28, 2005).
"Rekonstruktionsprobleme",
Johann Wolfgang Goethe-Universität Frankfurt, Deutschland
(Dec 8, 2005)
M. HOFFMANN
"Pointed Binary Encompassing Trees: Simple and Optimal",
21st European
Workshop on Computational Geometry,
Eindhoven, Netherlands
(Mar 10, 2005).
"Pointed and Colored Binary Encompassing Trees",
21st
Annual Symposium on Computational Geometry,
Pisa, Italy
(Jun 6, 2005).
"Chordless Paths Through Three Vertices",
5th
Workshop on Combinatorics, Geometry, and Computation,
Hiddensee, Germany
(Sep 28, 2005).
D. MITSCHE
"Bounding the Misclassification Error in Spectral
Partitioning in the Planted Partition Model",
Machine Learning Seminar, ETH Zürich
(Oct 19, 2005).
"Bounding the Misclassification Error in
Spectral Partitioning in the Planted Partition Model",
31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG),
Metz, France
(Jun 25, 2005).
"Reconstructing Many Partitions Using Spectral Techniques",
15th International Symposium on Fundamentals of Computation Theory (FCT),
Lübeck, Germany
(Aug 19, 2005).
"Boosting Spectral Partitioning by Sampling and Iteration",
16th International Symposium on Algorithms and Computation (ISAAC),
Hainan, China
(Dec 20, 2005).
A. RAZEN
"Counting Satisfying 2SAT Assignments",
5th Annual Workshop on Combinatorics, Geometry, and Computation (CGC),
Hiddensee, Germany
(Sep 27, 2005).
L. RÜST
"Unique Sink Orientations of Grids", 11th Conference on Integer Programming and Combinatorial Optimization (IPCO), Technische Universität Berlin, Germany (Jun 9, 2005).
"Simple Stochastic Games and P-Matrix Generalized Linear Complementarity Problems",
15th International Symposium on Fundamentals of Computation Theory (FCT),
Lübeck, Germany
(Aug 18, 2005).
E. SCHUBERTH
"Toward Image-Dependent Gamut Mapping: Fast and Accurate Gamut Boundary Determination",
IS&T/SPIE 17th Annual Symposium on Electronic Imaging,
San Jose, USA
(Jan 18, 2005).
"Elicitation of Product Preferences",
Meeting of a team of Google associate product managers from Google headquarters in Mountain View at ETH,
Zürich
(Jun 14, 2005).
"What Colors have to do with Geometry",
Upper Rhine Algorithms Workshop (URAW),
Tübingen, Germany
(Jul 18, 2005).
"Bildabhängiges Gamut Mapping",
EMPA, Dübendorf
(Dec 7, 2005).
M. STOJAKOVIC
"Small Sample Spaces",
SLADIM Seminar,
Department of Mathematics and Computer Science,
Novi Sad, Serbia
(Mar 14, 2005).
"Positional Games on Random Graphs",
Workshop Erdös Magic for Algorithms and Games,
Bertinoro International Center for Informatics,
Bertinoro, Italy
(Apr 25, 2005).
"Random Hamiltonian Cycle Game (and other Games)",
The 12th
International Conference on Random Structures
and Algorithms,
Poznan, Poland
(Aug 1, 2005).
"Balanced Avoidance Games on Random Graphs",
European
Conference on Combinatorics, Graph Theory and
Applications (EUROCOMB),
Berlin, Germany
(Sep 7, 2005).
T. SZABO
"Random Walk on Oriented Hypercubes",
Combinatorics and Complexity Theory Seminar,
Institute for Advanced Study, Princeton, NJ, USA
(Mar 14, 2005).
"Random Walk on Oriented Hypercubes",
Combinatorics Seminar,
City University of New York (CUNY), New York, NY, USA
(Mar 16, 2005).
"Odd Independent Transversals are Odd",
Discrete Mathematics Seminar,
Princeton University, Princeton, NJ, USA
(Mar 23, 2005).
"Random Walk on Oriented Hypercubes",
Workshop
Erdös Magic for Algorithms and Games,
Bertinoro International
Center for Informatics,
Bertinoro, Italy
(Apr 28, 2005).
"Jumping doesn't help in Abstract Cubes",
11th Conference on
Integer Programming and Combinatorial Optimization (IPCO),
Technische Universität Berlin, Germany
(Jun 9, 2005).
"The Random Simplex Algorithm is slow on Abstract Cubes",
The 12th
International Conference on Random Structures and
Algorithms Poznan, Poland
(Aug 5, 2005).
"The Random Simplex Algorithm is slow on Abstract Cubes",
Combinatorics Seminar, Rényi Institute, Budapest, Hungary
(Oct 13, 2005).
"Making, breaking, avoiding, enforcing",
Research Seminar "Theoretische Informatik",
Humboldt University, Berlin, Germany
(Dec 2, 2005).
E. WELZL
"Crossing-Free Matchings",
Seminar on Computational Geometry,
International Conference and Research
Center for Computer Science,
Schloss Dagstuhl, Wadern, Germany
(Mar 16, 2005).
"On the Number of Crossing-Free Matchings and Cycles",
International Seminar on Discrete and Computational Geometry,
Japan Advanced Institute of Science and Technology (JAIST),
Kanazawa, Japan
(Apr 5, 2005).
"Beweise",
Mittelschüllerinnentag, ETH Zürich
(May 10, 2005).
"Counting Plane Graphs on Point Sets in the Plane ",
XI Encuentros de Geometria Computacional,
Santander, Spain
(Jun 27, 2005; invited talk).
"Komplexität, Beweise und Zufall",
Maturandentage, ETH Zürich
(Sep 13, 2005).
"Theoretische Informatik - Algorithmische Geometrie",
Perspektiv-Workshop zur Theoretischen Informatik,
Internationales Begegnungs- und Forschungszentrum für
Informatik (IBFI), Dagstuhl, Germany (Nov 15, 2005).
P. ZUMSTEIN
"Pseudo-Random Graphs via Eigenvalues",
5th Annual Workshop on Combinatorics, Geometry, and Computation (CGC),
Hiddensee, Germany
(Sep 27, 2005).
Erfüllbarkeit logischer Formeln (SAT) - Kombinatorik und Algorithmen, E. Welzl; contact assistant: Robert Berke.
Informatik I (D-ITET), J. Giesen; contact assistant: Bernhard Seybold.
Informatik (D-MATH, D-PHYS), B. Gärtner; contact assistant: Michael Hoffmann.
Seminar zur algorithmischen Geometrie, B. Gärtner, R. Jacob, E. Welzl.
Seminar der Theoretischen Informatik (Mittagsseminar), M. Bläser, B. Gärtner, St. Gerke, J. Giesen, D. Feichtner-Kozlov, A. Steger, T. Szabó, E. Welzl.
Optimization Techniques (English), H.-J Lüthi, K. Fukuda.
Theoretische Informatik (Kernfach), Jiří Matoušek, E. Welzl; (VL Mo9-10, Th14-16; UE Fr 8-10&10-12), contact assistant: Robert Berke, Leo Rüst.
Computational Marketing, J. Giesen; (VL Tu13-15, UE15-16), contact assistant: Eva Schuberth.
Approximate Methods in Geometry, B. Gärtner, J. Giesen, E. Welzl; (VL Tu9-11, UE Tu11-12), contact assistant: Andreas Razen.
Extremal Combinatorics (English), T. Szabó; (VL Fr10-12, UE Fr13-14), contact assistant: Milos Stojakovic.
Seminar Point Based Graphics and Geometry, J. Giesen, M. Gross, E. Welzl; (SE We14-16).
Advanced Topics in Discrete Mathematics: Graphs (English), St. Gerke, A. Steger, T. Szabó; (SE Mo13-15).
Seminar SAT, T. Szabó, E. Welzl; (SE Th10-12), contact assistant: Robert Berke.
Seminar der Theoretischen Informatik (Mittagsseminar), M. Bläser, B. Gärtner, St. Gerke, J. Giesen, D. Feichtner-Kozlov, A. Steger, T. Szabó, E. Welzl; (SE Tu12-13, Th12-13).
Optimization and Applications Seminar, H. Lüthi, K. Fukuda, B. Gärtner, M. Morari; (K Mo16-18).
Workshop on Discrete Geometry, Mathematisches Forschungsinstitut Oberwolfach, Germany, April 10-16, 2005 (Martin Henk, Jiri Matousek, Emo Welzl)
Workshop on Geometric Combinatorics and Optimization, FIM (Institute for Mathematical Research), ETH Zurich, May 23-25, 2005 (Eva-Maria Feichtner, Komei Fukuda, Hans-Jakob Lüthi, Emo Welzl)
Organisation of special session on Discrete Geometry at the Joint Meeting of AMS (American Math. Soc.), DMV (German Math. Soc.), and ÖMG (Austrian Math. Soc.), Mainz, Germany, June 16-19, 2005 (J.E. Goodman, CUNY, New York; E. Welzl, ETH Zurich, G.M. Ziegler, TU Berlin)
3rd Gremo Workshop on Open Problems 2005, Kappel am Albis, Switzerland, July 4-5, 2005 (Michael Hoffmann, Eva Schuberth)
Third Joint Operations Research Days, IBM Zürich Research Lab, Rüschlikon, September 15-16, 2005 (E. Pratsini, IBM-Research; K. Fukuda, ETHZ-EPFL; M. Bierlaire, EPFL)
ACS Kickoff Meeting, ETH Zürich, Zürich, September 20-24, 2005 (B. Gärtner)
Michael Hoffmann,
On the Existence of Paths and Cycles
Advisor: Emo Welzl (referee)
/
Co-referee: Erik Demaine,
Massachusetts Institute of Technology, USA
/
Defense: Jan 21, 2005
Yoshio Okamoto,
Structural Parameters in Combinatorial Objects
Advisor: Emo Welzl (referee)
/
Co-referee: Komei Fukuda, ETH Zurich
/
Defense: Jan 25, 2005
Kaspar Fischer,
Smallest Enclosing Balls - Combinatorial Structure and Algorithms
Advisors: Bernd Gärtner; Emo Welzl (referee)
/
Co-referees: Bernd Gärtner, ETH Zurich, and
Jiri Matousek, Charles University Prague, Czech Republic
/
Defense: Jul 8, 2005
Milos Stojakovic,
Positional Games on Graphs
Advisors: Tibor Szabó; Emo Welzl (referee)
/
Co-referees: Jozsef Beck, Rutgers University, USA, and Tibor Szabó, ETH Zurich
/
Defense: Sep 23, 2005
R. BERKE
Teach. Assistance Erfüllbarkeit logischer Formeln - Kombinatorik und Algorithmen (WS04/05).
Teach. Assistance Theoretische Informatik (Kernfach) (SS05).
Teach. Assistance Seminar SAT (SS05).
Teach. Assistance Coordinator.
Attended the conferences/courses/workshops:
Doccourse Prague, Modern Methods in
Ramsey Theory, Prague, Czech Republic (Jan 22 - Feb 26, 2005).
3rd European
Conference on Combinatorics, Graph Theory and Applications
(Eurocomb),
Berlin, Germany
(Sep 5-9, 2005).
5th
Annual Workshop on Combinatorics, Geometry, and Computation (CGC) ,
Hiddensee, Germany
(Sep 25-28, 2005).
P. CSORBA
Teach. Assistance Topological Combinatorics (WS04/05).
Attended the conferences/courses/workshops:
Workshop on
Discrete Geometry, Mathematisches Forschungsinstitut Oberwolfach, Germany
(Apr 10-16, 2005)
Algebraic and
Geometric Combinatorics, Anogia, Crete (Aug 20-26, 2005).
B. GÄRTNER
Member of the CGAL Editorial Board.
Coordinator ACS.
J. GIESEN
Program committee member of
Symposium on Point-Based Graphics, Stony Brook, USA (2005)
M. HOFFMANN
Teach. Assistance Informatik I (D-MATH, D-PHYS) (WS04/05).
Informatik Koordinator.
Member of the CGAL Editorial Board.
D. MITSCHE
Teach. Assistance Informatik I (D-ITET) (WS04/05).
Teach. Assistance Theoretische Informatik (Kernfach) (SS05).
Coordinator Mittagsseminar.
Attended the conferences/courses/workshops:
31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Metz, France (Jun 23-25, 2005).
15th International Symposium on Fundamentals of Computation Theory (FCT), Lübeck, Germany (Aug 17-20, 2005).
3rd European Conference
on Combinatorics, Graph Theory and Applications (EuroComb`05),
Berlin, Germany (Sep 5-9, 2005).
16th International Symposium on Algorithms and Computation (ISAAC), Hainan, China (Dec 19-21, 2005).
Y. OKAMOTO
Teach. Assistance External Memory Algorithms and Data Structures (WS04/05).
A. RAZEN
Teach. Assistance Approximate Methods in Geometry (SS05).
Attended the conferences/courses/workshops:
5th Annual Workshop on Combinatorics, Geometry, and Computation (CGC),
Hiddensee, Germany (Sep 25-28, 2005).
L. RÜST
Teach. Assistance Informatik I (D-MATH, D-PHYS) (WS04/05).
Teach. Assistance Theoretische Informatik (Kernfach) (SS05).
Webmaster www-gremo.
Attended the conferences/courses/workshops:
11th Conference on Integer Programming and Combinatorial Optimization (IPCO), Technische Universität Berlin, Germany (Jun 8-10, 2005).
15th International Symposium on Fundamentals of Computation Theory (FCT), Lübeck, Germany (Aug 17-20, 2005).
E. SCHUBERTH
Teach. Assistance Bild-Farbe-Reproduktion (WS04/05).
Teach. Assistance Computational Marketing (SS05).
Attended the conferences/courses/workshops:
IS&T/SPIE 17th Annual Symposium on Electronic Imaging,
San Jose, USA
(Jan 18, 2005).
Upper Rhine Algorithms Workshop (URAW),
Tübingen, Germany
(Jul 18, 2005).
M. STOJAKOVIC
Teach. Assistance Graph Theory (WS04/05).
Teach. Assistance Extremal Combinatorics (SS05).
Attended the conferences/courses/workshops:
Workshop
Erdös Magic for Algorithms and Games, Bertinoro, Italy (Apr 24-29, 2005).
The 12th International
Conference on Random Structures and Algorithms, Poznan, Poland (Aug 1-5,
2005).
3rd European
Conference on Combinatorics, Graph Theory and Applications
(Eurocomb), Berlin, Germany (Sep 5-9, 2005).
E. WELZL
Head of Institute of Theoretical Computer Science, ETH Zurich.
Vice-Chair, Department of Computer Science, ETH Zurich.
Program committee member of
13th Annual European Symposium on Algorithms (ESA`05), Ibiza, Spain (Oct 3-6, 2005)
3rd European Conference on Combinatorics, Graph Theory and Applications (EuroComb`05), Berlin, Germany (Sep 5-9, 2005)
Editor (with Jacob Eli Goodman and János Pach) of Combinatorial and Computational Geometry (Mathematical Sciences Research Institute Publications), Cambridge University Press.
Editorial Board member of
Discrete and Computational Geometry, (J. Goodman & R. Pollack, Eds.), Springer Verlag
Computational Geometry - Theory and Applications, (K. Mehlhorn & J.-R. Sack, Eds.), Elsevier Science Publishers
Journal for Universal Computer Science, (H. Maurer, Ed.), Springer Verlag (electronic journal)
Fundamenta Informaticae, (Annales Societatis Mathmaticae Polonae, A. Skowron, Ed.), IOS Press
ORDER, (W.T. Trotter, Ed.), Kluwer Academic Press
Member (chair, contact person) of selection committees for
Full Professor/Assistant Professor (Tenure Track) of Ecosystem Management, Department of Environmental Sciences (chair)
Professorship in Biological Engineering, Department of Chemistry and Applied Biosciences (chair)
Member of the EATCS Council (European Association for Theoretical Computer Science).
Mitglied des Fachausschusses 0.1. Theoretische Informatik der
Gesellschaft für Informatik (GI).
Gutachter für Deutsche Forschungsgemeinschaft (DFG),
Graduiertenkollegs.
Mitglied der Prüfungsgruppe des Schwerpunktprogramms "Algorithmik grosser und komplexer Netzwerke" der Deutschen
Forschungsgemeinschaft (DFG).
Mitglied der Studienkommission der ETH Zürich.
Delegierter für Professorenwahlen an der ETH Zürich.
Coreferee for habilitation of
F. WESSENDORP
Implementation and documentation of a convex quadratic programming solver.
P. ZUMSTEIN
Teach. Assistance Theoretische Informatik (Kernfach) (SS05).
Attended the conferences/courses/workshops:
5th Annual Workshop on Combinatorics, Geometry, and Computation (CGC),
Hiddensee, Germany (Sep 25-28, 2005).
