Dekan Prof, Dr. Jörg Eschmeier, Prüfungsausschuss Prof, ...
This thesis develops the theory of dominance constraints, a family of logical languages that describe trees, and applies them as a formalism for the underspecified description of scope ambiguities in...
Trunk packing revisited (2008)
Ernst Althaus, Tobias Baumann, Elmar Schömer, Kai Werth
Abstract. For trunk packing problems only few approximation schemes are known, mostly designed for the European standard DIN 70020 [10] with equally sized boxes [12, 13, 15, 16]. In this paper two...
Abstract Point Containment in the Integer Hull of a Polyhedron 1 (2008)
Ernst Althaus, Friedrich Eisenbrand, Stefan Funke, Kurt Mehlhorn
We show that the point containment problem in the integer hull of a polyhedron, which is defined by m inequalities, with coefficients of at most ϕ bits can be solved in time O(m + ϕ) in the...
A Branch-and-Cut Algorithm for Multiple Sequence Alignment (2008)
Ernst Althaus, Alberto Caprara, Hans-peter Lenhof, Knut Reinert
Abstract. We consider a branch-and-cut approach for solving the multiple sequence alignment problem, which is a central problem in computational biology. We propose a general model for this problem...
SCIL - Symbolic Constraints in Integer Linear Programming (2008)
Ernst Althaus, Alexander Bockmayr, Matthias Elf, Michael Jünger, Thomas Kasper, Kurt Mehlhorn
We describe a new software system SCIL that introduces symbolic constraints into branch-and-cut-and-price algorithms for integer linear programs. Symbolic constraints are known from constraint...
Approximating the Interval Constrained Coloring Problem (2008)
Althaus, Ernst, Canzar, Stefan, Elbassioni, Khaled, Karrenbauer, Andreas, Mestre, Julián
Computing H/D-exchange speeds of single residues from data of peptic fragments (2008)
Althaus, Ernst, Canzar, Stefan, Emmett, Mark, Karrenbauer, Andreas, Marshall, Alan, Meyer-Bäse, Anke, ...
An Ecient Algorithm for the Conguration Problem of Dominance Graphs (2007)
Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren, Sven Thiel
Dominance constraints are logical tree descriptions originating from automata theory that have multiple applications in computational linguistics. The satisability problem of dominance constraints is...
Ernst Althaus, Stefan Canzar, Ernst Althaus, Stefan Canzar
problem efficiently
Approximating k-hop minimum-spanning trees (2005)
Althaus, Ernst, Funke, Stefan, Har-Peled, Sariel, Könemann, Jochen, A. Ramos, Edgar, Skutella, Martin
Given a complete graph on~n nodes with metric edge costs, the minimum-cost k-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
Approximating k-hop minimum-spanning trees (2005)
Althaus, Ernst, Funke, Stefan, Har-Peled, Sariel, Könemann, Jochen, A. Ramos, Edgar, Skutella, Martin
Given a complete graph on~n nodes with metric edge costs, the minimum-cost k-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
Approximation k-hop minimum-spanning trees (2005)
Ernst Althaus, Stefan Funke, Sariel Har-peled, Edgar A. Ramos, Martin Skutella
Abstract Given a complete graph on n nodes with metric edge costs, the minimum-cost k- hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest...
Approximating k-Hop Minimum-Spanning Trees (2005)
Ernst Althaus, Stefan Funke, Sariel Har-Peled, Jochen Könemann, Edgar A. Ramos, Martin Skutella
Given a complete graph on n nodes with metric edge costs, the minimum-cost k-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
Approximating k-Hop Minimum-Spanning Trees (2005)
Ernst Althaus, Stefan Funke, Sariel Har-Peled, Jochen Könemann, Edgar A. Ramos, Martin Skutella
Given a complete graph on n nodes with metric edge costs, the minimum-cost k-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
Approximation k-hop minimum-spanning trees (2005)
Ernst Althaus, Stefan Funke, Sariel Har-peled, Jochen Könemann, Edgar A. Ramos, Martin Skutella
Given a complete graph on n nodes with metric edge costs, the minimum-cost khop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
Approximating k-Hop Minimum-Spanning Trees (2005)
Althaus, Ernst, Funke, Stefan, Har-Peled, Sariel, Könemann, Jochen, Ramos, Edgar A., Skutella, Martin
In this paper we consider the problem of computing minimum-cost spanning trees with depth restrictions. Specifically, we are given an $n$-node complete graph $G$, a metric cost-function $c$ on its...
An efficient graph algorithm for dominance constraints (2004)
Althaus, Ernst, Duchier, Denys, Koller, Alexander, Mehlhorn, Kurt, Niehren, Joachim, Thiel, Sven
Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify normal...
Curve reconstruction and the traveling salesman problem (2004)
An instance of the curve reconstruction problem is a finite sample set V of an unknown collection of curves gamma. The task is to connect the points in V in the order in which they lie on gamma....
Point containment in the integer hull of a polyhedron (2004)
Althaus,Ernst, Eisenbrand,Friedrich, Funke,Stefan, Mehlhorn,Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time $O(m+\varphi)$...
Computing Locally Coherent Discourses. (2004)
Althaus,Ernst, Karamanis,Nikiforos, Koller,Alexander
We present the first algorithm that computes optimal orderings of sentences into a locally coherent discourse. The algorithm runs very efficiently on a variety of coherence measures from the...
Point Containment in the Integer Hull of a Polyhedron (2004)
Althaus,Ernst, Eisenbrand,Friedrich, Funke,Stefan, Mehlhorn,Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time...
Point containment in the integer hull of a polyhedron (2004)
Althaus,Ernst, Eisenbrand,Friedrich, Funke,Stefan, Mehlhorn,Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time $O(m+\varphi)$...
Point containment in the integer hull of a polyhedron (2004)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time $O(m+\varphi)$...
Computing Locally Coherent Discourses. (2004)
Althaus, Ernst, Karamanis, Nikiforos, Koller, Alexander
We present the first algorithm that computes optimal orderings of sentences into a locally coherent discourse. The algorithm runs very efficiently on a variety of coherence measures from the...
Point Containment in the Integer Hull of a Polyhedron (2004)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time...
Point containment in the integer hull of a polyhedron (2004)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time $O(m+\varphi)$...
Point containment in the integer hull of a polyhedron (2004)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
der Naturwissenschaftlich-Technischen Fakultäten (2004)
René Beier, Dekan Prof, Dr. Jörg Eschmeier, Vorsitzender Prof, Dr. Raimund Seidel, Erstgutachter Prof, ...
We investigate the performance of exact algorithms for hard optimization problems under random inputs. In particular, we prove various structural properties that lead to two general average-case...
Point containment in the integer hull of a polyhedron (2004)
Ernst Althaus, Friedrich Eisenbrand, Stefan Funke, Kurt Mehlhorn
We show that the point containment problem in the integer hull of a polyhedron, which is dened by m inequalities, with coecients of at most ' bits can be solved in time O(m + ') in the...
Point Containment in the Integer Hull of a Polyhedron (2004)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time...
Computing Locally Coherent Discourses. (2004)
Althaus, Ernst, Karamanis, Nikiforos, Koller, Alexander
We present the first algorithm that computes optimal orderings of sentences into a locally coherent discourse. The algorithm runs very efficiently on a variety of coherence measures from the...
An efficient graph algorithm for dominance constraints (2003)
Althaus, Ernst, Duchier, Denys, Koller, Alexander, Mehlhorn, Kurt, Niehren, Joachim, Thiel, Sven
Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify normal...
Improving Linear Programming Approaches for the Steiner Tree Problem (2003)
Althaus,Ernst, Polzin,Tobias, Vahdati Daneshmand,Siavash
We present two theoretically interesting and empirically successful techniques for improving the linear programming approaches, namely graph transformation and local cuts, in the context of the...
Power Efficient Range Assignment in Ad-hoc Wireless (2003)
Althaus,Ernst, Calinescu,Gruia, Mandoiu,Ion, Prasad,Sushil, Tchervenski,Nickolay, Zelikovsly,Alexander
An Efficient Algorithm for the Configuration Problem of Dominance Graphs (2003)
Althaus,Ernst, Duchier,Denys, Koller,Alexander, Mehlhorn,Kurt, Niehren,Joachim, Thiel,Sven
Improving Linear Programming Approaches for the Steiner Tree Problem (2003)
Althaus, Ernst, Polzin, Tobias, Vahdati Daneshmand, Siavash, Jansen, Klaus, Margraf, Marian, Mastrolli, Monaldo, ...
We present two theoretically interesting and empirically successful techniques for improving the linear programming approaches, namely graph transformation and local cuts, in the context of the...
Power Efficient Range Assignment in Ad-hoc Wireless (2003)
Althaus, Ernst, Calinescu, Gruia, Mandoiu, Ion, Prasad, Sushil, Tchervenski, Nickolay, Zelikovsly, Alexander
An Efficient Algorithm for the Configuration Problem of Dominance Graphs (2003)
Althaus, Ernst, Duchier, Denys, Koller, Alexander, Mehlhorn, Kurt, Niehren, Joachim, Thiel, Sven
An Efficient Graph Algorithm for Dominance Constraints (2003)
Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren, Sven Thiel
Abstract. Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify...
An Efficient Graph Algorithm for Dominance Constraints (2003)
Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren, Sven Thiel
Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify normal...
An Efficient Graph Algorithm for Dominance Constraints (2003)
Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren, Sven Thiel
Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NPcomplete. Here we identify normal...
A Polyhedral Approach to Surface Reconstruction from Planar Contours. (2002)
We investigate the problem of reconstruction a surface given its contours on parallel slices. We present a branch-and-cut algorithm which computes the surface with the minimal area. This surface is...
Althaus,Ernst, Caprara,Alberto, Lenhof,Hans-Peter, Reinert,Knut
Multiple sequence alignment is one of the dominant problems in computational molecular biology. Numerous scoring functions and methods have been proposed, most of which result in NP-hard problems. In...
SCIL - Symbolic Constraints in Integer Linear Programming. (2002)
Althaus,Ernst, Bockmayr,Alexander, Elf,Matthias, Kasper,Thomas, Jünger,Michael, Mehlhorn,Kurt
We describe a new software system SCIL that introduces symbolic constraints into branch-and-cut-and-price algorithms for integer linear programs. Symbolic constraints are known from constraint...
A combinatorial approach to protein docking with flexible side chains (2002)
Althaus,Ernst, Kohlbacher,Oliver, Lenhof,Hans-Peter, Müller,Peter
A Polyhedral Approach to Surface Reconstruction from Planar Contours. (2002)
Althaus, Ernst, Fink, Christian, Cook, William J., Schulz, Andreas S.
We investigate the problem of reconstruction a surface given its contours on parallel slices. We present a branch-and-cut algorithm which computes the surface with the minimal area. This surface is...
Althaus, Ernst, Caprara, Alberto, Lenhof, Hans-Peter, Reinert, Knut, Lengauer, Thomas
Multiple sequence alignment is one of the dominant problems in computational molecular biology. Numerous scoring functions and methods have been proposed, most of which result in NP-hard problems. In...
SCIL - Symbolic Constraints in Integer Linear Programming. (2002)
Althaus, Ernst, Bockmayr, Alexander, Elf, Matthias, Kasper, Thomas, Jünger, Michael, Mehlhorn, Kurt, ...
We describe a new software system SCIL that introduces symbolic constraints into branch-and-cut-and-price algorithms for integer linear programs. Symbolic constraints are known from constraint...
A combinatorial approach to protein docking with flexible side chains (2002)
Althaus, Ernst, Kohlbacher, Oliver, Lenhof, Hans-Peter, Müller, Peter
SCIL -- Symbolic Constraints in Integer Linear Programming (2002)
Ernst Althaus, Thomas Kasper, Alexander Bockmayr, Michael Jünger, Matthias Elf, Kurt Mehlhorn
We describe SCIL. SCIL introduces symbolic constraints into branch-and-cut-and-price algorithms for integer linear programs. Symbolic constraints are known from constraint programming and contribute...
SCIP – symbolic constraints in integer linear programming (2002)
Ernst Althaus, Thomas Kasper, Alexander Bockmayr, Michael Junger, Kurt Mehlhorn
We describe SCIL. SCIL introduces symbolic constraints into branch-and-cut-and-price algorithms for integer linear programs. Symbolic constraints are known from constraint programming and contribute...
Althaus, Ernst, Caprara, Alberto, Lenhof, Hans-Peter, Reinert, Knut
Multiple sequence alignment is one of the dominant problems in computational molecular biology. Numerous scoring functions and methods have been proposed, most of which result in NP-hard problems. In...
Curve reconstruction and the traveling salesman problem (2001)
An instance of the curve reconstruction problem is a finite sample set V of an unknown collection of curves gamma. The task is to connect the points in V in the order in which they lie on gamma....
Curve reconstruction and the traveling salesmann problem / (2001)
Saarbrücken, Universiẗat, Diss., 2001.
Traveling salesman-based curve reconstruction in polynomial time (2001)
Abstract. An instance of the curve reconstruction problem is a finite sample set V of an unknown collection of curves γ. The task is to connect the points in V in the order in which they lie on γ....
An Efficient Algorithm for the Configuration Problem of Dominance Graphs (2001)
Althaus, Ernst, Duchier, Denys, Koller, Alexander, Mehlhorn, Kurt, Niehren, Joachim, Thiel, Sven
Dominance constraints are logical tree descriptions originating from automata theory that have multiple applications in computational linguistics. The satisfiability problem of dominance constraints...
Traveling Salesman-Based Curve Reconstruction in Polynomial Time (2001)
Althaus, Ernst, Mehlhorn, Kurt
An instance of the curve reconstruction problem is a finite sample set $V$ of an unknown curve $\gamma$. The task is to connect the points in $V$ in the order in which they lie on $\gamma$....
TSP-Based Curve Reconstruction (2000)
Ernst Althaus, Kurt Mehlhorn, Stefan Schirra
An instance of the curve reconstruction problem is a nite sample V of an unknown curve . The task is to connect the points in V in the order in which they lie on . Several new algorithms for the...
Experiments on Curve Reconstruction (2000)
Ernst Althaus, Kurt Mehlhorn, Stefan Näher, Stefan Schirra
An instance of the curve reconstruction problem is a finite sample V of an unknown curve gamma...
TSP-Based Curve Reconstruction in Polynomial Time (2000)
An instance of the curve reconstruction problem is a nite sample V of an unknown curve and the task is to connect the points in V in the order in which they lie on . Giesen [Gie99] showed recently...
TSP-Based Curve Reconstruction in Polynomial Time (2000)
Althaus, Ernst, Mehlhorn, Kurt
An instance of the curve reconstruction problem is a finite sample set $V$ of an unknown curve $\gamma$. The task is to connect the points in $V$ in the order in which they lie on $\gamma$....
Experiments on curve reconstruction (2000)
Althaus, Ernst, Mehlhorn, Kurt, Näher, Stefan, Schirra, Stefan
Maximum Network Flow with Floating Point Arithmetic (1998)
Althaus, Ernst, Mehlhorn, Kurt
We discuss the implementation of network flow algorithms in floating point arithmetic. We give an example to illustrate the difficulties that may arise when floating point arithmetic is used without...
Graz, Rechts- u. staatswiss. F., Diss., 1942 (Nicht f. d. Austausch).