Prof. Dr. Ernst Althaus

Head of Algorithmics

Johannes Gutenberg University Mainz
Institute of Computer Science
Staudingerweg 9
55128 Mainz
Room: 03-423

 

Phone number:+49 6131 39 23610

 

Office Hours: Arrangement by mail

Short Scientific CV

since December 2008
Professor at the Johannes Gutenberg-Universität Mainz
Head of the research group on "Algorithmics"

December 2009 - December 2015
Senior Researcher at the Max-Planck-Institut für Informatik, Saarbrücken

April 2007 - November 2008
Senior Researcher at the Max-Planck-Insitut für Informatik, Saarbrücken
Heading research area "Combinatorial Optmization"

October 2005 - March 2007
Visiting Professor at the Johannes Gutenberg-Universität Mainz
Head of the research group on "Theoretical Computer Science"

April 2004 - September 2005
Head of an independent research group at the Laboratoire lorrain de recherche en informatique et ses applications (LORIA), Nancy
Heading a research group on "Optimization in Bioinformatics"

September 2002 - March 2004
Postdoc at the Max-Planck-Insitut für Informatik, Saarbrücken

September 2001 - August 2002
Postdoc at the International Computer Science Institute, Berkeley, CA

May 2001 - August 2001
Postdoc at the Max-Planck-Insitut für Informatik, Saarbrücken

February 1999 - April 2001
Researcher at the Max-Planck-Insitut für Informatik, Saarbrücken
Ph. D. candidate in Computer Science at University of Saarbrücken (Universität des Saarlandes) and at MPII.

 

Education

January 2008
Habilitation
Universität des Saarlandes, Saarbrücken

April 2001
Promotion
Supervisor: Kurt Mehlhorn
Title: Curve Reconstruction and the Traveling Salesman Problem

December 1998
Diploma
Supervisor: Kurt Mehlhorn
Title: Berechnung optimaler Steinerbäume in der Ebene

 

Publications (selection)

2022

Althaus, E., Berenbrink, P., Brinkmann, A., and Steiner, R. (2022). On the Optimality of the Greedy Garbage Collection Strategy for SSDs. Proceedings of the 42nd IEEE International Conference on Distributed Computing Systems (ICDCS), 78-88. DOI Author/Publisher URL

2021

Althaus, E., and Ziegler, S. (2021). Optimal Tree Decompositions Revisited: A Simpler Linear-Time FPT Algorithm. In C. Gentile, G. Stecca, and P. Ventura (eds.), Graphs and Combinatorial Optimization: from Theory to Applications: CTW2020 Proceedings (pp. 67-78). Cham:Springer International Publishing. DOI
Althaus, E., Dousti, M. S., and Kramer, S. (2021). Fast Private Parameter Learning and Evaluation for Sum-Product Networks. CoRR, abs/2104.07353.
Althaus, E., Hildebrandt, A., and Mosca, D. (2021). Learning Molecular Classes from Small Numbers of Positive Examples Using Graph Grammars. In Algorithms for Computational Biology (pp. 3-15). Springer International Publishing. DOI
Althaus, E., Schnurbusch, D., Wüschner, J., and Ziegler, S. (2021). On Tamaki’s Algorithm to Compute Treewidths. In D. Coudert and E. Natale (eds.), SEA (Vols 190, pp. 9:1-9:1). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Author/Publisher URL
Hildebrandt, A. K., Althaus, E., and Hildebrandt, A. (2021). Privately Querying Privacy: Privacy Estimation with Guaranteed Privacy of User and Database Party. 56-72. Author/Publisher URL
Häcker, C., Bouros, P., Chondrogiannis, T., and Althaus, E. (2021). Most Diverse Near-Shortest Paths. 229-239. Author/Publisher URL

2020

Althaus, E., Rauterberg, F., and Ziegler, S. (2020). Computing Euclidean Steiner trees over segments. EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION, 8(3-4), 309-325. DOI Author/Publisher URL

2019

Althaus, E., and Ziegler, S. (2019). Optimal Tree Decompositions Revisited: A Simpler Linear-Time FPT Algorithm. CoRR, abs/1912.09144.

2018

Althaus, E., Brinkmann, A., Kling, P., et al. (2018). Scheduling shared continuous resources on many-cores. Journal of Scheduling, 21, 77-92. DOI

2017

Althaus, E., Beber, B., Damm, W., et al. (2017). Verification of linear hybrid systems with large discrete state spaces using counterexample-guided abstraction refinement. Science of Computer Programming, 148, 123-160. DOI
Althaus, E., Hildebrandt, A., Mosca, D. (2017). Graph Rewriting Based Search for Molecular Structures: Definitions, Algorithms, Hardness. Federation of International Conferences on Software Technologies: Applications and Foundations, 43-59.

2015

Althaus, E., and Muttary, U. (2015). University Course Timetabling with Conflict Minimization and Elective Courses. 12th Workshop on Models and Algorithms for Planning and Scheduling Problems, 224-229.
Althaus, E., Beber, B., Kupilas, J., and Scholl, C. (2015). Improving Interpolants for Linear Arithmetic. In B. Finkbeiner, G. Pu, and L. Zhang (eds.), ATVA (Vols 9364, pp. 48-63). Springer. Author/Publisher URL

2014

Althaus, E., Hildebrandt, A., Hildebrandt, A. K. (2014). A Greedy Algorithm for Hierarchical Complete Linkage Clustering. International Conference on Algorithms for Computational Biology, 25-34.
Hildebrandt, A. K., Dietzen, M., Lengauer, T., et al. (2014). Efficient computation of root mean square deviations under rigid transformations. Journal of computational chemistry, 35, 765-771.
Hildebrandt, A., Krupp, M. (2014). Algorithms for the maximum weight connected k-induced subgraph problem. Combinatorial Optimization and Applications, 268-268.
Scholl, C., Pigorsch, F., Disch, S., Althaus, E. (2014). Simple interpolants for linear arithmetic. In G. P. Fettweis and W. Nebel (eds.), DATE (pp. 1-6). European Design and Automation Association. Author/Publisher URL

2013

Althaus, E., Kupilas, J., Naujoks, R. (2013). On the low-dimensional Steiner minimum tree problem in Hamming metric. Theoretical computer science, 505, Seiten: 2-10. Author/Publisher URL
Hildebrandt, A. K., Althaus, E., Lenhof, H.-P., et al. (2013). Efficient Interpretation of Tandem Mass Tags in Top-Down Proteomics. German Conference on Bioinformatics 2013, 34, 56-67.

2012

Althaus, E., Hoffmann, S., Kupilas, J., and Thaden, E. (2012). A Column Generation Approach to Scheduling of Real-Time Networks - Best Paper Award of International Conference on Computer Science and Applications 2012 (S. I. Ao, C. Douglas, W. S. Grundfest, and J. Burgstone, eds.; pp. 224-229). Newswood Limited.
Althaus, E., and Dumitriu, D. (2012). Certifying feasibility and objective value of linear programs. Operations Research Letters, 40(4), 292-297. DOI

2011

Althaus, E., Canzar, S., Elbassioni, K., et al. (2011). Approximation Algorithms for the Interval Constrained Coloring Problem. Algorithmica, 61(2), 342-361. DOI
Althaus, E., Altmeyer, S., Naujoks, R. (2011). Precise and efficient parametric path analysis. In J. Vitek and B. D. Sutter (eds.), LCTES (pp. 141-150). ACM. Author/Publisher URL
Althaus, E., Altmeyer, S., Naujoks, R. (2011). Symbolic Worst Case Execution Times. In A. Cerone and P. Pihlajasaari (eds.), ICTAC (Vols 6916, pp. 25-44). Springer. Author/Publisher URL
Althaus, E., Becker, B., Dumitriu, D., Kupferschmid, S. (2011). Integration of an LP Solver into Interval Constraint Propagation. In W. Wang, X. Zhu, and D.-Z. Du (eds.), COCOA (Vols 6831, pp. 343-356). Springer. Author/Publisher URL
Althaus, E., Kupilas, J., Naujoks, R. (2011). On the Low-Dimensional Steiner Minimum Tree Problem in Hamming Metric. In M. Ogihara and J. Tarui (eds.), TAMC (Vols 6648, pp. 308-319). Springer. Author/Publisher URL
Althaus, E., Naujoks, R., Thaden, E. (2011). A Column Generation Approach to Scheduling of Periodic Tasks. In P. M. Pardalos and S. Rebennack (eds.), SEA (Vols 6630, pp. 340-351). Springer. Author/Publisher URL

2010

Althaus, E., Canzar, S., Ehrler, C., et al. (2010). Computing H/D-Exchange rates of single residues from data of proteolytic fragments. BMC Bioinformatics, 11(1). DOI
Althaus, E., Hachenberger, P. (2010). Fully Automatic Trunk Packing with Free Placements. CoRR, abs/1008.3773.

2009

Meyer-Baese, A., Cappendijk, S., Althaus, E. (2009, June). Global uniform stability analysis of biological networks with different time-scales under perturbations. 2009 International Joint Conference on Neural Networks. Published. 2009 International Joint Conference on Neural Networks (IJCNN 2009 - Atlanta). DOI
Althaus, E., Canzar, S., Ehrler, C., et al. (2009). Discrete Fitting of Hydrogen-Deuterium-Exchange-data of Overlapping Fragments. In H. R. Arabnia and M. Q. Yang (eds.), BIOCOMP (pp. 496-502). CSREA Press. Author/Publisher URL
Althaus, E., Dumitriu, D. (2009). Fast and Accurate Bounds on Linear Programs. In J. Vahrenhold (ed.), SEA (Vols 5526, pp. 40-50). Springer. Author/Publisher URL
Althaus, E., Klau, G. W., Kohlbacher, O., et al. (2009). Integer Linear Programming in Computational Biology. In S. Albers, H. Alt, and S. Näher (eds.), Efficient Algorithms (Vols 5760, pp. 199-218). Springer. Author/Publisher URL
Althaus, E., Kruglov, E., Weidenbach, C. (2009). Superposition Modulo Linear Arithmetic SUP(LA). In S. Ghilardi and R. Sebastiani (eds.), FroCoS (Vols 5749, pp. 84-99). Springer. Author/Publisher URL
Meyer-Bäse, A., Cappendijk, S., Althaus, E. (2009). Robust Stability Analysis of the Tryptophan Regulatory Network of E.Coli. In H. R. Arabnia and M. Q. Yang (eds.), BIOCOMP (pp. 510-513). CSREA Press. Author/Publisher URL

2008

Althaus, E., Canzar, S. (2008). A Lagrangian relaxation approach for the multiple sequence alignment problem. Journal of Combinatorial Optimization, 16(2), 127-154. DOI
Althaus, E., Canzar, S. (2008). LASA: A Tool for Non-heuristic Alignment of Multiple Sequences. In M. Elloumi, J. Küng, M. Linial, et al. (eds.), BIRD (Vols 13, pp. 489-498). Springer. Author/Publisher URL
Althaus, E., Canzar, S., Elbassioni, K. M., et al. (2008). Approximating the Interval Constrained Coloring Problem. In J. Gudmundsson (ed.), SWAT (Vols 5124, pp. 210-221). Springer. Author/Publisher URL
Althaus, E., Canzar, S., Emmett, M. R., et al. (2008). Computing H/D-exchange speeds of single residues from data of peptic fragments. In R. L. Wainwright, H. Haddad (eds.), SAC (pp. 1273-1277). ACM. Author/Publisher URL
Althaus, E., Naujoks, R. (2008). Reconstructing Phylogenetic Networks with One Recombination. In C. C. McGeoch (ed.), WEA (Vols 5038, pp. 275-288). Springer. Author/Publisher URL

2007

Althaus, E., and Canzar, S. (2007). A Lagrangian Relaxation Approach for the Multiple Sequence Alignment Problem. In A. W. M. Dress, Y. Xu, and B. Zhu (eds.), COCOA (Vols 4616, pp. 267-278). Springer. Author/Publisher URL
Althaus, E., Baumann, T., Schömer, E., and Werth, K. (2007). Trunk Packing Revisited. In C. Demetrescu (ed.), WEA (Vols 4525, pp. 420-432). Springer. Author/Publisher URL

2006

Althaus, E., Călinescu, G., Măndoiu, I. I., et al. (2006). Power Efficient Range Assignment for Symmetric Connectivity in Static Ad Hoc Wireless Networks. Wireless Networks, 12(3), 287-299. DOI
Althaus, E., Caprara, A., Lenhof, H.-P., Reinert, K. (2006). A branch-and-cut algorithm for multiple sequence alignment. Mathematical Programming, 105(2-3), 387-425. DOI
Althaus, E., Naujoks, R. (2006). Computing steiner minimum trees in Hamming metric. SODA, 172-181. Author/Publisher URL

2005

Althaus, E., Funke, S., Har-Peled, S., et al. (2005). Approximating k-hop minimum-spanning trees. Operations Research Letters, 33(2), 115-120. DOI

2004

Althaus, E., Eisenbrand, F., Funke, S., and Mehlhorn, K. (2004). Point containment in the integer hull of a polyhedron. In J. I. Munro (ed.), SODA (pp. 929-933). SIAM. Author/Publisher URL
Althaus, E., Karamanis, N., and Koller, A. (2004). Computing Locally Coherent Discourses. In D. Scott, W. Daelemans, and M. A. Walker (eds.), ACL (pp. 399-406). ACL. Author/Publisher URL

2003

Althaus, E., Duchier, D., Koller, A., et al. (2003). An efficient graph algorithm for dominance constraints. Journal of Algorithms, 48(1), 194-219. DOI
Althaus, E., Calinescu, G., Mandoiu, I. I., et al. (2003). Power efficient range assignment in ad-hoc wireless networks. WCNC, 1889-1894. Author/Publisher URL
Althaus, E., Polzin, T., Daneshmand, S. V. (2003). Improving Linear Programming Approaches for the Steiner Tree Problem. In K. Jansen, M. Margraf, M. Mastrolilli, and J. D. P. Rolim (eds.), WEA (Vols 2647, pp. 1-14). Springer. Author/Publisher URL

2002

Althaus, E., Kohlbacher, O., Lenhof, H.-P., Müller, P. (2002). A Combinatorial Approach to Protein Docking with Flexible Side Chains. Journal of Computational Biology, 9(4), 597-612. DOI
Althaus, E., Fink, C. (2002). A Polyhedral Approach to Surface Reconstruction from Planar Contours. In W. J. Cook and A. S. Schulz (eds.), IPCO (Vols 2337, pp. 258-272). Springer. Author/Publisher URL
Althaus, E., Bockmayr, A., Elf, M., et al. (2002). SCIL - Symbolic Constraints in Integer Linear Programming. In R. H. Möhring and R. Raman (eds.), ESA (Vols 2461, pp. 75-87). Springer. Author/Publisher URL
Althaus, E., Caprara, A., Lenhof, H.-P., Reinert, K. (2002). Multiple sequence alignment with arbitrary gap costs: Computing an optimal solution using polyhedral combinatorics. ECCB, 4-16. Author/Publisher URL

2001

Althaus, E., and Mehlhorn, K. (2001). Traveling Salesman-Based Curve Reconstruction in Polynomial Time. SIAM Journal on Computing, 31(1), 27-66. DOI
Althaus, E., Duchier, D., Koller, A., et al. (2001). An efficient algorithm for the configuration problem of dominance graphs. In S. R. Kosaraju (ed.), SODA (pp. 815-824). ACM/SIAM. Author/Publisher URL

2000

Althaus, E. (2000). Curve reconstruction and the traveling salesman problem. Author/Publisher URL
Althaus, E., and Mehlhorn, K. (2000). TSP-based curve reconstruction in polynomial time. In D. B. Shmoys (ed.), SODA (pp. 686-695). ACM/SIAM. Author/Publisher URL
Althaus, E., Kohlbacher, O., Lenhof, H.-P., and Müller, P. (2000). A combinatorial approach to protein docking with flexible side-chains. In R. Shamir, S. Miyano, S. Istrail, et al. (eds.), RECOMB (pp. 15-24). ACM. Author/Publisher URL

1998

Althaus, E., and Mehlhorn, K. (1998). Maximum network flow with floating point arithmetic. Information Processing Letters, 66(3), 109-113. DOI