Univ.-Prof. Dr. Monika Henzinger (Deputy Speaker)

Full Professor (Computer Science), Deputy Speaker

Research areas in the program

  • Combinatorial Optimization
  • Dynamic Optimization
  • Parallel and Distributed Optimization

Keywords

  • combinatorial algorithms
  • efficient algorithms and data structures
  • approximation algorithms for combinatorial optimization problems

Research Interests

Combinatorial algorithms, especially on graphs, efficient algorithms and data structures, approximation algorithms for combinatorial optimization problems

Know-how and infrastructure of the research group

Monika Henzinger is a leading researcher in the area of combinatorial optimization and efficient algorithms and data structures. She is working on questions arising in graph algorithms, online algorithms, and approximation algorithms as well as graph games and algorithmic game theory. She is the principle investigator of the 2013 ERC Advanced Grant on graph algorithms and their applications.

In recent years she has focused on dynamic graph algorithms as well as optimization problems arising in computational biology, computer verification, and in internet advertisement. In a recent line of work (Henzinger, Krinninger, and Nanongkai 2013a, Henzinger, Krinninger, and Nanongkai 2013b, Henzinger, Krinninger, and Nanongkai 2014a, Henzinger, Krinninger, and Nanongkai 2014b,  Henzinger, Krinninger, and Nanongkai 2014c) she consecutively improved the running time for decremental graph algorithm for maintaining approximate shortest paths finally resulting in  the first decremental graph algorithm for maintaining approximate shortest paths in undirected weighted graphs that takes near-constant time per update (Henzinger, Krinninger, and Nanongkai 2014a) and the first such algorithm in directed weighted graphs that takes sublinear time per update   (Henzinger, Krinninger, and Nanongkai 2014b). 

She also gave the first constant-factor approximation algorithm for maximizing a submodular function under viablility constraints, which is a certain type of non-downward closed constraints arising in computational biology (Dvorak, Henzinger, and Williamson 2013). She also published a sequence of papers on optimization problems arising in internet advertising, especially in sponsored search auctions (Duetting, Henzinger, and Starnberger 2013, Duetting, Henzinger, and Weber 2013a, 2013b, Duetting, Henzinger, and Starnberger 2012, Colini-Baldeschi et al 2012, Henzinger and Vidali 2011, Feldman et al 2010).

She also gave recently the first decremental graph algorithm for maintaining approximate shortest paths in directed undirected uncapacitated graphs that takes sublinear time per update (Henzinger, Krinninger, and Nanongkai 2014). She also gave the first linear-time deterministic (1+ε) approximate shortest path algorithm (Henzinger, Krinninger, and Nanongkai 2013).She also recently gave the first constant-factor approximation algorithm for maximizing a submodular function under  viablility constraints, which is a certain type of non-downward closed constraints arising in computational biology (Dvorak, Henzinger, and Williamson 2013).

Collaborations within the VGSCO

With Vladimir Kolmogorov, Nysret Musliu and Günther Raidl on Combinatorial Optimization, with Birgit Rudloff on Dynamic Optimization and with Dan Alistarh on Parallel and Distributed Optimization.

Scientific CV

Study of Computer Science at the University of the Saarland (Saarbruecken), Diplom (1989), Ph.D. in Computer Science at Princeton University (1993). Assistant Professor Cornell University (1993-1996). Research Scientist at Digital Equipment Corporation (1996-1999). Associate Professor of Computer Science at the University of the Saarland (1999). Director of Research at Google Inc (1999-2005), Professor of Computer Science at the Ecole Polytechnique Federale de Lausanne (2005-2009). Professor of Computer Science at the University of Vienna (2009-2023). Since March 2023, Professor of Computer Science at the Institute of Science and Technology Austria.

Editor of two books, and author of more than 40 publications in refereed journals and over 60 publications in refereed conferences, such as:  Journal of the ACM, SIAM Journal of Computing,  Journal of Computer and System Sciences, Algorithmica, Journal of Algorithms, Theoretical Computer Science, IEEE Transactions on the Web,  IEEE Symposium on Foundations of Computer Science,  ACM Symposium on Theory of Computing, ACM/SIAM Symposium on Discrete Algorithms.

Publications

Showing entries 61 - 70 out of 149
Goranci, G, Henzinger, M & Leniowski, D 2018, A Tree Structure for Dynamic Facility Location. in H Bast, G Herman & Y Azar (eds), 26th Annual European Symposium on Algorithms (ESA 2018)., 39, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Wadern, Leibniz International Proceedings in Informatics (LIPIcs), vol. 112, 26th Annual European Symposium on Algorithms (ESA 2018)
, Helsinki, Finland, 20/08/18. https://doi.org/10.4230/LIPIcs.ESA.2018.39
Goranci, G, Henzinger, M & Peng, P 2018, Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs. in H Bast, G Herman & Y Azar (eds), 26th Annual European Symposium on Algorithms (ESA 2018)., 40, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern, Leibniz International Proceedings in Informatics (LIPIcs), vol. 112, 26th Annual European Symposium on Algorithms (ESA 2018)
, Helsinki, Finland, 20/08/18. https://doi.org/10.4230/LIPIcs.ESA.2018.40
Bhattacharya, S, Henzinger, M & Italiano, GF 2018, 'Dynamic algorithms via the primal-dual method', Information and Computation, vol. 261, no. 2, pp. 219-239. https://doi.org/10.1016/j.ic.2018.02.005
Chatterjee, K, Henzinger, M, Loitzenbauer, V, Oraee, S & Toman, V 2018, Symbolic Algorithms for Graphs and Markov Decision Processes with Fairness Objectives. in 30th International Conference on Computer Aided Verification (CAV 2018). Computer Aided Verification - 30th International Conference (CAV), 2018, Oxford, United Kingdom, 14/07/18. https://doi.org/10.1007/978-3-319-96142-213
Bhattacharya, S, Henzinger, M & Italiano, GF 2018, 'Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching', SIAM. Journal on Computing (SICOMP), vol. 47, no. 3, pp. 859-887. https://doi.org/10.1137/140998925
Chatterjee, K, Dvovrák, W, Henzinger, M & Svozil, A 2018, Algorithms and Conditional Lower Bounds for Planning Problems. in MMD Weerdt (ed.), Proceedings of the Twenty-eighth International Conference on Automated Planning and Scheduling: 24-29 June 2018, Delft, the Netherlands / ICAPS 2018 Delft. AAAI Press, Palo Alto, California, ICAPS 2018: 28th International Conference on Automated Planning and Scheduling, Delft, Netherlands, 24/06/18. <https://aaai.org/ocs/index.php/ICAPS/ICAPS18/paper/view/17639>
Biedermann, S, Henzinger, M, Schulz, C & Schuster, B 2018, Memetic Graph Clustering. in 7th International Symposium on Experimental Algorithms (SEA 2018). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Dagstuhl, Leibniz International Proceedings in Informatics (LIPIcs), vol. 103, pp. 3:1-3:15, SEA 2018: 17th International Symposium on Experimental Algorithms, L'Aquila, Italy, 27/06/18. https://doi.org/10.4230/LIPIcs.SEA.2018.3
Goranci, G, Henzinger, M & Thorup, M 2018, 'Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time', ACM Transactions on Algorithms, vol. 14, no. 2, a17. https://doi.org/10.1145/3174803
Henzinger, M, Noe, A, Schulz, C & Strash, D 2018, Practical Minimum Cut Algorithms. in R Pagh & S Venkatasubramanian (eds), 2018 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX). SIAM, Philadelphia, Pennsylvania, pp. 48-61, ALENEX18, New Orleans, United States, 7/01/18. https://doi.org/10.1137/1.9781611975055.5
Bhattacharya, S, Chakrabarty, D, Henzinger, M & Nanongkai, D 2018, Dynamic Algorithms for Graph Coloring. in A Czumaj (ed.), Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, Pennsylvania, pp. 1-20, SODA 2018, New Orleans, United States, 7/01/18. https://doi.org/10.1137/1.9781611975031.1
Showing entries 61 - 70 out of 149
To top