Monika Henzinger

Publications (as of February 2017)

Home » Publications

Below is a list of recent conference and journal publications (since 2011). For a complete list see DBLP. To download (most of) these papers go to the Eprints Server at the University of Vienna. Here they are grouped into the following topics:

·         Dynamic graph algorithms

·         Static graph algorithms

·         Approximation and online algorithms

·         Distributed graph algorithms

·         Algorithms for problems in MDPs and game graphs with applications to computer verification

·         Algorithmic mechanism design


Recent conference publications (since 2009)

Dynamic graph algorithms

Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time
Sayan Bhattacharya, Deeparnab Chakrabarty, and Monika Henzinger. 19th International Conference on Integer Programming and Combinatorial Opimization (IPCO’17), 2017.

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3n) Worst Case Update Time
Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. 28th ACM SIAM Symposium on Discrete Algorithms (SODA’17), 2017, 470-489.

Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time.
Gramoz Goranci, Monika Henzinger, and Mikkel Thorup. 24th Annual European Symposium on Algorithms (ESA’16), 2016.

Incremental and Fully Dynamic Sugraph Connectivity for Emergency Planning
Monika Henzinger and Stefan Neumann.
24th Annual European Symposium on Algorithms (ESA’16), 2016.

New Deterministic Approximation Algorithms for Fully Dynamic Matching.
Sayan
Bhattacharya, Monika Henzinger, and Danupon Nanongkai. Proc. 48th ACM Symposium on Theory of Computing (STOC’16), 2016.

Design of Dynamic Algorithms via Primal-Dual Method.
Sayan
Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. 42nd International Colloquium on Automata, Languages and Programming (ICALP’15), 2015, 206-218.

Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. 42nd International Colloquium on Automata, Languages and Programming (ICALP’15), 2015, 725-736. [.pdf]

Unifying and Strengthening Hardness for Dynamic Problems via an Online Matrix-Vector Multiplication Conjecture.
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Proc. 47th ACM Symposium on Theory of Computing (STOC’15), 2015, 21-30. [.pdf]

Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos E. Tsourakakis. 47th ACM Symposium on Theory of Computing (STOC’15), 2015, 173-182. [.pdf]

Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.
Sayan Bhattacharya, Monika Henzinger, and Guiseppe Italiano.
25th ACM SIAM Symposium on Discrete Algorithms (SODA’15), 2015, 785-804. [.pdf]

Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
55th Annual IEEE Symposium on Foundations of Computer Science (FOCS’14), Philadelphia, USA, 2014. [.pdf]

Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
ACM Symposium on Theory of Computing (STOC’14), New York USA, 2014. [.pdf]

A Subquadratic-Time Algorithm for Dynamic Single-Source Shortest Paths
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
ACM Symposium on Discrete Algorithms (SODA’14), Portland, USA, 2014. [.pdf]

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
54th Annual IEEE Symposium on Foundations of Computer Science (FOCS’13), Berkeley, USA, 2013. [.pdf]

Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
40th International Colloquium on Automata, Languages and Programming (ICALP’13), Riga, Latvia, 2013. [.pdf]


Static graph algorithms

Local Flow Partitioning for Faster Edge Connectivity.
Monika Henzinger, Satish Rao, and Di Wang. 28th ACM SIAM Symposium on Discrete Algorithms (SODA’17), 2017, 1919-1938.

Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.
Monika Henzinger, Sebastian Krinninger, and Veronika Loitzenbauer. 42nd International Colloquium on Automata, Languages and Programming (ICALP’15), 2015, 713-724. [.pdf]


Approximation and Online Algorithms

Welfare Maximization with Friends-of-Friends Network Externalities.
Sayan Bhattacharya, Wolfgang Dvorak, Monika Henzinger, and Martin Starnberger.
32nd Symposium on Theoretical Aspects of Computer Science (STACS), 2015. [.pdf]

Limiting Price Discrimination when Selling Products with Positive Network Externalities.
Ludek Cigler, Wolfgang Dvorak, Monika Henzinger, and Martin Starnberger.
Proc.~10th Conference on Web and Internet Economics (WINE), 2014, 44-57. [.pdf]

Online Bipartite Matching with Decomposable Weights
Moses Charikar, Monika Henzinger, and Huy Nguyen.
22th Annual European Symposium on Algorithms (ESA’14), Wroclaw, Poland, 2014. [.pdf] [Full version .pdf]

Approximating the Cycle Mean
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, and Veronika Loitzenbauer. Fourth International Symposion on Games, Automata, Logics and Formal Verification (GandALF’13), Borca di Cadore, Italy, 2013. [.pdf]

Maximizing a Submodular Function with Viability Constraints
Wolfgang Dvorak, Monika Henzinger, and David Williamson.
21st Annual European Symposium on Algorithms (ESA’13), Sophia Antipolis, France, 2013. [.pdf]


Distributed graph algorithms

A Deterministic Almost-Tight Distributed Algorithm for Approximating Single_Source Shortest Paths.
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Proc. 48th ACM Symposium on Theory of Computing (STOC’16), 2016.

Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
40th International Colloquium on Automata, Languages and Programming (ICALP’13), Riga, Latvia, 2013. [.pdf]


Algorithms for MDPs and Game Graph Game

Conditionally Optimal Algorithms for Generalized Buchi Games Streett Objectives
Krishnendu Chatterjee, Wolfgang Dvorak, Monika Henzinger, and Veronika Loitzenbauer.

41st Symposium on Mathematical Foundations of Computer Science (MFCS’16), 2016. [.pdf]

Model and Objective Separation with Conditional Lower Bounds: Disjunction is Harder than Conjunction. Streett Objectives
Krishnendu Chatterjee, Wolfgang Dvorak, Monika Henzinger, and Veronika Loitzenbauer.
31st ACM/IEEE Symposium on Logic in Computer Science (LICS’16), 2016. [.pdf]

Improved Algorithms for One-Pair and k-Pair Streett Objectives
Krishnendu Chatterjee, Monika Henzinger, and Veronika Loitzenbauer.

30th ACM/IEEE Symposium on Logic in Computer Science (LICS’15), Kyoto, Japan, 2015. [.pdf]

Polynomial-time Algorithms for Energy Games with Special Weight Structures
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
20th Annual European Symposium on Algorithms (ESA’12), Ljubljana, Slovenia, 2012. [.pdf]

An O(n^2) Time Algorithm for Alternating Buchi Games
Krishnendu Chatterjee and Monika Henzinger
ACM Symposium on Discrete Algorithms (SODA’12), Kyoto, Japan, 2012. [.pdf]

Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Buchi Objectives
Krishnendu Chatterjee, Monika Henzinger, Joglekar Manas, and Shah Nisarg 23rd International Conference on Computer Aided Verification (CAV), Utah, USA, 2011.
Also appeared in Formal Methods in System Design 42(3): 301-327 (2013) [.pdf]

Faster and Dynamic Algorithms For Maximal End-Component Decomposition And Related Graph Problems In Probabilistic Verification
Krishnendu Chatterjee and Monika Henzinger
ACM Symposium on Discrete Algorithms (SODA’11), San Francisco, USA, 2011. [.pdf]


Mechanism Design

Combinatorial Auctions with Conflict-Based Externalities
Yun Kuen Cheung, Monika Henzinger, Martin Hoefer, and Martin Starnberger
Conference on Web and Internet Economics (WINE’15), Amsterdam, The Netherlands, December 2015. [.pdf]

Ad Exchange: Envy-free Auctions with Mediators
Oren Ben-Zwi, Monika Henzinger, and Veronika Loitzenbauer
Conference on Web and Internet Economics (WINE’15), Amsterdam, The Netherlands, December 2015. [.pdf]

Truthful Unit-Demand Auctions with Budgets Revisited
Monika Henzinger and Veronika Loitzenbauer
Theoretical Computer Science, 573:1-15, 2015. [.pdf]

Valuation Compressions in Combinatorial Auctions
Paul Dütting, Monika Henzinger, Martin Starnberger
Conference on Web and Internet Economics (WINE’13), Cambridge, MA, December 2013
[.pdf]

On Multiple Keyword Sponsored Search Auctions with Budgets
Riccardo Colini Baldeschi, Monika Henzinger, Stefano Leonardi, and Martin Starnberger
39th International Colloquium on Automata, Languages and Programming (ICALP’12), Warwick, UK, 2012. [.pdf]

Auctions with Heterogeneous Items and Budget Limits
Paul Dütting, Monika Henzinger, Martin Starnberger
Workshop on Internet & Network Economics (WINE’12), Liverpool, UK, 2012.
[.pdf | .ps | report]

Maximizing Revenue from Strategic Recommendations under Decaying Trust
Paul Dütting, Monika Henzinger, Ingmar Weber
Conference on Information and Knowledge Management (CIKM’12), Maui, USA, 2012.

[.pdf | .ps | report | poster]

Multi-Parameter Mechanism Design under Budget and Matroid Constraints
Monika Henzinger and Angelina Vidali
European Symposium on ALgorithms (ESA’11), Saarbruecken, Germany, 2011. [.pdf]

An Expressive Mechanism for Auctions on the Web
Paul Dütting, Monika Henzinger, and Ingmar Weber
World Wide Web Conference (WWW’11), Hyderabad, India, 2011
[.pdf | .ps | report | poster]

How Much is Your Personal Recommendation Worth? (Best Poster Award)
Paul Dütting, Monika Henzinger, and Ingmar Weber
World Wide Web Conference (WWW’10), Raleigh, USA, 2010
[.pdf | .ps | report | poster]

Sponsored Search, Market Equilibria, and the Hungarian Method
Paul Dütting, Monika Henzinger, and Ingmar Weber
Symposium on Theoretical Aspects of Computer Science (STACS’10), Nancy, France, 2010
[.pdf | .ps | report]

Bidder Optimal Assignments for General Utilities
Paul Dütting, Monika Henzinger, and Ingmar Weber
Workshop on Internet & Network Economics (WINE’09), Rome, Italy, 2009
[.pdf | .ps]


Recent journal publications (since 2011)

Maximizing a Submodular Function with Vialbility Constraints.
Wolfgang Dvorak, Monika Henzinger, and David P. Williamson
Algorithmica, 77(1):152-172 (2017).

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
SIAM Journal on Computing, 45(3):947-1006 (2016).

On Multiple Keyword Sponsored Search Auctions with Budgets
Riccardo Colini Baldeschi, Monika Henzinger, Stefano Leonardi, and Martin Starnberger
ACM Transactions on Economics and Computation, 4(1): 2 (2015).
[.pdf]

Auctions with Heterogeneous Items and Budget Limits
Paul Dütting, Monika Henzinger, Martin Starnberger
ACM Transactions on Economics and Computation, 4(1): 4 (2015).
[.pdf | .ps | report]

Truthful Unit-Demand Auctions with Budgets Revisited.
Monika Henzinger and Veronika Loitzenbauer.
Theoretical Computer Science, Volume 573, Pages 1-15, 2015
[.pdf]

An Expressive Mechanism for Auctions on the Web.
Paul Dütting, Monika Henzinger, and Ingmar Weber.
ACM Transactions on Economics and Computation, 4(1): 1 (2015).
[.pdf | .ps]

Efficient and Dynamic Algorithms For Alternating Buchi Games and Maximal End-component Decomposition
Krishnendu Chatterjee and Monika Henzinger
Journal of the ACM, Volume 61, Issue 3, Article No. 15, 2014 [.pdf]

Split Diversity in Constrained Conservation Prioritization using Integer Linear Programming.
Olga Chernomor, Bui Quang Minh, Felix Forest, Steffen Klaere, Travis Ingram, Monika Henzinger, and Arndt von Haeseler.
Methods in Ecology and Evolution, doi: 10.1111/2041-210X.12299, 2014.

Polynomial-time Algorithms for Energy Games with Special Weight Structures
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
Algorithmica, Volume 70, Issue 3, Pages 457-492, 2014. [.pdf]

Approximating the Cycle Mean
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, Veronika Loitzenbauer and Michael A. Rasking
Theoretical Computer Science, 2014, DOI: 10.1016/j.tcs.2014.06.031. [.html]

A Comprehensive Study of Techniques for URL-based Web Page Language Classification
Eda Baykan, Monika Henzinger, and Ingmar Weber
ACM Transactions on the Web, Volume 7, Issue 1, Article No. 3, Pages 3:1-3:37, 2013 [.pdf]

Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Buechi Objectives
Krishnendu Chatterjee, Monika Henzinger, Manas Joglekar, and Nisarg Shah
Formal Methods in System Design, Volume 42, Issue 3, Pages 301-327, 2013. [.pdf]

Bidder Optimal Assignments for General Utilities
Paul Dütting, Monika Henzinger, and Ingmar Weber
Theoretical Computer Science, Volume 478, Pages 67-73, 2013. [.pdf | .ps]

Sponsored Search, Market Equilibria, and the Hungarian Method
Paul Dütting, Monika Henzinger, and Ingmar Weber
Information Processing Letters, Volume 113, Issue 3, Pages 67-73, 2013. [.pdf | .ps]

Offline File Assignments for Online Load Balancing
Paul Dütting, Monika Henzinger, and Ingmar Weber
Information Processing Letters, Volume 111, Issue 4, Pages 178-183, 2011. [.pdf | .ps]

A Comprehensive Study of Features and Algorithms for URL-based Topic Classification
Eda Baykan, Monika Henzinger, Ludmila Marian, and Ingmar Weber
ACM Transactions on the Web, Volume 5, Issue 3, Pages 15:1-15:29, 2011. [.pdf]

Recent invited talks

Internet Auctions
Festvortrag, Tag der Informatik, Fachbereich Informatik, HU Berlin, Germany, May 2013
Internet Auctions
Festvortrag, 40-Jahre-Feier, Fachbereich Informatik, TU Dortmund, Germany, January 2013
Breaking the O(n m) Barrier for Buechi Games and Maximal End-Component Decomposition
Oxford Algorithms Workshop, Oxford, UK, October 2012
Efficient Algorithms and Their Applications
European Computer Science Summit (ECSS), Milan, Italy, November 2011
Mechanisms for the Marriage and Assignment Game
Conference on Algorithms and Complexity (CIAC’10), Rome, Italy, May 2010
[.pdf | .ps]

Patents

I am the co-inventor of over 50 patents.