
Theory of Combinatorial Algorithms
Teaching and Research Group Emo Welzl
| Quick~Links: |
Personnel, Guests, Grants, Publications, Lectures, Courses, Workshops, Dissertations, Master Theses, Bachelor Theses, Miscellaneous
|
Personnel
-
Professors
Fukuda, Komei (1/3 appointment)
Welzl, Emo
-
Research Associates and Ph.D. Students
Brise, Yves
Christ, Tobias
Gärtner, Bernd, Dr.
Gebauer, Heidi
Gundert, Anna (since Jan 4)
Hoffmann, Michael, Dr.
Jaggi, Martin
Moser, Robin
Nivasch, Gabriel, Dr.
Scheder, Dominik
Sulovský, Marek
Traxler, Patrick
Wagner, Uli, Dr.
-
Administration
Salow, Andrea
Guests
Grants
-
Linear Time Kernel Methods and Matrix Factorizations
(Financed by Google Research Awards)
The goal of this research is to study fast approximation algorithms for kernel
methods on the one hand, and for approximate matrix factorizations and
semi-definite programs on the other hand.
Building on the coreset paradigm, we try to contribute to the understanding of
sparsity and algorithmic performance on large scale problems of this form, and
will also consider several practical applications from machine learning.
Contact: B.
Gärtner, M.
Jaggi
-
Combinatorial and Computational Aspects of Embeddings
(Financed by the Swiss National Science Foundation).
The goal of this project is to study combinatorial and algorithmic questions
related to the embeddability of simplicial complexes into Euclidean space and
obstructions thereto.
For graphs, the study of such questions has a long history and is best
exemplified by classical results such as Euler's polyhedral formula,
Kuratowski's characterization of planar graphs in terms of forbidden minors, or
the fact that planarity is testable in linear time.
On the topological side, embeddings of polyhedra and obstructions to their
existence are also a classical and well studied topic in geometric topology.
However, in contrast to the closely related topic of classifying embeddings up
to isotopy, in particular knot theory, which has been studied extensively also
from an algorithmic viewpoint, the computational complexity of the embeddability
problem had, until recently, not been addressed.
The first part of the present project concerns the systematic study of this
complexity question. Together with J. Matousek and Martin Tancer, we have shown
that embeddability of a given simplicial complex is at least NP-hard to test for
a wide range of the parameters (dimension k of the complex and ambient dimension
d), essentially, if they fall outside the metastable range of the
Haefliger-Weber Theorem. Moreover, in some cases the problem is even
algorithmically undecidable. Numerous open problems remain, such as elucidating
the complexity situation within the metastable range.
The second part of the project is concerned with extremal problems for
simplicial complexes and with threshold phenomena for random simplicial
complexes as introduced by Linial and Meshulam, both in the context of
embeddability. A fundamental extremal question is, for instance: How many
triangles can a 2-dimensional simplicial complex contain (in terms of the
number of vertices or the number of edges) if it admits an embedding into
4-space? The corresponding question for random complexes is: If K is a
2-dimensional complex on n vertices where every possible triangle is chosen
independently with probability p, what is the threshold probability p=p(n)
for K being embeddable in 4-space?
Contact: U. Wagner
-
k-Sets and Geometric Graphs
(Financed by the Swiss National Science Foundation).
The goal of this project is to investigate two basic and interrelated problems
in discrete and computational geometry.
The first part concerns triangulations and crossing-free geometric graphs in
the plane. These structures are omnipresent, for example optimal Euclidean
matchings, spanning trees and tours are crossing-free, triangulations provide
structure to scattered points sets, etc. Moreover, combinatorial structures
relate to this notion, e.g. well-formed parenthesis expressions or binary trees.
While the situation is well-understood for point sets in convex position
(then it amounts to Catalan structures whose investgation goes back to Euler
around 1750), the general setting is much less understood. This concerns
extremal problems, algorithmic counting and enumeration.
The second part of the project concerns the combinatorics partitioning point
sets in the plane by a line into two parts of prescribed sizes.
The question how many such partitions there can be for a point set of a given
size is known as the "k-set problem". Apart from its intrinsic interest as a
combinatorial question, this problem arises in the analysis of a number of
geometric algorithms, and also turns out to be pivotal for numerous other
geometric questions, some of which seem at first quite unrelated.
One focus of this part will be on identities for k-sets and k-facets through
continuous motion, in particular in the 3-dimensional case. Moreover, we plan
to further investigate applications of k-sets to other geometric problems, e.g.
circle and sphere containment problems and to rectilinear crossing numbers.
Contact: U. Wagner
-
Support Vector Machines: Geometry, Combinatorics and Algorithms
(Financed by the Swiss National Science Foundation).
The goal of this project is to study the geometric, combinatorial, and
algorithmic foundations of support vector machines (SVM). The
focus is on techniques that are orthogonal to the techniques
used and developed in the machine learning community. The project will
be carried out as an (inter)national collaboration, with two partners
from Switzerland (ETH Zürich), and one partner from Germany
(Friedrich-Schiller-Universität Jena).
Contact: B. Gärtner,
M. Jaggi
-
A Fresh Look at the Complexity of Pivoting in Linear Complementarity
(Financed by the Swiss National Science Foundation.)
We propose to study both linear and convex quadratic programming in a more general setting:
by examining the linear complementarity problem with sufficient matrices. Besides providing
a unifying framework for the two problems, linear complementarity also has many direct
applications, e.g. in control theory, finance, algorithmic game theory.
The tools we will use in our research can generally be described as combinatorial abstract
models of optimisation problems. We concentrate on two of them: oriented matroids and unique-sink
orientations.
Several algorithms have been suggested by previous research in this area. For most of them there
are both positive and negative results: they are known to be polynomial on some subclasses of
the problems, but super-polynomial on other, larger classes. For many classes, however, such
analysis is missing (among them are the two we consider the most important, that is, LCP with
P-matrices and with sufficient matrices). At present randomised algorithms appear promising,
and hence we plan to concentrate on their analysis.
We plan to attack the problem from two sides. We aim to find new classes of problems for which
some algorithm runs in polynomial (or expected polynomial) time; and we will search for new
examples of abstract optimisation problems for which known algorithms are slow. This will in
turn reduce the gap between positive and negative results for these algorithms. We believe
that this approach will eventually lead to a strongly polynomial algorithm for the linear
complementarity problem with sufficient matrices.
Contact:
K. Fukuda, ETHZ and EPFL,
J. Foniok, ETHZ
Publications
-
Books
-
Journals (with refereeing)
R. Berke, D. Mitsche, Colorings at Minimum Cost,
Discrete Mathematics 310:3
(2010), 561-569.
R. Berke, T. Szabo, Deciding Relaxed Two-Colorability - A Hardness
Jump,
Combinatorics, Probability and Computing (2010), to appear.
T. Christ, M. Hoffmann, Y. Okamoto, T. Uno,
Improved Bounds for Wireless Localization,
Algorithmica (2010), to appear.
K. Fukuda, S. Moriyama, H. Nakayama and J. Richter-Gebert,
Every non-euclidean oriented matroid admits a biquadratic final polynomial,
Combinatorica
(2010), to appear.
K. Fukuda, C. Weibel,
A linear equation for minkowski sums of polytopes relatively in general position,
European J. Combinatorics
(2010), to appear.
M. Hoffmann, B. Speckmann, Cs.D. Tóth,
Pointed binary encompassing trees: simple and optimal,
Computational Geometry - Theory and Applications
43:1 (2010), 35-41.
R. Moser, G.Tardos,
A Constructive Proof of the General Lovász Local Lemma,
Journal of the ACM (2010), to appear.
-
Conference Proceedings (with selection process)
-
Other (including submitted work)
Y. Brise, B. Gärtner,
Clarkson's Algorithm for Violator Spaces, Computational Geometry: Theory and Applications (2010), submitted.
K. Buchin, J. Matoušek, R. Moser, D. Pálvölgyi,
Vectors in a Box
(2010), submitted.
T. Christ, D. Pálvölgyi, M. Stojaković,
Consistent digital line segments,
Symposium of Computational Geometry (SoCG) (2010), submitted.
J. Foniok, K. Fukuda, L. Klaus,
Combinatorial Characterizations of K-matrices,
(2010), submitted.
B. Gärtner, J. Giesen, M. Jaggi,
A combinatorial algorithm to compute regularized part-worth
values in choice based conjoint analysis, (2010), submitted.
J. Giesen, M. Jaggi, S. Laue,
Approximating Parameterized Convex Optimization Problems,
(2010), submitted.
D. Hefetz, M. Krivelevich, M. Stojaković, T. Szabó,
Fast winning strategies in Avoider-Enforcer games, (2010), submitted.
H. Nakayamka, S. Moriyama, K. Fukuda,
Realizations of oriented matroids by polynomial optimization,
(2010), submitted.
H. Nakayamka, S. Moriyama, K. Fukuda,
Three characteristic rank-4 oriented matroids,
(2010), submitted.
A. Razen, E. Welzl, Counting Crossing-Free Geometric Graphs with Exponential
Speed-Up, (2010), submitted.
T. Szabó, P. Zumstein, S Zürcher,
On the Minimum Degree of Minimal Ramsey Graphs (2010), submitted.
Lectures
M. HOFFMANN
"Plane Graphs with Parity Constraints",
Noon Seminar, TU Eindhoven, Netherlands (Jan 18, 2010).
U. WAGNER
"Complete Minors in Simplicial Complexes",
Combinatorics Seminar, The Hebrew University of Jerusalem, Israel
(Jan 18 & 25, 2010).
"Complete Minors in Hypergraphs and Simplicial Complexes",
Combinatorics Seminar, Tel-Aviv University, Tel-Aviv, Israel
(Jan 24, 2010).
Courses and Seminars
Spring 10
-
Graph Drawing,
B. Gärtner, M. Hoffmann,
(VL Mo10-12 CAB G51, UE Mo 13-14 CAB G59, [+1A]), contact assistant: Marek Sulovský.
-
Integer Programming,
J. Foniok, K. Fukuda,
(VL Tu15-17 HG E1.1, UE Tu17-18 HG E1.1),
contact assistant: Lorenz Klaus.
-
Metric Embeddings,
J. Matoušek, U. Wagner,
(VL Tu11-12, CAB G51, Th10-12, HG G26.1, UE Mo11-12 HG D5.2, Tu14-15, IFW A32.1, [+1A]),
contact assistant: Gabriel Nivasch.
-
Optimization and Applications Seminar,
K. Fukuda, B. Gärtner, D. Klatte, H. Lüthi, J. Lygeros, J. Mayer, M. Morari, K. Schmedders;
(K Mo16-18 HG G19.1).
-
Seminar Computational Geometry,
B. Gärtner, M. Hoffmann, E. Welzl;
(SE Fr14-16 CAB G59).
-
Seminar der Theoretischen Informatik (Mittagsseminar),
B. Gärtner, D. Hefetz, M. Hoffmann, G. Nivasch, U. Wagner, E. Welzl;
(SE Tu12-13 CAB G51, Th12-13 CAB G51).
-
Seminar SAT,
E. Welzl; (SE Tu13-15 CAB G52), contact assistant: tba.
Fall 09
-
Algorithms, Probability, and Computing,
E. Welzl;
(VL Mo13-14 CAB G11, Tu14-16 CAB G51; UE We13-15, Th8-10, Fr14-16, [+2A]),
contact assistant: Dominik Scheder.
-
Computational Geometry,
B. Gärtner, M. Hoffmann;
(VL Mo13-15 CAB G59, Th13-14 CAB G51, UE Th14-16 CAB G51, [+1A])
contact assistant: Tobias Christ.
-
Diskrete Mathematik (D-ITET),
U. Wagner, E. Welzl;
(VL Mo10-12 CAB G11, UE Fr10-12 biweekly),
contact assistants: Torsten Mütze, Luca Gugelmann.
-
Graphs and Algorithms: Advanced Topics,
D. Hefetz, U. Wagner;
(VL We10-12 CAB G56, UE Th11-12 CHN D42, [+1A])
contact assistant: Heidi Gebauer.
-
Informatik (D-MATH, D-PHYS),
B. Gärtner, J. Hromkovic;
(VL Tu13-15, UE Tu15-17),
contact assistant: Yves Brise.
-
Satisfiability of Boolean Formulas - Combinatorics and Algorithms,
E. Welzl;
(VL We8-10 CAB G56, Fr11-12 CAB G52, UE Fr9-11 CAB G52, [+1A]),
contact assistant: Dominik Scheder.
-
Theory of Computing (Theoretische Informatik),
J. Hromkovic, E. Welzl;
(VL Tu10-12 CAB G61, Fr8-10 CAB G61, UE We13-15, discussion hour Th12-13 HG F7, [+1A]),
contact assistant: Hans-Joachim Böckenhauer.
-
Algorithms Lab,
E. Welzl;
(VL Mo17-19 CAB G61, UE We17-19, [+1A]),
contact assistants:
Yann Disser,
Michael Hoffmann,
Florian Jug,
Christoph Krautz,
Rastislav Sramek,
Marek Sulovský.
-
Optimization and Applications Seminar,
K. Fukuda, B. Gärtner, P. Kall, D. Klatte, H. Lüthi, M. Morari;
(K Mo16-18 HG E41).
-
Seminar Approximation Algorithms,
B. Gärtner, M. Mihalak, E. Welzl;
(Fr13-15 CAB G52).
-
Seminar der Theoretischen Informatik (Mittagsseminar),
B. Gärtner, D.Hefetz, M. Hoffmann, U. Wagner, E. Welzl;
(SE Tu12-13, Th12-13).
Spring 09
-
Optimization and Applications Seminar,
K. Fukuda, B. Gärtner, D. Klatte, H. Lüthi, J. Lygeros, J. Mayer, M. Morari;
(K Mo16-18 HG G19.1).
-
Approximation Algorithms and Semidefinite Programming (English),
B. Gärtner, J. Matoušek; (VL Tu9-11, Th10-11 CAB H52, UE Tu11-12, Th11-12 CAB H52), contact assistant: Marek Sulovský.
-
Nonlinear Discrete Optimization,
Shmuel Onn (VL We13-15 HG G43, Starts Mar 4), contact assistant: J. Foniok, D. Adjiashvili.
-
Polyhedral Computations,
K. Fukuda; (VL Tu15-17 HG E1.1, UE Tu17-18 HG E1.1), contact assistant: Jan Foniok.
-
Reading Seminar,
U. Wagner, E. Welzl; (SE Fr15-17 CAB G56).
-
Seminar SAT,
E. Welzl; (SE Tu13-15 CAB G52), contact assistant: Robin Moser .
-
Seminar der Theoretischen Informatik (Mittagsseminar),
B. Gärtner, D. Hefetz, M. Hoffmann, A. Steger, U. Wagner, E. Welzl;
(SE Tu12-13 CAB G51, Th12-13 CAB G51).
-
Seminar Computational Geometry,
B. Gärtner, M. Hoffmann, E. Welzl;
(SE Fr14-16 CAB G59).
Organization of Workshops etc.
-
27th European Workshop on Computational Geometry,
Zurich, Switzerland,
March 28 - 30, 2011, (Michael Hoffmann)
-
8th Gremo Workshop on Open Problems 2010,
Morschach (SZ), Switzerland,
Jun 30 - Jul 2, 2010,
(Michael Hoffmann)
-
38th International Colloquium on Automata, Languages and Programming (ICALP),
Zurich, Switzerland,
July 4 - 8, 2011, (Michael Hoffmann)
Dissertations
Master and Diploma Theses
- Stefan Kraft,
The Structure of Minimal Unsatisfiable CNF Formulas,
Advisor: Heidi Gebauer, Dominik Scheder / to be completed
Bachelor and Semester Theses / Internship Projects
-
Timon Hertli,
A Simple Algorithm for 3-SAT,
Advisor: Dominik Scheder / to be completed
-
Urs Holzer,
Relations between the exponential time complexity of NP-complete problems,
Advisor: Dominik Scheder / to be completed
Miscellaneous
Y. BRISE
Webmaster www-gremo.
Teach. Assistance Informatik I (D-MAVT) (Spring 10)
K. FUKUDA
Editorial Board Member of
European J. Combinatorics, Computational Geometry: Theory and Applications,
Applied Mathematics Research eXpress.
Program committee cochair of
B. GÄRTNER
Member of the CGAL Editorial Board.
Editor-in-Chief of CGAL.
Program committee member of
H. GEBAUER
Teach. Assistance Coordinator
M. HOFFMANN
Informatik Koordinator.
Member of the CGAL Editorial Board.
G. NIVASCH
Contact Assistant Metric Embeddings (D-INFK) (Spring 10)
M. SULOVSKÝ
Contact Assistant Graph Drawing (D-INFK) (Spring 10)
E. WELZL
Head of Institute of Theoretical Computer Science, ETH Zurich,
and member of the board of the Department of Computer Science, ETH Zurich.
Program committee member of
Editorial Board member of
-
ACM Transacations on Computation Theory,
(Lance Fortnow, Ed.), ACM
-
Mathematik Kompakt,
(M. Brokate, H.W. Engl, K.-H. Hoffmann, G. Kersting, G. Stroth, E. Welzl, Eds.),
Birkhäuser Verlag
-
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)
Member (chair, contact person) of selection committees for
-
Professor of Orthopedic Technologies in Aging,
Department of Mechanical and Process Engineering, ETH Zurich (chair)
Chair of the EATCS Award committee (with Eugenio Moggi and Pavlos Spirakis).
Mitglied des Fachausschusses 0.1. Theoretische Informatik der Gesellschaft für Informatik (GI).
Mitglied der Lehrkommission (ehemalige Studienkommission) der ETH Zürich.
Delegierter für Professorenwahlen an der ETH Zürich.
Mitglied der Unterrichtskommission des Departements Informatik der ETH Zürich.
|