Monika Henzinger
Henzinger_Monika Group
196 Publications
2024 | Published | Conference Paper | IST-REx-ID: 14769 |
M. H. Henzinger, D. Saulpic, and L. Sidl, “Experimental evaluation of fully dynamic k-means via coresets,” in 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments, Alexandria, VA, United States, 2024, pp. 220–233.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 15008 |
G. Goranci, M. H. Henzinger, H. Räcke, S. Sachdeva, and A. R. Sricharan, “Electrical flows for polylogarithmic competitive oblivious routing,” in 15th Innovations in Theoretical Computer Science Conference, Berkeley, CA, United States, 2024, vol. 287.
[Published Version]
View
| Files available
| DOI
| arXiv
2023 | Published | Conference Paper | IST-REx-ID: 12760 |
M. H. Henzinger, S. Neumann, H. Räcke, and S. Schmid, “Dynamic maintenance of monotone dynamic programs and applications,” in 40th International Symposium on Theoretical Aspects of Computer Science, Hamburg, Germany, 2023, vol. 254.
[Published Version]
View
| Files available
| DOI
| arXiv
2023 | Published | Conference Paper | IST-REx-ID: 13236 |
D. W. Zheng and M. H. Henzinger, “Multiplicative auction algorithm for approximate maximum weight bipartite matching,” in International Conference on Integer Programming and Combinatorial Optimization, Madison, WI, United States, 2023, vol. 13904, pp. 453–465.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2023 | Published | Journal Article | IST-REx-ID: 14043 |
M. H. Henzinger, B. Jin, R. Peng, and D. P. Williamson, “A combinatorial cut-toggling algorithm for solving Laplacian linear systems,” Algorithmica, vol. 85. Springer Nature, pp. 2680–3716, 2023.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| WoS
| arXiv
2023 | Published | Conference Paper | IST-REx-ID: 14085 |
G. Goranci and M. H. Henzinger, “Efficient data structures for incremental exact and approximate maximum flow,” in 50th International Colloquium on Automata, Languages, and Programming, Paderborn, Germany, 2023, vol. 261.
[Published Version]
View
| Files available
| DOI
2023 | Published | Conference Paper | IST-REx-ID: 14086 |
M. H. Henzinger, P. Liu, J. Vondrák, and D. W. Zheng, “Faster submodular maximization for several classes of matroids,” in 50th International Colloquium on Automata, Languages, and Programming, Paderborn, Germany, 2023, vol. 261.
[Published Version]
View
| Files available
| DOI
| arXiv
2023 | Published | Conference Paper | IST-REx-ID: 14462 |
H. Fichtenberger, M. H. Henzinger, and J. Upadhyay, “Constant matters: Fine-grained error bound on differentially private continual observation,” in Proceedings of the 40th International Conference on Machine Learning, Honolulu, Hawaii, HI, United States, 2023, vol. 202, pp. 10072–10092.
[Published Version]
View
| Download Published Version (ext.)
2023 | Published | Journal Article | IST-REx-ID: 14558
S. Bhattacharya, M. H. Henzinger, D. Nanongkai, and X. Wu, “Deterministic near-optimal approximation algorithms for dynamic set cover,” SIAM Journal on Computing, vol. 52, no. 5. Society for Industrial and Applied Mathematics, pp. 1132–1192, 2023.
View
| DOI
2022 | Published | Conference Paper | IST-REx-ID: 11808 |
K. Hanauer, M. H. Henzinger, and C. Schulz, “Recent advances in fully dynamic graph algorithms,” in 1st Symposium on Algorithmic Foundations of Dynamic Networks, Virtual, 2022, vol. 221.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2022 | Published | Conference Paper | IST-REx-ID: 11812 |
K. Hanauer, M. H. Henzinger, and Q. C. Hua, “Fully dynamic four-vertex subgraph counting,” in 1st Symposium on Algorithmic Foundations of Dynamic Networks, Virtual, 2022, vol. 221.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2022 | Published | Conference Paper | IST-REx-ID: 11930 |
M. H. Henzinger, A. Noe, and C. Schulz, “Practical fully dynamic minimum cut algorithms,” in 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments, Alexandria, VA, United States, 2022, pp. 13–26.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2022 | Submitted | Preprint | IST-REx-ID: 14236 |
G. Goranci and M. H. Henzinger, “Incremental approximate maximum flow in m1/2+o(1) update time,” arXiv. .
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2021 | Published | Conference Paper | IST-REx-ID: 11649 |
M. H. Henzinger, A. Paz, and S. Schmid, “On the complexity of weight-dynamic network algorithms,” in IFIP Networking Conference, Espoo and Helsinki, Finland, 2021.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2021 | Published | Journal Article | IST-REx-ID: 11663 |
A. Bernstein, S. Forster, and M. H. Henzinger, “A deamortization approach for dynamic spanner and dynamic maximal matching,” ACM Transactions on Algorithms, vol. 17, no. 4. Association for Computing Machinery, 2021.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2021 | Published | Journal Article | IST-REx-ID: 11756 |
M. H. Henzinger and P. Peng, “Constant-time dynamic weight approximation for minimum spanning forest,” Information and Computation, vol. 281, no. 12. Elsevier, 2021.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2021 | Published | Conference Paper | IST-REx-ID: 11771 |
M. H. Henzinger and X. Wu, “Upper and lower bounds for fully retroactive graph problems,” in 17th International Symposium on Algorithms and Data Structures, Virtual, 2021, vol. 12808, pp. 471–484.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2021 | Published | Conference Paper | IST-REx-ID: 11814 |
H. Fichtenberger, M. H. Henzinger, and W. Ost, “Differentially private algorithms for graphs under continual observation,” in 29th Annual European Symposium on Algorithms, Lisbon, Portual, 2021, vol. 204.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2021 | Published | Journal Article | IST-REx-ID: 11886 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “A deterministic almost-tight distributed algorithm for approximating single-source shortest paths,” SIAM Journal on Computing, vol. 50, no. 3. Society for Industrial & Applied Mathematics, pp. STOC16-98-STOC16-137, 2021.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2021 | Published | Conference Paper | IST-REx-ID: 11919 |
T. Bergamaschi, M. H. Henzinger, M. P. Gutenberg, V. V. Williams, and N. Wein, “New techniques and fine-grained hardness for dynamic near-additive spanners,” in 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, VA, United States, 2021, pp. 1836–1855.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2021 | Published | Conference Paper | IST-REx-ID: 11920 |
S. Bhattacharya, M. H. Henzinger, D. Nanongkai, and X. Wu, “Dynamic set cover: Improved amortized and worst-case update time,” in 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, VA, United States, 2021, pp. 2537–2549.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2021 | Published | Conference Paper | IST-REx-ID: 11923 |
M. H. Henzinger, S. Neumann, H. Räcke, and S. Schmid, “Tight bounds for online graph partitioning,” in 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, VA, United States, 2021, pp. 2799–2818.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2021 | Published | Conference Paper | IST-REx-ID: 11931 |
G. Goranci, M. H. Henzinger, D. Leniowski, C. Schulz, and A. Svozil, “Fully dynamic k-center clustering in low dimensional metrics,” in 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments, Alexandria, VA, United States, 2021, pp. 143–153.
[Published Version]
View
| DOI
| Download Published Version (ext.)
2021 | Published | Journal Article | IST-REx-ID: 9293 |
K. Chatterjee, W. Dvořák, M. H. Henzinger, and A. Svozil, “Algorithms and conditional lower bounds for planning problems,” Artificial Intelligence, vol. 297, no. 8. Elsevier, 2021.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| WoS
| arXiv
2021 | Published | Conference Paper | IST-REx-ID: 10002 |
K. Chatterjee, W. Dvorak, M. H. Henzinger, and A. Svozil, “Symbolic time and space tradeoffs for probabilistic verification,” in Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, Rome, Italy, 2021, pp. 1–13.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| WoS
| arXiv
2021 | Published | Conference Paper | IST-REx-ID: 10054 |
K. Chatterjee, M. H. Henzinger, S. S. Kale, and A. Svozil, “Faster algorithms for bounded liveness in graphs and game graphs,” in 48th International Colloquium on Automata, Languages, and Programming, Glasgow, Scotland, 2021, vol. 198.
[Published Version]
View
| Files available
| DOI
2020 | Published | Journal Article | IST-REx-ID: 11674 |
M. H. Henzinger, D. Leniowski, and C. Mathieu, “Dynamic clustering to minimize the sum of radii,” Algorithmica, vol. 82, no. 11. Springer Nature, pp. 3183–3194, 2020.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2020 | Published | Journal Article | IST-REx-ID: 11675 |
S. Bhattacharya, D. Chakrabarty, and M. H. Henzinger, “Deterministic dynamic matching in O(1) update time,” Algorithmica, vol. 82, no. 4. Springer Nature, pp. 1057–1080, 2020.
[Published Version]
View
| DOI
| Download Published Version (ext.)
2020 | Published | Conference Paper | IST-REx-ID: 11816 |
M. H. Henzinger, K. Shahbaz, R. Paul, and C. Schulz, “Dynamic matching algorithms in practice,” in 8th Annual European Symposium on Algorithms, Pisa, Italy, 2020, vol. 173.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2020 | Published | Conference Paper | IST-REx-ID: 11818 |
M. H. Henzinger and S. Kale, “Fully-dynamic coresets,” in 28th Annual European Symposium on Algorithms, Pisa, Italy, 2020, vol. 173.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2020 | Published | Conference Paper | IST-REx-ID: 11819 |
M. H. Henzinger, A. Noe, C. Schulz, and D. Strash, “Finding all global minimum cuts in practice,” in 28th Annual European Symposium on Algorithms, Pisa, Italy, 2020, vol. 173.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2020 | Published | Conference Paper | IST-REx-ID: 11822 |
K. Hanauer, M. H. Henzinger, and C. Schulz, “Faster fully dynamic transitive closure in practice,” in 18th International Symposium on Experimental Algorithms, Pisa, Italy, 2020, vol. 160.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2020 | Published | Conference Paper | IST-REx-ID: 11824 |
M. H. Henzinger, S. Neumann, and A. Wiese, “Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles,” in 36th International Symposium on Computational Geometry, Zurich, Switzerland, 2020, vol. 164.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2020 | Published | Conference Paper | IST-REx-ID: 11825 |
M. H. Henzinger and P. Peng, “Constant-time dynamic (Δ+1)-coloring,” in 37th International Symposium on Theoretical Aspects of Computer Science, Montpellier, France, 2020, vol. 154.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2020 | Published | Conference Paper | IST-REx-ID: 11852 |
L. Chen, G. Goranci, M. H. Henzinger, R. Peng, and T. Saranurak, “Fast dynamic cuts, distances and effective resistances via vertex sparsifiers,” in 61st Annual Symposium on Foundations of Computer Science, Durham, NC, United States, 2020, pp. 1135–1146.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2020 | Published | Conference Paper | IST-REx-ID: 11880 |
K. Hanauer, M. H. Henzinger, and C. Schulz, “Fully dynamic single-source reachability in practice: An experimental study,” in 2020 Symposium on Algorithm Engineering and Experiments, Salt Lake City, UT, United States, 2020, pp. 106–119.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2020 | Published | Conference Paper | IST-REx-ID: 11881 |
M. H. Henzinger, A. Noe, and C. Schulz, “Shared-memory branch-and-reduce for multiterminal cuts,” in 2020 Symposium on Algorithm Engineering and Experiments, Salt Lake City, UT, United States, 2020, pp. 42–55.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2020 | Published | Journal Article | IST-REx-ID: 11889
M. H. Henzinger, S. Rao, and D. Wang, “Local flow partitioning for faster edge connectivity,” SIAM Journal on Computing, vol. 49, no. 1. Society for Industrial & Applied Mathematics, pp. 1–36, 2020.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2020 | Published | Journal Article | IST-REx-ID: 11894 |
G. Goranci, M. H. Henzinger, and P. Peng, “Improved guarantees for vertex sparsification in planar graphs,” SIAM Journal on Discrete Mathematics, vol. 34, no. 1. Society for Industrial & Applied Mathematics, pp. 130–162, 2020.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2019 | Published | Conference Paper | IST-REx-ID: 11826 |
B. Ancona, M. H. Henzinger, L. Roditty, V. V. Williams, and N. Wein, “Algorithms and hardness for diameter in dynamic graphs,” in 46th International Colloquium on Automata, Languages, and Programming, Patras, Greece, 2019, vol. 132.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2019 | Published | Book Chapter | IST-REx-ID: 11847
S. Biedermann, M. H. Henzinger, C. Schulz, and B. Schuster, “Vienna Graph Clustering,” in Protein-Protein Interaction Networks, vol. 2074, S. Canzar and F. Rojas Ringeling, Eds. Springer Nature, 2019, pp. 215–231.
View
| DOI
| PubMed | Europe PMC
2019 | Published | Conference Paper | IST-REx-ID: 11850 |
M. H. Henzinger, S. Neumann, and S. Schmid, “Efficient distributed workload (re-)embedding,” in SIGMETRICS’19: International Conference on Measurement and Modeling of Computer Systems, Phoenix, AZ, United States, 2019, pp. 43–44.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2019 | Published | Conference Paper | IST-REx-ID: 11851
M. H. Henzinger, A. Noe, and C. Schulz, “Shared-memory exact minimum cuts,” in 33rd International Parallel and Distributed Processing Symposium, Rio de Janeiro, Brazil, 2019.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2019 | Published | Conference Paper | IST-REx-ID: 11853 |
S. Bhattacharya, M. H. Henzinger, and D. Nanongkai, “A new deterministic algorithm for dynamic set cover,” in 60th Annual Symposium on Foundations of Computer Science, Baltimore, MD, United States, 2019, pp. 406–423.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2019 | Published | Conference Paper | IST-REx-ID: 11865 |
M. Daga, M. H. Henzinger, D. Nanongkai, and T. Saranurak, “Distributed edge connectivity in sublinear time,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Phoenix, AZ, United States, 2019, pp. 343–354.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2019 | Published | Conference Paper | IST-REx-ID: 11871 |
A. Bernstein, S. Forster, and M. H. Henzinger, “A deamortization approach for dynamic spanner and dynamic maximal matching,” in 30th Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, United States, 2019, pp. 1899–1918.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2019 | Published | Journal Article | IST-REx-ID: 11898 |
S. Bhattacharya, M. H. Henzinger, and S. Neumann, “New amortized cell-probe lower bounds for dynamic problems,” Theoretical Computer Science, vol. 779. Elsevier, pp. 72–87, 2019.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2019 | Published | Conference Paper | IST-REx-ID: 6887 |
K. Chatterjee, W. Dvorák, M. H. Henzinger, and A. Svozil, “Near-linear time algorithms for Streett objectives in graphs and MDPs,” in Leibniz International Proceedings in Informatics, Amsterdam, Netherlands, 2019, vol. 140.
[Published Version]
View
| Files available
| DOI
2018 | Published | Conference Paper | IST-REx-ID: 310 |
K. Chatterjee, W. Dvorák, M. H. Henzinger, and V. Loitzenbauer, “Lower bounds for symbolic computation on graphs: Strongly connected components, liveness, safety, and diameter,” presented at the SODA: Symposium on Discrete Algorithms, New Orleans, Louisiana, United States, 2018, pp. 2341–2356.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| WoS
| arXiv
2018 | Published | Conference Paper | IST-REx-ID: 35 |
K. Chatterjee, W. Dvorák, M. H. Henzinger, and A. Svozil, “Algorithms and conditional lower bounds for planning problems,” in 28th International Conference on Automated Planning and Scheduling , Delft, Netherlands, 2018.
View
| Files available
| Download None (ext.)
| WoS
| arXiv
2018 | Published | Journal Article | IST-REx-ID: 11657 |
M. H. Henzinger, A. Noe, C. Schulz, and D. Strash, “Practical minimum cut algorithms,” ACM Journal of Experimental Algorithmics, vol. 23. Association for Computing Machinery, pp. 1–22, 2018.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2018 | Published | Journal Article | IST-REx-ID: 11664 |
G. Goranci, M. H. Henzinger, and M. Thorup, “Incremental exact min-cut in polylogarithmic amortized update time,” ACM Transactions on Algorithms, vol. 14, no. 2. Association for Computing Machinery, 2018.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2018 | Published | Journal Article | IST-REx-ID: 11667 |
P. Dütting, M. H. Henzinger, and M. Starnberger, “Valuation compressions in VCG-based combinatorial auctions,” ACM Transactions on Economics and Computation, vol. 6, no. 2. Association for Computing Machinery, 2018.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2018 | Published | Journal Article | IST-REx-ID: 11757 |
S. Bhattacharya, M. H. Henzinger, and G. Italiano, “Dynamic algorithms via the primal-dual method,” Information and Computation, vol. 261, no. 08. Elsevier, pp. 219–239, 2018.
[Published Version]
View
| DOI
| Download Published Version (ext.)
2018 | Published | Journal Article | IST-REx-ID: 11768 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Decremental single-source shortest paths on undirected graphs in near-linear total update time,” Journal of the ACM, vol. 65, no. 6. Association for Computing Machinery, pp. 1–40, 2018.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2018 | Published | Conference Paper | IST-REx-ID: 11827 |
G. Goranci, M. H. Henzinger, and D. Leniowski, “A tree structure for dynamic facility location,” in 26th Annual European Symposium on Algorithms, Helsinki, Finland, 2018, vol. 112.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2018 | Published | Conference Paper | IST-REx-ID: 11828 |
G. Goranci, M. H. Henzinger, and P. Peng, “Dynamic effective resistances and approximate schur complement on separable graphs,” in 26th Annual European Symposium on Algorithms, Helsinki, Finland, 2018, vol. 112.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2018 | Published | Conference Paper | IST-REx-ID: 11872 |
S. Bhattacharya, D. Chakrabarty, M. H. Henzinger, and D. Nanongkai, “Dynamic algorithms for graph coloring,” in 29th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, United States, 2018, pp. 1–20.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2018 | Published | Conference Paper | IST-REx-ID: 11882 |
M. H. Henzinger, A. Noe, C. Schulz, and D. Strash, “Practical minimum cut algorithms,” in 20th Workshop on Algorithm Engineering and Experiments, New Orleans, LA, United States, 2018, pp. 48–61.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2018 | Published | Journal Article | IST-REx-ID: 11890 |
S. Bhattacharya, M. H. Henzinger, and G. F. Italiano, “Deterministic fully dynamic data structures for vertex cover and matching,” SIAM Journal on Computing, vol. 47, no. 3. Society for Industrial & Applied Mathematics, pp. 859–887, 2018.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2018 | Published | Conference Paper | IST-REx-ID: 11911 |
S. Biedermann, M. H. Henzinger, C. Schulz, and B. Schuster, “Memetic graph clustering,” in 17th International Symposium on Experimental Algorithms, L’Aquila, Italy, 2018, vol. 103.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2018 | Published | Conference Paper | IST-REx-ID: 141 |
K. Chatterjee, M. H. Henzinger, V. Loitzenbauer, S. Oraee, and V. Toman, “Symbolic algorithms for graphs and Markov decision processes with fairness objectives,” presented at the CAV: Computer Aided Verification, Oxford, United Kingdom, 2018, vol. 10982, pp. 178–197.
[Published Version]
View
| Files available
| DOI
| WoS
2018 | Published | Conference Paper | IST-REx-ID: 10883 |
K. Chatterjee, W. Dvořák, M. H. Henzinger, and A. Svozil, “Quasipolynomial set-based symbolic algorithms for parity games,” in 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, Awassa, Ethiopia, 2018, vol. 57, pp. 233–253.
[Published Version]
View
| Files available
| DOI
| arXiv
2017 | Published | Journal Article | IST-REx-ID: 464 |
K. Chatterjee, M. H. Henzinger, and V. Loitzenbauer, “Improved algorithms for parity and Streett objectives,” Logical Methods in Computer Science, vol. 13, no. 3. International Federation of Computational Logic, 2017.
[Published Version]
View
| Files available
| DOI
| arXiv
2017 | Published | Conference Paper | IST-REx-ID: 552 |
K. Chatterjee, M. H. Henzinger, and A. Svozil, “Faster algorithms for mean-payoff parity games,” in Leibniz International Proceedings in Informatics, Aalborg, Denmark, 2017, vol. 83.
[Published Version]
View
| Files available
| DOI
2017 | Published | Conference Paper | IST-REx-ID: 12571 |
S. Bhattacharya, D. Chakrabarty, and M. H. Henzinger, “Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time,” in 19th International Conference on Integer Programming and Combinatorial Optimization, Waterloo, ON, Canada, 2017, vol. 10328, pp. 86–98.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2017 | Published | Conference Paper | IST-REx-ID: 11651 |
D. Wang, K. Fountoulakis, M. H. Henzinger, M. W. Mahoney, and Satish Rao , “Capacity releasing diffusion for speed and locality,” in Proceedings of the 34th International Conference on Machine Learning, Sydney, Australia, 2017, vol. 70, pp. 3598–3607.
[Published Version]
View
| Download Published Version (ext.)
| arXiv
2017 | Published | Journal Article | IST-REx-ID: 11665 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks,” ACM Transactions on Algorithms, vol. 13, no. 4. Association for Computing Machinery, 2017.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2017 | Published | Journal Article | IST-REx-ID: 11676 |
W. Dvořák, M. H. Henzinger, and D. P. Williamson, “Maximizing a submodular function with viability constraints,” Algorithmica, vol. 77, no. 1. Springer Nature, pp. 152–172, 2017.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2017 | Published | Conference Paper | IST-REx-ID: 11829 |
M. H. Henzinger, A. Lincoln, S. Neumann, and V. Vassilevska Williams, “Conditional hardness for sensitivity problems,” in 8th Innovations in Theoretical Computer Science Conference, Berkley, CA, United States, 2017, vol. 67.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2017 | Published | Conference Paper | IST-REx-ID: 11831 |
G. Goranci, M. H. Henzinger, and P. Peng, “Improved guarantees for vertex sparsification in planar graphs,” in 25th Annual European Symposium on Algorithms, Vienna, Austria, 2017, vol. 87.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
| arXiv
2017 | Published | Conference Paper | IST-REx-ID: 11832 |
M. H. Henzinger, D. Leniowski, and C. Mathieu, “Dynamic clustering to minimize the sum of radii,” in 25th Annual European Symposium on Algorithms, Vienna, Austria, 2017, vol. 87.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2017 | Published | Conference Paper | IST-REx-ID: 11833 |
G. Goranci, M. H. Henzinger, and P. Peng, “The power of vertex sparsifiers in dynamic graph algorithms,” in 25th Annual European Symposium on Algorithms, Vienna, Austria, 2017, vol. 87.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2017 | Published | Conference Paper | IST-REx-ID: 11873 |
M. H. Henzinger, S. Rao, and D. Wang, “Local flow partitioning for faster edge connectivity,” in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 2017, pp. 1919–1938.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2017 | Published | Conference Paper | IST-REx-ID: 11874 |
S. Bhattacharya, M. H. Henzinger, and D. Nanongkai, “Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time,” in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 2017, vol. 0, pp. 470–489.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2017 | Published | Journal Article | IST-REx-ID: 11903 |
S. Bhattacharya, W. Dvořák, M. H. Henzinger, and M. Starnberger, “Welfare maximization with friends-of-friends network externalities,” Theory of Computing Systems, vol. 61, no. 4. Springer Nature, pp. 948–986, 2017.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
2017 | Published | Conference Paper | IST-REx-ID: 6519 |
K. Chatterjee, W. Dvorák, M. H. Henzinger, and V. Loitzenbauer, “Improved set-based symbolic algorithms for parity games,” presented at the CSL: Conference on Computer Science Logic, Stockholm, Sweden, 2017, vol. 82.
[Published Version]
View
| Files available
| DOI
2016 | Published | Conference Paper | IST-REx-ID: 1140 |
K. Chatterjee, W. Dvoák, M. H. Henzinger, and V. Loitzenbauer, “Model and objective separation with conditional lower bounds: disjunction is harder than conjunction,” in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, New York, NY, USA, 2016, pp. 197–206.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2016 | Published | Conference Paper | IST-REx-ID: 11834 |
G. Goranci, M. H. Henzinger, and M. Thorup, “Incremental exact min-cut in poly-logarithmic amortized update time,” in 24th Annual European Symposium on Algorithms, Aarhus, Denmark, 2016, vol. 57.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2016 | Published | Conference Paper | IST-REx-ID: 11835 |
M. H. Henzinger and S. Neumann, “Incremental and fully dynamic subgraph connectivity for emergency planning,” in 24th Annual European Symposium on Algorithms, Aarhus, Denmark, 2016, vol. 57.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2016 | Published | Conference Paper | IST-REx-ID: 11836 |
Y. K. Cheung, G. Goranci, and M. H. Henzinger, “Graph minors for preserving terminal distances approximately - lower and upper bounds,” in 43rd International Colloquium on Automata, Languages, and Programming, Rome, Italy, 2016, vol. 55.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2016 | Published | Conference Paper | IST-REx-ID: 11866 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “A deterministic almost-tight distributed algorithm for approximating single-source shortest paths,” in 48th Annual ACM SIGACT Symposium on Theory of Computing, Cambridge, MA, United States, 2016, pp. 489–498.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2016 | Published | Conference Paper | IST-REx-ID: 11867 |
S. Bhattacharya, M. H. Henzinger, and D. Nanongkai, “New deterministic approximation algorithms for fully dynamic matching,” in 48th Annual ACM SIGACT Symposium on Theory of Computing, Cambridge, MA, United States, 2016, pp. 398–411.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2016 | Published | Journal Article | IST-REx-ID: 11891 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization,” SIAM Journal on Computing, vol. 45, no. 3. Society for Industrial & Applied Mathematics, pp. 947–1006, 2016.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2016 | Published | Conference Paper | IST-REx-ID: 1068 |
K. Chatterjee, W. Dvorák, M. H. Henzinger, and V. Loitzenbauer, “Conditionally optimal algorithms for generalized Büchi Games,” presented at the MFCS: Mathematical Foundations of Computer Science (SG), Krakow, Poland, 2016, vol. 58.
[Published Version]
View
| Files available
| DOI
2015 | Published | Journal Article | IST-REx-ID: 11668 |
R. Colini-Baldeschi, S. Leonardi, M. H. Henzinger, and M. Starnberger, “On multiple keyword sponsored search auctions with budgets,” ACM Transactions on Economics and Computation, vol. 4, no. 1. Association for Computing Machinery, 2015.
[Submitted Version]
View
| DOI
| Download Submitted Version (ext.)
2015 | Published | Journal Article | IST-REx-ID: 11669 |
P. Dütting, M. H. Henzinger, and M. Starnberger, “Auctions for heterogeneous items and budget limits,” ACM Transactions on Economics and Computation, vol. 4, no. 1. Association for Computing Machinery, 2015.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Published | Conference Paper | IST-REx-ID: 11773 |
O. Ben-Zwi, M. H. Henzinger, and V. Loitzenbauer, “Ad exchange: Envy-free auctions with mediators,” in 11th International Conference on Web and Internet Economics, Amsterdam, Netherlands, 2015, vol. 9470, pp. 104–117.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Published | Conference Paper | IST-REx-ID: 11774 |
Y. K. Cheung, M. H. Henzinger, M. Hoefer, and M. Starnberger, “Combinatorial auctions with conflict-based externalities,” in 11th International Conference on Web and Internet Economics, Amsterdam, Netherlands, 2015, vol. 9470, pp. 230–243.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Published | Conference Paper | IST-REx-ID: 11785 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Improved algorithms for decremental single-source reachability on directed graphs,” in 42nd International Colloquium on Automata, Languages and Programming, Kyoto, Japan, 2015, vol. 9134, pp. 725–736.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Published | Conference Paper | IST-REx-ID: 11786 |
S. Bhattacharya, M. H. Henzinger, and G. F. Italiano, “Design of dynamic algorithms via primal-dual method,” in 42nd International Colloquium on Automata, Languages and Programming, Kyoto, Japan, 2015, vol. 9134, pp. 206–218.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Published | Conference Paper | IST-REx-ID: 11787 |
M. H. Henzinger, S. Krinninger, and V. Loitzenbauer, “Finding 2-edge and 2-vertex strongly connected components in quadratic time,” in 2nd International Colloquium on Automata, Languages and Programming, Kyoto, Japan, 2015, vol. 9134, pp. 713–724.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Published | Conference Paper | IST-REx-ID: 11788 |
W. Dvořák and M. H. Henzinger, “Online ad assignment with an ad exchange,” in 12th International Workshop of Approximation and Online Algorithms, Wroclaw, Poland, 2015, vol. 8952, pp. 156–167.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Published | Conference Paper | IST-REx-ID: 11837 |
S. Bhattacharya, W. Dvorák, M. H. Henzinger, and Martin Starnberger, “Welfare maximization with friends-of-friends network externalities,” in 32nd International Symposium on Theoretical Aspects of Computer Science, Garching, Germany, 2015, vol. 30, pp. 90–102.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
2015 | Published | Journal Article | IST-REx-ID: 11845 |
O. Chernomor et al., “Split diversity in constrained conservation prioritization using integer linear programming,” Methods in Ecology and Evolution, vol. 6, no. 1. Wiley, pp. 83–91, 2015.
[Published Version]
View
| Files available
| DOI
| PubMed | Europe PMC
2015 | Published | Conference Paper | IST-REx-ID: 11868 |
M. H. Henzinger, S. Krinninger, D. Nanongkai, and T. Saranurak, “Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture,” in 47th Annual ACM Symposium on Theory of Computing, Portland, OR, United States, 2015.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Published | Conference Paper | IST-REx-ID: 11869 |
S. Bhattacharya, M. H. Henzinger, D. Nanongkai, and C. Tsourakakis, “Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams,” in 47th Annual ACM Symposium on Theory of Computing, Portland, OR, United States, 2015, pp. 173–182.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Published | Journal Article | IST-REx-ID: 11901 |
M. H. Henzinger and V. Loitzenbauer, “Truthful unit-demand auctions with budgets revisited,” Theoretical Computer Science, vol. 573. Elsevier, pp. 1–15, 2015.
View
| DOI
| Download None (ext.)
2015 | Published | Conference Paper | IST-REx-ID: 1661 |
K. Chatterjee, M. H. Henzinger, and V. Loitzenbauer, “Improved algorithms for one-pair and k-pair Streett objectives,” in Proceedings - Symposium on Logic in Computer Science, Kyoto, Japan, 2015, vol. 2015–July.
[Submitted Version]
View
| Files available
| DOI
| Download Submitted Version (ext.)
2014 | Published | Journal Article | IST-REx-ID: 535 |
K. Chatterjee, M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Polynomial-time algorithms for energy games with special weight structures,” Algorithmica, vol. 70, no. 3. Springer, pp. 457–492, 2014.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2014 | Published | Journal Article | IST-REx-ID: 1375 |
K. Chatterjee, M. H. Henzinger, S. Krinninger, V. Loitzenbauer, and M. Raskin, “Approximating the minimum cycle mean,” Theoretical Computer Science, vol. 547, no. C. Elsevier, pp. 104–116, 2014.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2014 | Published | Conference Paper | IST-REx-ID: 11789 |
M. Charikar, M. H. Henzinger, and H. L. Nguyễn, “Online bipartite matching with decomposable weights,” in 22nd Annual European Symposium on Algorithms, Wroclaw, Poland, 2014, vol. 8737, pp. 260–271.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2014 | Published | Conference Paper | IST-REx-ID: 11790
L. Cigler, W. Dvořák, M. H. Henzinger, and M. Starnberger, “Limiting price discrimination when selling products with positive network externalities,” in 10th International Conference of Web and Internet Economics, Beijing, China, 2014, vol. 8877, pp. 44–57.
View
| DOI
2014 | Published | Conference Paper | IST-REx-ID: 11855 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Decremental single-source shortest paths on undirected graphs in near-linear total update time,” in 55th Annual Symposium on Foundations of Computer Science, Philadelphia, PA, United States, 2014, pp. 146–155.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2014 | Published | Conference Paper | IST-REx-ID: 11870 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs,” in 46th Annual ACM Symposium on Theory of Computing, New York, NY, United States, 2014.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2014 | Published | Conference Paper | IST-REx-ID: 11875 |
S. Bhattacharya, M. H. Henzinger, and G. F. Italiano, “Deterministic fully dynamic data structures for vertex cover and matching,” in 26th Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, United States, 2014, pp. 785–804.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2014 | Published | Conference Paper | IST-REx-ID: 11876 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “A subquadratic-time algorithm for decremental single-source shortest paths,” in 25th Annual ACM-SIAM Symposium on Discrete Algorithms, Portland, OR, United States, 2014, pp. 1053–1072.
[Published Version]
View
| DOI
| Download Published Version (ext.)
2014 | Published | Journal Article | IST-REx-ID: 2141 |
K. Chatterjee and M. H. Henzinger, “Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition,” Journal of the ACM, vol. 61, no. 3. ACM, 2014.
[Submitted Version]
View
| Files available
| DOI
| Download Submitted Version (ext.)
2013 | Published | Journal Article | IST-REx-ID: 2831 |
K. Chatterjee, M. H. Henzinger, M. Joglekar, and N. Shah, “Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives,” Formal Methods in System Design, vol. 42, no. 3. Springer, pp. 301–327, 2013.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2013 | Published | Journal Article | IST-REx-ID: 11759 |
P. Dütting, M. H. Henzinger, and I. Weber, “Sponsored search, market equilibria, and the Hungarian Method,” Information Processing Letters, vol. 113, no. 3. Elsevier, pp. 67–73, 2013.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2013 | Published | Conference Paper | IST-REx-ID: 11791 |
P. Dütting, M. H. Henzinger, and M. Starnberger, “Valuation compressions in VCG-based combinatorial auctions,” in 9th International Conference on Web and Internet Economics, Cambridge, MA, USA, 2013, vol. 8289, pp. 146–159.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2013 | Published | Conference Paper | IST-REx-ID: 11792 |
W. Dvořák, M. H. Henzinger, and D. P. Williamson, “Maximizing a submodular function with viability constraints,” in 21st Annual European Symposium on Algorithms, Sophia Antipolis, France, 2013, vol. 8125, pp. 409–420.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2013 | Published | Conference Paper | IST-REx-ID: 11793 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks,” in 40th International Colloquium on Automata, Languages, and Programming, Riga, Latvia, 2013, vol. 7966, pp. 607–619.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2013 | Published | Conference Paper | IST-REx-ID: 11856 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization,” in 54th Annual Symposium on Foundations of Computer Science, Berkeley, CA, United States, 2013, pp. 538–547.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2013 | Published | Journal Article | IST-REx-ID: 11902
P. Dütting, M. H. Henzinger, and I. Weber, “Bidder optimal assignments for general utilities,” Theoretical Computer Science, vol. 478, no. 3. Elsevier, pp. 22–32, 2013.
View
| Files available
| DOI
2012 | Published | Conference Paper | IST-REx-ID: 3165 |
K. Chatterjee and M. H. Henzinger, “An O(n2) time algorithm for alternating Büchi games,” in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Kyoto, Japan, 2012, pp. 1386–1399.
View
| Files available
| DOI
| Download None (ext.)
| arXiv
2012 | Published | Conference Paper | IST-REx-ID: 11656
P. Dütting, M. H. Henzinger, and I. Weber, “Maximizing revenue from strategic recommendations under decaying trust,” in Proceedings of the 21st ACM international conference on Information and knowledge management, Maui, HI, United States, 2012, pp. 2268–2286.
View
| DOI
2012 | Published | Conference Paper | IST-REx-ID: 11794 |
P. Dütting, M. H. Henzinger, and M. Starnberger, “Auctions with heterogeneous items and budget limits,” in 8th International Workshop on Internet and Network Economics, Liverpool, United Kingdom, 2012, vol. 7695, pp. 44–57.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2012 | Published | Conference Paper | IST-REx-ID: 11795
R. Colini-Baldeschi, M. H. Henzinger, S. Leonardi, and M. Starnberger, “On multiple keyword sponsored search auctions with budgets,” in 39th International Colloquium on Automata, Languages, and Programming, Warwick, United Kingdom, 2012, vol. 7392, pp. 1–12.
View
| Files available
| DOI
2012 | Published | Conference Paper | IST-REx-ID: 10905 |
K. Chatterjee, M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Polynomial-time algorithms for energy games with special weight structures,” in Algorithms – ESA 2012, Ljubljana, Slovenia, 2012, vol. 7501, pp. 301–312.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2011 | Published | Conference Paper | IST-REx-ID: 3342 |
K. Chatterjee, M. H. Henzinger, M. Joglekar, and S. Nisarg, “Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives,” presented at the CAV: Computer Aided Verification, Snowbird, USA, 2011, vol. 6806, pp. 260–276.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2011 | Published | Conference Paper | IST-REx-ID: 3343 |
K. Chatterjee and M. H. Henzinger, “Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification,” presented at the SODA: Symposium on Discrete Algorithms, San Francisco, SA, United States, 2011, pp. 1318–1336.
[Submitted Version]
View
| DOI
| Download Submitted Version (ext.)
2011 | Published | Technical Report | IST-REx-ID: 5379 |
K. Chatterjee and M. H. Henzinger, An O(n2) time algorithm for alternating Büchi games. IST Austria, 2011.
[Published Version]
View
| Files available
| DOI
2010 | Published | Conference Paper | IST-REx-ID: 11797 |
J. Feldman, M. H. Henzinger, N. Korula, V. S. Mirrokni, and C. Stein, “Online stochastic packing applied to display ad allocation,” in 18th Annual European Symposium on Algorithms, Liverpool, United Kingdom, 2010, vol. 6346, pp. 182–194.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2010 | Published | Conference Paper | IST-REx-ID: 11838 |
P. Dütting, M. H. Henzinger, and I. Weber, “Sponsored search, market equilibria, and the Hungarian Method,” in 27th International Symposium on Theoretical Aspects of Computer Science, Nancy, France, 2010, vol. 5, pp. 287–298.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
| arXiv
2009 | Published | Conference Paper | IST-REx-ID: 11799
P. Dütting, M. H. Henzinger, and I. Weber, “Bidder optimal assignments for general utilities,” in 5th International Workshop on Internet and Network Economics, Rome, Italy, 2009, vol. 5929, pp. 575–582.
View
| Files available
| DOI
2009 | Published | Conference Paper | IST-REx-ID: 11912 |
Eda Baykan, M. H. Henzinger, S. F. Keller, S. de Castelberg, and M. Kinzler, “A comparison of techniques for sampling web pages,” in 26th International Symposium on Theoretical Aspects of Computer Science, Freiburg, Germany, 2009, vol. 3, pp. 13–30.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2007 | Published | Journal Article | IST-REx-ID: 11884
M. H. Henzinger, “Search technologies for the internet,” Science, vol. 317, no. 5837. American Association for the Advancement of Science, pp. 468–471, 2007.
View
| DOI
| PubMed | Europe PMC
2007 | Published | Conference Paper | IST-REx-ID: 11924
M. H. Henzinger, “Combinatorial algorithms for web search engines: three success stories,” in 18th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, United States, 2007, pp. 1022–1026.
View
2006 | Published | Conference Paper | IST-REx-ID: 11929
M. H. Henzinger, “Finding near-duplicate web pages: A large-scale evaluation of algorithms,” in 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Seattle, WA, United States, 2006, pp. 284–291.
View
| DOI
2005 | Published | Journal Article | IST-REx-ID: 11763 |
A. Goel, M. H. Henzinger, and S. Plotkin, “An online throughput-competitive algorithm for multicast routing and admission control,” Journal of Algorithms, vol. 55, no. 1. Elsevier, pp. 1–20, 2005.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
2005 | Published | Journal Article | IST-REx-ID: 11904
M. H. Henzinger, B.-W. Chang, B. Milch, and S. Brin, “Query-free news search,” World Wide Web, vol. 8, no. 2. Springer Nature, pp. 101–126, 2005.
View
| Files available
| DOI
2004 | Published | Journal Article | IST-REx-ID: 11762 |
M. H. Henzinger, “Algorithmic challenges in web search engines,” Internet Mathematics, vol. 1, no. 1. Internet Mathematics, pp. 115–123, 2004.
[Published Version]
View
| DOI
| Download Published Version (ext.)
2004 | Published | Journal Article | IST-REx-ID: 11877 |
M. H. Henzinger and S. Lawrence, “Extracting knowledge from the World Wide Web,” Proceedings of the National Academy of Sciences, vol. 101, no. suppl_1. Proceedings of the National Academy of Sciences, pp. 5186–5191, 2004.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| PubMed | Europe PMC
2003 | Published | Journal Article | IST-REx-ID: 11766 |
M. H. Henzinger and S. Leonardi, “Scheduling multicasts on unit-capacity trees and meshes,” Journal of Computer and System Sciences, vol. 66, no. 3. Elsevier, pp. 567–611, 2003.
[Published Version]
View
| DOI
| Download Published Version (ext.)
2003 | Published | Conference Paper | IST-REx-ID: 11860
M. H. Henzinger, B.-W. Chang, B. Milch, and S. Brin, “Query-free news search,” in Proceedings of the 12th international conference on World Wide Web, Budapest, Hungary, 2003.
View
| Files available
| DOI
2003 | Published | Conference Paper | IST-REx-ID: 11897
K. Bharat and M. H. Henzinger, “Improved algorithms for topic distillation in a hyperlinked environment,” in 21st annual international ACM SIGIR conference on Research and development in information retrieval, Melbourne, Australia, 2003, pp. 104–111.
View
| DOI
2003 | Published | Conference Paper | IST-REx-ID: 11909 |
M. H. Henzinger, R. Motwani, and C. Silverstein, “Challenges in web search engines,” in 18th International Joint Conference on Artificial Intelligence, Acapulco, Mexico, 2003, pp. 1573–1579.
[Published Version]
View
| Download Published Version (ext.)
2000 | Published | Journal Article | IST-REx-ID: 11770 |
K. Bharat, A. Broder, J. Dean, and M. H. Henzinger, “A comparison of techniques to find mirrored hosts on the WWW,” Journal of the American Society for Information Science, vol. 51, no. 12. Wiley, pp. 1114–1122, 2000.
[Published Version]
View
| DOI
| Download Published Version (ext.)
1999 | Published | Journal Article | IST-REx-ID: 11679
M. H. Henzinger, V. King, and T. Warnow, “Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology,” Algorithmica, vol. 24. Springer Nature, pp. 1–13, 1999.
View
| Files available
| DOI
1999 | Published | Conference Paper | IST-REx-ID: 11691
A. Goel, M. H. Henzinger, S. Plotkin, and E. Tardos, “Scheduling data transfers in a network and the set scheduling problem,” in Proceedings of the 31st annual ACM symposium on Theory of computing, Atlanta, GA, United States, 1999, pp. 189–197.
View
| DOI
1999 | Published | Journal Article | IST-REx-ID: 11895 |
C. Silverstein, H. Marais, M. H. Henzinger, and M. Moricz, “Analysis of a very large web search engine query log,” ACM SIGIR Forum, vol. 33, no. 1. Association for Computing Machinery, pp. 6–12, 1999.
[Published Version]
View
| DOI
| Download Published Version (ext.)
1999 | Published | Conference Paper | IST-REx-ID: 11925
M. H. Henzinger and S. Leonardi , “Scheduling multicasts on unit-capacity trees and meshes,” in 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, United States, 1999, pp. 438–447.
View
1998 | Published | Journal Article | IST-REx-ID: 11680
D. Alberts and M. H. Henzinger, “Average-case analysis of dynamic graph algorithms,” Algorithmica, vol. 20. Springer Nature, pp. 31–60, 1998.
View
| Files available
| DOI
1998 | Published | Conference Paper | IST-REx-ID: 11682
P. K. Agarwal, D. EppsteinL. J. Guibas, and M. H. Henzinger, “Parametric and kinetic minimum spanning trees,” in Proceedings of the 39th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, United States, 1998, pp. 596–605.
View
| DOI
1998 | Published | Conference Paper | IST-REx-ID: 11926
A. Goel, M. H. Henzinger, and S. Plotkin, “An online throughput-competitive algorithm for multicast routing and admission control,” in 9th Annual ACM SIAM Symposium on Discrete Algorithms, San Francisco, CA, United States, 1998, pp. 97–106.
View
| Files available
1997 | Published | Journal Article | IST-REx-ID: 11767 |
M. H. Henzinger, P. Klein, S. Rao, and S. Subramanian, “Faster shortest-path algorithms for planar graphs,” Journal of Computer and System Sciences, vol. 55, no. 1. Elsevier, pp. 3–23, 1997.
[Published Version]
View
| DOI
| Download Published Version (ext.)
1997 | Published | Journal Article | IST-REx-ID: 11849 |
J. M. Anderson et al., “Continuous profiling: Where have all the cycles gone?,” ACM SIGOPS Operating Systems Review, vol. 31, no. 5. Association for Computing Machinery, pp. 1–14, 1997.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
1996 | Published | Conference Paper | IST-REx-ID: 11927 |
M. H. Henzinger, V. King, and T. Warnow, “Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology,” in 7th Annual ACM-SIAM Symposium on Discrete Algorithms, Atlanta, GA, United States, 1996, pp. 333–340.
[Published Version]
View
| Files available
| Download Published Version (ext.)
1995 | Published | Conference Paper | IST-REx-ID: 11928 |
D. Alberts and M. H. Henzinger, “Average case analysis of dynamic graph algorithms,” in 6th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, United States, 1995, pp. 312–321.
[Published Version]
View
| Files available
| Download Published Version (ext.)
Grants
196 Publications
2024 | Published | Conference Paper | IST-REx-ID: 14769 |
M. H. Henzinger, D. Saulpic, and L. Sidl, “Experimental evaluation of fully dynamic k-means via coresets,” in 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments, Alexandria, VA, United States, 2024, pp. 220–233.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 15008 |
G. Goranci, M. H. Henzinger, H. Räcke, S. Sachdeva, and A. R. Sricharan, “Electrical flows for polylogarithmic competitive oblivious routing,” in 15th Innovations in Theoretical Computer Science Conference, Berkeley, CA, United States, 2024, vol. 287.
[Published Version]
View
| Files available
| DOI
| arXiv
2023 | Published | Conference Paper | IST-REx-ID: 12760 |
M. H. Henzinger, S. Neumann, H. Räcke, and S. Schmid, “Dynamic maintenance of monotone dynamic programs and applications,” in 40th International Symposium on Theoretical Aspects of Computer Science, Hamburg, Germany, 2023, vol. 254.
[Published Version]
View
| Files available
| DOI
| arXiv
2023 | Published | Conference Paper | IST-REx-ID: 13236 |
D. W. Zheng and M. H. Henzinger, “Multiplicative auction algorithm for approximate maximum weight bipartite matching,” in International Conference on Integer Programming and Combinatorial Optimization, Madison, WI, United States, 2023, vol. 13904, pp. 453–465.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2023 | Published | Journal Article | IST-REx-ID: 14043 |
M. H. Henzinger, B. Jin, R. Peng, and D. P. Williamson, “A combinatorial cut-toggling algorithm for solving Laplacian linear systems,” Algorithmica, vol. 85. Springer Nature, pp. 2680–3716, 2023.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| WoS
| arXiv
2023 | Published | Conference Paper | IST-REx-ID: 14085 |
G. Goranci and M. H. Henzinger, “Efficient data structures for incremental exact and approximate maximum flow,” in 50th International Colloquium on Automata, Languages, and Programming, Paderborn, Germany, 2023, vol. 261.
[Published Version]
View
| Files available
| DOI
2023 | Published | Conference Paper | IST-REx-ID: 14086 |
M. H. Henzinger, P. Liu, J. Vondrák, and D. W. Zheng, “Faster submodular maximization for several classes of matroids,” in 50th International Colloquium on Automata, Languages, and Programming, Paderborn, Germany, 2023, vol. 261.
[Published Version]
View
| Files available
| DOI
| arXiv
2023 | Published | Conference Paper | IST-REx-ID: 14462 |
H. Fichtenberger, M. H. Henzinger, and J. Upadhyay, “Constant matters: Fine-grained error bound on differentially private continual observation,” in Proceedings of the 40th International Conference on Machine Learning, Honolulu, Hawaii, HI, United States, 2023, vol. 202, pp. 10072–10092.
[Published Version]
View
| Download Published Version (ext.)
2023 | Published | Journal Article | IST-REx-ID: 14558
S. Bhattacharya, M. H. Henzinger, D. Nanongkai, and X. Wu, “Deterministic near-optimal approximation algorithms for dynamic set cover,” SIAM Journal on Computing, vol. 52, no. 5. Society for Industrial and Applied Mathematics, pp. 1132–1192, 2023.
View
| DOI
2022 | Published | Conference Paper | IST-REx-ID: 11808 |
K. Hanauer, M. H. Henzinger, and C. Schulz, “Recent advances in fully dynamic graph algorithms,” in 1st Symposium on Algorithmic Foundations of Dynamic Networks, Virtual, 2022, vol. 221.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2022 | Published | Conference Paper | IST-REx-ID: 11812 |
K. Hanauer, M. H. Henzinger, and Q. C. Hua, “Fully dynamic four-vertex subgraph counting,” in 1st Symposium on Algorithmic Foundations of Dynamic Networks, Virtual, 2022, vol. 221.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2022 | Published | Conference Paper | IST-REx-ID: 11930 |
M. H. Henzinger, A. Noe, and C. Schulz, “Practical fully dynamic minimum cut algorithms,” in 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments, Alexandria, VA, United States, 2022, pp. 13–26.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2022 | Submitted | Preprint | IST-REx-ID: 14236 |
G. Goranci and M. H. Henzinger, “Incremental approximate maximum flow in m1/2+o(1) update time,” arXiv. .
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2021 | Published | Conference Paper | IST-REx-ID: 11649 |
M. H. Henzinger, A. Paz, and S. Schmid, “On the complexity of weight-dynamic network algorithms,” in IFIP Networking Conference, Espoo and Helsinki, Finland, 2021.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2021 | Published | Journal Article | IST-REx-ID: 11663 |
A. Bernstein, S. Forster, and M. H. Henzinger, “A deamortization approach for dynamic spanner and dynamic maximal matching,” ACM Transactions on Algorithms, vol. 17, no. 4. Association for Computing Machinery, 2021.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2021 | Published | Journal Article | IST-REx-ID: 11756 |
M. H. Henzinger and P. Peng, “Constant-time dynamic weight approximation for minimum spanning forest,” Information and Computation, vol. 281, no. 12. Elsevier, 2021.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2021 | Published | Conference Paper | IST-REx-ID: 11771 |
M. H. Henzinger and X. Wu, “Upper and lower bounds for fully retroactive graph problems,” in 17th International Symposium on Algorithms and Data Structures, Virtual, 2021, vol. 12808, pp. 471–484.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2021 | Published | Conference Paper | IST-REx-ID: 11814 |
H. Fichtenberger, M. H. Henzinger, and W. Ost, “Differentially private algorithms for graphs under continual observation,” in 29th Annual European Symposium on Algorithms, Lisbon, Portual, 2021, vol. 204.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2021 | Published | Journal Article | IST-REx-ID: 11886 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “A deterministic almost-tight distributed algorithm for approximating single-source shortest paths,” SIAM Journal on Computing, vol. 50, no. 3. Society for Industrial & Applied Mathematics, pp. STOC16-98-STOC16-137, 2021.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2021 | Published | Conference Paper | IST-REx-ID: 11919 |
T. Bergamaschi, M. H. Henzinger, M. P. Gutenberg, V. V. Williams, and N. Wein, “New techniques and fine-grained hardness for dynamic near-additive spanners,” in 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, VA, United States, 2021, pp. 1836–1855.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2021 | Published | Conference Paper | IST-REx-ID: 11920 |
S. Bhattacharya, M. H. Henzinger, D. Nanongkai, and X. Wu, “Dynamic set cover: Improved amortized and worst-case update time,” in 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, VA, United States, 2021, pp. 2537–2549.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2021 | Published | Conference Paper | IST-REx-ID: 11923 |
M. H. Henzinger, S. Neumann, H. Räcke, and S. Schmid, “Tight bounds for online graph partitioning,” in 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, VA, United States, 2021, pp. 2799–2818.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2021 | Published | Conference Paper | IST-REx-ID: 11931 |
G. Goranci, M. H. Henzinger, D. Leniowski, C. Schulz, and A. Svozil, “Fully dynamic k-center clustering in low dimensional metrics,” in 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments, Alexandria, VA, United States, 2021, pp. 143–153.
[Published Version]
View
| DOI
| Download Published Version (ext.)
2021 | Published | Journal Article | IST-REx-ID: 9293 |
K. Chatterjee, W. Dvořák, M. H. Henzinger, and A. Svozil, “Algorithms and conditional lower bounds for planning problems,” Artificial Intelligence, vol. 297, no. 8. Elsevier, 2021.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| WoS
| arXiv
2021 | Published | Conference Paper | IST-REx-ID: 10002 |
K. Chatterjee, W. Dvorak, M. H. Henzinger, and A. Svozil, “Symbolic time and space tradeoffs for probabilistic verification,” in Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, Rome, Italy, 2021, pp. 1–13.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| WoS
| arXiv
2021 | Published | Conference Paper | IST-REx-ID: 10054 |
K. Chatterjee, M. H. Henzinger, S. S. Kale, and A. Svozil, “Faster algorithms for bounded liveness in graphs and game graphs,” in 48th International Colloquium on Automata, Languages, and Programming, Glasgow, Scotland, 2021, vol. 198.
[Published Version]
View
| Files available
| DOI
2020 | Published | Journal Article | IST-REx-ID: 11674 |
M. H. Henzinger, D. Leniowski, and C. Mathieu, “Dynamic clustering to minimize the sum of radii,” Algorithmica, vol. 82, no. 11. Springer Nature, pp. 3183–3194, 2020.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2020 | Published | Journal Article | IST-REx-ID: 11675 |
S. Bhattacharya, D. Chakrabarty, and M. H. Henzinger, “Deterministic dynamic matching in O(1) update time,” Algorithmica, vol. 82, no. 4. Springer Nature, pp. 1057–1080, 2020.
[Published Version]
View
| DOI
| Download Published Version (ext.)
2020 | Published | Conference Paper | IST-REx-ID: 11816 |
M. H. Henzinger, K. Shahbaz, R. Paul, and C. Schulz, “Dynamic matching algorithms in practice,” in 8th Annual European Symposium on Algorithms, Pisa, Italy, 2020, vol. 173.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2020 | Published | Conference Paper | IST-REx-ID: 11818 |
M. H. Henzinger and S. Kale, “Fully-dynamic coresets,” in 28th Annual European Symposium on Algorithms, Pisa, Italy, 2020, vol. 173.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2020 | Published | Conference Paper | IST-REx-ID: 11819 |
M. H. Henzinger, A. Noe, C. Schulz, and D. Strash, “Finding all global minimum cuts in practice,” in 28th Annual European Symposium on Algorithms, Pisa, Italy, 2020, vol. 173.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2020 | Published | Conference Paper | IST-REx-ID: 11822 |
K. Hanauer, M. H. Henzinger, and C. Schulz, “Faster fully dynamic transitive closure in practice,” in 18th International Symposium on Experimental Algorithms, Pisa, Italy, 2020, vol. 160.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2020 | Published | Conference Paper | IST-REx-ID: 11824 |
M. H. Henzinger, S. Neumann, and A. Wiese, “Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles,” in 36th International Symposium on Computational Geometry, Zurich, Switzerland, 2020, vol. 164.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2020 | Published | Conference Paper | IST-REx-ID: 11825 |
M. H. Henzinger and P. Peng, “Constant-time dynamic (Δ+1)-coloring,” in 37th International Symposium on Theoretical Aspects of Computer Science, Montpellier, France, 2020, vol. 154.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2020 | Published | Conference Paper | IST-REx-ID: 11852 |
L. Chen, G. Goranci, M. H. Henzinger, R. Peng, and T. Saranurak, “Fast dynamic cuts, distances and effective resistances via vertex sparsifiers,” in 61st Annual Symposium on Foundations of Computer Science, Durham, NC, United States, 2020, pp. 1135–1146.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2020 | Published | Conference Paper | IST-REx-ID: 11880 |
K. Hanauer, M. H. Henzinger, and C. Schulz, “Fully dynamic single-source reachability in practice: An experimental study,” in 2020 Symposium on Algorithm Engineering and Experiments, Salt Lake City, UT, United States, 2020, pp. 106–119.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2020 | Published | Conference Paper | IST-REx-ID: 11881 |
M. H. Henzinger, A. Noe, and C. Schulz, “Shared-memory branch-and-reduce for multiterminal cuts,” in 2020 Symposium on Algorithm Engineering and Experiments, Salt Lake City, UT, United States, 2020, pp. 42–55.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2020 | Published | Journal Article | IST-REx-ID: 11889
M. H. Henzinger, S. Rao, and D. Wang, “Local flow partitioning for faster edge connectivity,” SIAM Journal on Computing, vol. 49, no. 1. Society for Industrial & Applied Mathematics, pp. 1–36, 2020.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2020 | Published | Journal Article | IST-REx-ID: 11894 |
G. Goranci, M. H. Henzinger, and P. Peng, “Improved guarantees for vertex sparsification in planar graphs,” SIAM Journal on Discrete Mathematics, vol. 34, no. 1. Society for Industrial & Applied Mathematics, pp. 130–162, 2020.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2019 | Published | Conference Paper | IST-REx-ID: 11826 |
B. Ancona, M. H. Henzinger, L. Roditty, V. V. Williams, and N. Wein, “Algorithms and hardness for diameter in dynamic graphs,” in 46th International Colloquium on Automata, Languages, and Programming, Patras, Greece, 2019, vol. 132.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2019 | Published | Book Chapter | IST-REx-ID: 11847
S. Biedermann, M. H. Henzinger, C. Schulz, and B. Schuster, “Vienna Graph Clustering,” in Protein-Protein Interaction Networks, vol. 2074, S. Canzar and F. Rojas Ringeling, Eds. Springer Nature, 2019, pp. 215–231.
View
| DOI
| PubMed | Europe PMC
2019 | Published | Conference Paper | IST-REx-ID: 11850 |
M. H. Henzinger, S. Neumann, and S. Schmid, “Efficient distributed workload (re-)embedding,” in SIGMETRICS’19: International Conference on Measurement and Modeling of Computer Systems, Phoenix, AZ, United States, 2019, pp. 43–44.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2019 | Published | Conference Paper | IST-REx-ID: 11851
M. H. Henzinger, A. Noe, and C. Schulz, “Shared-memory exact minimum cuts,” in 33rd International Parallel and Distributed Processing Symposium, Rio de Janeiro, Brazil, 2019.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2019 | Published | Conference Paper | IST-REx-ID: 11853 |
S. Bhattacharya, M. H. Henzinger, and D. Nanongkai, “A new deterministic algorithm for dynamic set cover,” in 60th Annual Symposium on Foundations of Computer Science, Baltimore, MD, United States, 2019, pp. 406–423.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2019 | Published | Conference Paper | IST-REx-ID: 11865 |
M. Daga, M. H. Henzinger, D. Nanongkai, and T. Saranurak, “Distributed edge connectivity in sublinear time,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Phoenix, AZ, United States, 2019, pp. 343–354.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2019 | Published | Conference Paper | IST-REx-ID: 11871 |
A. Bernstein, S. Forster, and M. H. Henzinger, “A deamortization approach for dynamic spanner and dynamic maximal matching,” in 30th Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, United States, 2019, pp. 1899–1918.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2019 | Published | Journal Article | IST-REx-ID: 11898 |
S. Bhattacharya, M. H. Henzinger, and S. Neumann, “New amortized cell-probe lower bounds for dynamic problems,” Theoretical Computer Science, vol. 779. Elsevier, pp. 72–87, 2019.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2019 | Published | Conference Paper | IST-REx-ID: 6887 |
K. Chatterjee, W. Dvorák, M. H. Henzinger, and A. Svozil, “Near-linear time algorithms for Streett objectives in graphs and MDPs,” in Leibniz International Proceedings in Informatics, Amsterdam, Netherlands, 2019, vol. 140.
[Published Version]
View
| Files available
| DOI
2018 | Published | Conference Paper | IST-REx-ID: 310 |
K. Chatterjee, W. Dvorák, M. H. Henzinger, and V. Loitzenbauer, “Lower bounds for symbolic computation on graphs: Strongly connected components, liveness, safety, and diameter,” presented at the SODA: Symposium on Discrete Algorithms, New Orleans, Louisiana, United States, 2018, pp. 2341–2356.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| WoS
| arXiv
2018 | Published | Conference Paper | IST-REx-ID: 35 |
K. Chatterjee, W. Dvorák, M. H. Henzinger, and A. Svozil, “Algorithms and conditional lower bounds for planning problems,” in 28th International Conference on Automated Planning and Scheduling , Delft, Netherlands, 2018.
View
| Files available
| Download None (ext.)
| WoS
| arXiv
2018 | Published | Journal Article | IST-REx-ID: 11657 |
M. H. Henzinger, A. Noe, C. Schulz, and D. Strash, “Practical minimum cut algorithms,” ACM Journal of Experimental Algorithmics, vol. 23. Association for Computing Machinery, pp. 1–22, 2018.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2018 | Published | Journal Article | IST-REx-ID: 11664 |
G. Goranci, M. H. Henzinger, and M. Thorup, “Incremental exact min-cut in polylogarithmic amortized update time,” ACM Transactions on Algorithms, vol. 14, no. 2. Association for Computing Machinery, 2018.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2018 | Published | Journal Article | IST-REx-ID: 11667 |
P. Dütting, M. H. Henzinger, and M. Starnberger, “Valuation compressions in VCG-based combinatorial auctions,” ACM Transactions on Economics and Computation, vol. 6, no. 2. Association for Computing Machinery, 2018.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2018 | Published | Journal Article | IST-REx-ID: 11757 |
S. Bhattacharya, M. H. Henzinger, and G. Italiano, “Dynamic algorithms via the primal-dual method,” Information and Computation, vol. 261, no. 08. Elsevier, pp. 219–239, 2018.
[Published Version]
View
| DOI
| Download Published Version (ext.)
2018 | Published | Journal Article | IST-REx-ID: 11768 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Decremental single-source shortest paths on undirected graphs in near-linear total update time,” Journal of the ACM, vol. 65, no. 6. Association for Computing Machinery, pp. 1–40, 2018.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2018 | Published | Conference Paper | IST-REx-ID: 11827 |
G. Goranci, M. H. Henzinger, and D. Leniowski, “A tree structure for dynamic facility location,” in 26th Annual European Symposium on Algorithms, Helsinki, Finland, 2018, vol. 112.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2018 | Published | Conference Paper | IST-REx-ID: 11828 |
G. Goranci, M. H. Henzinger, and P. Peng, “Dynamic effective resistances and approximate schur complement on separable graphs,” in 26th Annual European Symposium on Algorithms, Helsinki, Finland, 2018, vol. 112.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2018 | Published | Conference Paper | IST-REx-ID: 11872 |
S. Bhattacharya, D. Chakrabarty, M. H. Henzinger, and D. Nanongkai, “Dynamic algorithms for graph coloring,” in 29th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, United States, 2018, pp. 1–20.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2018 | Published | Conference Paper | IST-REx-ID: 11882 |
M. H. Henzinger, A. Noe, C. Schulz, and D. Strash, “Practical minimum cut algorithms,” in 20th Workshop on Algorithm Engineering and Experiments, New Orleans, LA, United States, 2018, pp. 48–61.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2018 | Published | Journal Article | IST-REx-ID: 11890 |
S. Bhattacharya, M. H. Henzinger, and G. F. Italiano, “Deterministic fully dynamic data structures for vertex cover and matching,” SIAM Journal on Computing, vol. 47, no. 3. Society for Industrial & Applied Mathematics, pp. 859–887, 2018.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2018 | Published | Conference Paper | IST-REx-ID: 11911 |
S. Biedermann, M. H. Henzinger, C. Schulz, and B. Schuster, “Memetic graph clustering,” in 17th International Symposium on Experimental Algorithms, L’Aquila, Italy, 2018, vol. 103.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2018 | Published | Conference Paper | IST-REx-ID: 141 |
K. Chatterjee, M. H. Henzinger, V. Loitzenbauer, S. Oraee, and V. Toman, “Symbolic algorithms for graphs and Markov decision processes with fairness objectives,” presented at the CAV: Computer Aided Verification, Oxford, United Kingdom, 2018, vol. 10982, pp. 178–197.
[Published Version]
View
| Files available
| DOI
| WoS
2018 | Published | Conference Paper | IST-REx-ID: 10883 |
K. Chatterjee, W. Dvořák, M. H. Henzinger, and A. Svozil, “Quasipolynomial set-based symbolic algorithms for parity games,” in 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, Awassa, Ethiopia, 2018, vol. 57, pp. 233–253.
[Published Version]
View
| Files available
| DOI
| arXiv
2017 | Published | Journal Article | IST-REx-ID: 464 |
K. Chatterjee, M. H. Henzinger, and V. Loitzenbauer, “Improved algorithms for parity and Streett objectives,” Logical Methods in Computer Science, vol. 13, no. 3. International Federation of Computational Logic, 2017.
[Published Version]
View
| Files available
| DOI
| arXiv
2017 | Published | Conference Paper | IST-REx-ID: 552 |
K. Chatterjee, M. H. Henzinger, and A. Svozil, “Faster algorithms for mean-payoff parity games,” in Leibniz International Proceedings in Informatics, Aalborg, Denmark, 2017, vol. 83.
[Published Version]
View
| Files available
| DOI
2017 | Published | Conference Paper | IST-REx-ID: 12571 |
S. Bhattacharya, D. Chakrabarty, and M. H. Henzinger, “Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time,” in 19th International Conference on Integer Programming and Combinatorial Optimization, Waterloo, ON, Canada, 2017, vol. 10328, pp. 86–98.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2017 | Published | Conference Paper | IST-REx-ID: 11651 |
D. Wang, K. Fountoulakis, M. H. Henzinger, M. W. Mahoney, and Satish Rao , “Capacity releasing diffusion for speed and locality,” in Proceedings of the 34th International Conference on Machine Learning, Sydney, Australia, 2017, vol. 70, pp. 3598–3607.
[Published Version]
View
| Download Published Version (ext.)
| arXiv
2017 | Published | Journal Article | IST-REx-ID: 11665 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks,” ACM Transactions on Algorithms, vol. 13, no. 4. Association for Computing Machinery, 2017.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2017 | Published | Journal Article | IST-REx-ID: 11676 |
W. Dvořák, M. H. Henzinger, and D. P. Williamson, “Maximizing a submodular function with viability constraints,” Algorithmica, vol. 77, no. 1. Springer Nature, pp. 152–172, 2017.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2017 | Published | Conference Paper | IST-REx-ID: 11829 |
M. H. Henzinger, A. Lincoln, S. Neumann, and V. Vassilevska Williams, “Conditional hardness for sensitivity problems,” in 8th Innovations in Theoretical Computer Science Conference, Berkley, CA, United States, 2017, vol. 67.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2017 | Published | Conference Paper | IST-REx-ID: 11831 |
G. Goranci, M. H. Henzinger, and P. Peng, “Improved guarantees for vertex sparsification in planar graphs,” in 25th Annual European Symposium on Algorithms, Vienna, Austria, 2017, vol. 87.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
| arXiv
2017 | Published | Conference Paper | IST-REx-ID: 11832 |
M. H. Henzinger, D. Leniowski, and C. Mathieu, “Dynamic clustering to minimize the sum of radii,” in 25th Annual European Symposium on Algorithms, Vienna, Austria, 2017, vol. 87.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2017 | Published | Conference Paper | IST-REx-ID: 11833 |
G. Goranci, M. H. Henzinger, and P. Peng, “The power of vertex sparsifiers in dynamic graph algorithms,” in 25th Annual European Symposium on Algorithms, Vienna, Austria, 2017, vol. 87.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2017 | Published | Conference Paper | IST-REx-ID: 11873 |
M. H. Henzinger, S. Rao, and D. Wang, “Local flow partitioning for faster edge connectivity,” in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 2017, pp. 1919–1938.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2017 | Published | Conference Paper | IST-REx-ID: 11874 |
S. Bhattacharya, M. H. Henzinger, and D. Nanongkai, “Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time,” in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 2017, vol. 0, pp. 470–489.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2017 | Published | Journal Article | IST-REx-ID: 11903 |
S. Bhattacharya, W. Dvořák, M. H. Henzinger, and M. Starnberger, “Welfare maximization with friends-of-friends network externalities,” Theory of Computing Systems, vol. 61, no. 4. Springer Nature, pp. 948–986, 2017.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
2017 | Published | Conference Paper | IST-REx-ID: 6519 |
K. Chatterjee, W. Dvorák, M. H. Henzinger, and V. Loitzenbauer, “Improved set-based symbolic algorithms for parity games,” presented at the CSL: Conference on Computer Science Logic, Stockholm, Sweden, 2017, vol. 82.
[Published Version]
View
| Files available
| DOI
2016 | Published | Conference Paper | IST-REx-ID: 1140 |
K. Chatterjee, W. Dvoák, M. H. Henzinger, and V. Loitzenbauer, “Model and objective separation with conditional lower bounds: disjunction is harder than conjunction,” in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, New York, NY, USA, 2016, pp. 197–206.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2016 | Published | Conference Paper | IST-REx-ID: 11834 |
G. Goranci, M. H. Henzinger, and M. Thorup, “Incremental exact min-cut in poly-logarithmic amortized update time,” in 24th Annual European Symposium on Algorithms, Aarhus, Denmark, 2016, vol. 57.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2016 | Published | Conference Paper | IST-REx-ID: 11835 |
M. H. Henzinger and S. Neumann, “Incremental and fully dynamic subgraph connectivity for emergency planning,” in 24th Annual European Symposium on Algorithms, Aarhus, Denmark, 2016, vol. 57.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2016 | Published | Conference Paper | IST-REx-ID: 11836 |
Y. K. Cheung, G. Goranci, and M. H. Henzinger, “Graph minors for preserving terminal distances approximately - lower and upper bounds,” in 43rd International Colloquium on Automata, Languages, and Programming, Rome, Italy, 2016, vol. 55.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2016 | Published | Conference Paper | IST-REx-ID: 11866 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “A deterministic almost-tight distributed algorithm for approximating single-source shortest paths,” in 48th Annual ACM SIGACT Symposium on Theory of Computing, Cambridge, MA, United States, 2016, pp. 489–498.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2016 | Published | Conference Paper | IST-REx-ID: 11867 |
S. Bhattacharya, M. H. Henzinger, and D. Nanongkai, “New deterministic approximation algorithms for fully dynamic matching,” in 48th Annual ACM SIGACT Symposium on Theory of Computing, Cambridge, MA, United States, 2016, pp. 398–411.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2016 | Published | Journal Article | IST-REx-ID: 11891 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization,” SIAM Journal on Computing, vol. 45, no. 3. Society for Industrial & Applied Mathematics, pp. 947–1006, 2016.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2016 | Published | Conference Paper | IST-REx-ID: 1068 |
K. Chatterjee, W. Dvorák, M. H. Henzinger, and V. Loitzenbauer, “Conditionally optimal algorithms for generalized Büchi Games,” presented at the MFCS: Mathematical Foundations of Computer Science (SG), Krakow, Poland, 2016, vol. 58.
[Published Version]
View
| Files available
| DOI
2015 | Published | Journal Article | IST-REx-ID: 11668 |
R. Colini-Baldeschi, S. Leonardi, M. H. Henzinger, and M. Starnberger, “On multiple keyword sponsored search auctions with budgets,” ACM Transactions on Economics and Computation, vol. 4, no. 1. Association for Computing Machinery, 2015.
[Submitted Version]
View
| DOI
| Download Submitted Version (ext.)
2015 | Published | Journal Article | IST-REx-ID: 11669 |
P. Dütting, M. H. Henzinger, and M. Starnberger, “Auctions for heterogeneous items and budget limits,” ACM Transactions on Economics and Computation, vol. 4, no. 1. Association for Computing Machinery, 2015.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Published | Conference Paper | IST-REx-ID: 11773 |
O. Ben-Zwi, M. H. Henzinger, and V. Loitzenbauer, “Ad exchange: Envy-free auctions with mediators,” in 11th International Conference on Web and Internet Economics, Amsterdam, Netherlands, 2015, vol. 9470, pp. 104–117.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Published | Conference Paper | IST-REx-ID: 11774 |
Y. K. Cheung, M. H. Henzinger, M. Hoefer, and M. Starnberger, “Combinatorial auctions with conflict-based externalities,” in 11th International Conference on Web and Internet Economics, Amsterdam, Netherlands, 2015, vol. 9470, pp. 230–243.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Published | Conference Paper | IST-REx-ID: 11785 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Improved algorithms for decremental single-source reachability on directed graphs,” in 42nd International Colloquium on Automata, Languages and Programming, Kyoto, Japan, 2015, vol. 9134, pp. 725–736.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Published | Conference Paper | IST-REx-ID: 11786 |
S. Bhattacharya, M. H. Henzinger, and G. F. Italiano, “Design of dynamic algorithms via primal-dual method,” in 42nd International Colloquium on Automata, Languages and Programming, Kyoto, Japan, 2015, vol. 9134, pp. 206–218.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Published | Conference Paper | IST-REx-ID: 11787 |
M. H. Henzinger, S. Krinninger, and V. Loitzenbauer, “Finding 2-edge and 2-vertex strongly connected components in quadratic time,” in 2nd International Colloquium on Automata, Languages and Programming, Kyoto, Japan, 2015, vol. 9134, pp. 713–724.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Published | Conference Paper | IST-REx-ID: 11788 |
W. Dvořák and M. H. Henzinger, “Online ad assignment with an ad exchange,” in 12th International Workshop of Approximation and Online Algorithms, Wroclaw, Poland, 2015, vol. 8952, pp. 156–167.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Published | Conference Paper | IST-REx-ID: 11837 |
S. Bhattacharya, W. Dvorák, M. H. Henzinger, and Martin Starnberger, “Welfare maximization with friends-of-friends network externalities,” in 32nd International Symposium on Theoretical Aspects of Computer Science, Garching, Germany, 2015, vol. 30, pp. 90–102.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
2015 | Published | Journal Article | IST-REx-ID: 11845 |
O. Chernomor et al., “Split diversity in constrained conservation prioritization using integer linear programming,” Methods in Ecology and Evolution, vol. 6, no. 1. Wiley, pp. 83–91, 2015.
[Published Version]
View
| Files available
| DOI
| PubMed | Europe PMC
2015 | Published | Conference Paper | IST-REx-ID: 11868 |
M. H. Henzinger, S. Krinninger, D. Nanongkai, and T. Saranurak, “Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture,” in 47th Annual ACM Symposium on Theory of Computing, Portland, OR, United States, 2015.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Published | Conference Paper | IST-REx-ID: 11869 |
S. Bhattacharya, M. H. Henzinger, D. Nanongkai, and C. Tsourakakis, “Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams,” in 47th Annual ACM Symposium on Theory of Computing, Portland, OR, United States, 2015, pp. 173–182.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2015 | Published | Journal Article | IST-REx-ID: 11901 |
M. H. Henzinger and V. Loitzenbauer, “Truthful unit-demand auctions with budgets revisited,” Theoretical Computer Science, vol. 573. Elsevier, pp. 1–15, 2015.
View
| DOI
| Download None (ext.)
2015 | Published | Conference Paper | IST-REx-ID: 1661 |
K. Chatterjee, M. H. Henzinger, and V. Loitzenbauer, “Improved algorithms for one-pair and k-pair Streett objectives,” in Proceedings - Symposium on Logic in Computer Science, Kyoto, Japan, 2015, vol. 2015–July.
[Submitted Version]
View
| Files available
| DOI
| Download Submitted Version (ext.)
2014 | Published | Journal Article | IST-REx-ID: 535 |
K. Chatterjee, M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Polynomial-time algorithms for energy games with special weight structures,” Algorithmica, vol. 70, no. 3. Springer, pp. 457–492, 2014.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2014 | Published | Journal Article | IST-REx-ID: 1375 |
K. Chatterjee, M. H. Henzinger, S. Krinninger, V. Loitzenbauer, and M. Raskin, “Approximating the minimum cycle mean,” Theoretical Computer Science, vol. 547, no. C. Elsevier, pp. 104–116, 2014.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2014 | Published | Conference Paper | IST-REx-ID: 11789 |
M. Charikar, M. H. Henzinger, and H. L. Nguyễn, “Online bipartite matching with decomposable weights,” in 22nd Annual European Symposium on Algorithms, Wroclaw, Poland, 2014, vol. 8737, pp. 260–271.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2014 | Published | Conference Paper | IST-REx-ID: 11790
L. Cigler, W. Dvořák, M. H. Henzinger, and M. Starnberger, “Limiting price discrimination when selling products with positive network externalities,” in 10th International Conference of Web and Internet Economics, Beijing, China, 2014, vol. 8877, pp. 44–57.
View
| DOI
2014 | Published | Conference Paper | IST-REx-ID: 11855 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Decremental single-source shortest paths on undirected graphs in near-linear total update time,” in 55th Annual Symposium on Foundations of Computer Science, Philadelphia, PA, United States, 2014, pp. 146–155.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2014 | Published | Conference Paper | IST-REx-ID: 11870 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs,” in 46th Annual ACM Symposium on Theory of Computing, New York, NY, United States, 2014.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2014 | Published | Conference Paper | IST-REx-ID: 11875 |
S. Bhattacharya, M. H. Henzinger, and G. F. Italiano, “Deterministic fully dynamic data structures for vertex cover and matching,” in 26th Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, United States, 2014, pp. 785–804.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2014 | Published | Conference Paper | IST-REx-ID: 11876 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “A subquadratic-time algorithm for decremental single-source shortest paths,” in 25th Annual ACM-SIAM Symposium on Discrete Algorithms, Portland, OR, United States, 2014, pp. 1053–1072.
[Published Version]
View
| DOI
| Download Published Version (ext.)
2014 | Published | Journal Article | IST-REx-ID: 2141 |
K. Chatterjee and M. H. Henzinger, “Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition,” Journal of the ACM, vol. 61, no. 3. ACM, 2014.
[Submitted Version]
View
| Files available
| DOI
| Download Submitted Version (ext.)
2013 | Published | Journal Article | IST-REx-ID: 2831 |
K. Chatterjee, M. H. Henzinger, M. Joglekar, and N. Shah, “Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives,” Formal Methods in System Design, vol. 42, no. 3. Springer, pp. 301–327, 2013.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2013 | Published | Journal Article | IST-REx-ID: 11759 |
P. Dütting, M. H. Henzinger, and I. Weber, “Sponsored search, market equilibria, and the Hungarian Method,” Information Processing Letters, vol. 113, no. 3. Elsevier, pp. 67–73, 2013.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2013 | Published | Conference Paper | IST-REx-ID: 11791 |
P. Dütting, M. H. Henzinger, and M. Starnberger, “Valuation compressions in VCG-based combinatorial auctions,” in 9th International Conference on Web and Internet Economics, Cambridge, MA, USA, 2013, vol. 8289, pp. 146–159.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2013 | Published | Conference Paper | IST-REx-ID: 11792 |
W. Dvořák, M. H. Henzinger, and D. P. Williamson, “Maximizing a submodular function with viability constraints,” in 21st Annual European Symposium on Algorithms, Sophia Antipolis, France, 2013, vol. 8125, pp. 409–420.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2013 | Published | Conference Paper | IST-REx-ID: 11793 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks,” in 40th International Colloquium on Automata, Languages, and Programming, Riga, Latvia, 2013, vol. 7966, pp. 607–619.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2013 | Published | Conference Paper | IST-REx-ID: 11856 |
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization,” in 54th Annual Symposium on Foundations of Computer Science, Berkeley, CA, United States, 2013, pp. 538–547.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2013 | Published | Journal Article | IST-REx-ID: 11902
P. Dütting, M. H. Henzinger, and I. Weber, “Bidder optimal assignments for general utilities,” Theoretical Computer Science, vol. 478, no. 3. Elsevier, pp. 22–32, 2013.
View
| Files available
| DOI
2012 | Published | Conference Paper | IST-REx-ID: 3165 |
K. Chatterjee and M. H. Henzinger, “An O(n2) time algorithm for alternating Büchi games,” in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Kyoto, Japan, 2012, pp. 1386–1399.
View
| Files available
| DOI
| Download None (ext.)
| arXiv
2012 | Published | Conference Paper | IST-REx-ID: 11656
P. Dütting, M. H. Henzinger, and I. Weber, “Maximizing revenue from strategic recommendations under decaying trust,” in Proceedings of the 21st ACM international conference on Information and knowledge management, Maui, HI, United States, 2012, pp. 2268–2286.
View
| DOI
2012 | Published | Conference Paper | IST-REx-ID: 11794 |
P. Dütting, M. H. Henzinger, and M. Starnberger, “Auctions with heterogeneous items and budget limits,” in 8th International Workshop on Internet and Network Economics, Liverpool, United Kingdom, 2012, vol. 7695, pp. 44–57.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2012 | Published | Conference Paper | IST-REx-ID: 11795
R. Colini-Baldeschi, M. H. Henzinger, S. Leonardi, and M. Starnberger, “On multiple keyword sponsored search auctions with budgets,” in 39th International Colloquium on Automata, Languages, and Programming, Warwick, United Kingdom, 2012, vol. 7392, pp. 1–12.
View
| Files available
| DOI
2012 | Published | Conference Paper | IST-REx-ID: 10905 |
K. Chatterjee, M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Polynomial-time algorithms for energy games with special weight structures,” in Algorithms – ESA 2012, Ljubljana, Slovenia, 2012, vol. 7501, pp. 301–312.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2011 | Published | Conference Paper | IST-REx-ID: 3342 |
K. Chatterjee, M. H. Henzinger, M. Joglekar, and S. Nisarg, “Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives,” presented at the CAV: Computer Aided Verification, Snowbird, USA, 2011, vol. 6806, pp. 260–276.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2011 | Published | Conference Paper | IST-REx-ID: 3343 |
K. Chatterjee and M. H. Henzinger, “Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification,” presented at the SODA: Symposium on Discrete Algorithms, San Francisco, SA, United States, 2011, pp. 1318–1336.
[Submitted Version]
View
| DOI
| Download Submitted Version (ext.)
2011 | Published | Technical Report | IST-REx-ID: 5379 |
K. Chatterjee and M. H. Henzinger, An O(n2) time algorithm for alternating Büchi games. IST Austria, 2011.
[Published Version]
View
| Files available
| DOI
2010 | Published | Conference Paper | IST-REx-ID: 11797 |
J. Feldman, M. H. Henzinger, N. Korula, V. S. Mirrokni, and C. Stein, “Online stochastic packing applied to display ad allocation,” in 18th Annual European Symposium on Algorithms, Liverpool, United Kingdom, 2010, vol. 6346, pp. 182–194.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2010 | Published | Conference Paper | IST-REx-ID: 11838 |
P. Dütting, M. H. Henzinger, and I. Weber, “Sponsored search, market equilibria, and the Hungarian Method,” in 27th International Symposium on Theoretical Aspects of Computer Science, Nancy, France, 2010, vol. 5, pp. 287–298.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
| arXiv
2009 | Published | Conference Paper | IST-REx-ID: 11799
P. Dütting, M. H. Henzinger, and I. Weber, “Bidder optimal assignments for general utilities,” in 5th International Workshop on Internet and Network Economics, Rome, Italy, 2009, vol. 5929, pp. 575–582.
View
| Files available
| DOI
2009 | Published | Conference Paper | IST-REx-ID: 11912 |
Eda Baykan, M. H. Henzinger, S. F. Keller, S. de Castelberg, and M. Kinzler, “A comparison of techniques for sampling web pages,” in 26th International Symposium on Theoretical Aspects of Computer Science, Freiburg, Germany, 2009, vol. 3, pp. 13–30.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| arXiv
2007 | Published | Journal Article | IST-REx-ID: 11884
M. H. Henzinger, “Search technologies for the internet,” Science, vol. 317, no. 5837. American Association for the Advancement of Science, pp. 468–471, 2007.
View
| DOI
| PubMed | Europe PMC
2007 | Published | Conference Paper | IST-REx-ID: 11924
M. H. Henzinger, “Combinatorial algorithms for web search engines: three success stories,” in 18th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, United States, 2007, pp. 1022–1026.
View
2006 | Published | Conference Paper | IST-REx-ID: 11929
M. H. Henzinger, “Finding near-duplicate web pages: A large-scale evaluation of algorithms,” in 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Seattle, WA, United States, 2006, pp. 284–291.
View
| DOI
2005 | Published | Journal Article | IST-REx-ID: 11763 |
A. Goel, M. H. Henzinger, and S. Plotkin, “An online throughput-competitive algorithm for multicast routing and admission control,” Journal of Algorithms, vol. 55, no. 1. Elsevier, pp. 1–20, 2005.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
2005 | Published | Journal Article | IST-REx-ID: 11904
M. H. Henzinger, B.-W. Chang, B. Milch, and S. Brin, “Query-free news search,” World Wide Web, vol. 8, no. 2. Springer Nature, pp. 101–126, 2005.
View
| Files available
| DOI
2004 | Published | Journal Article | IST-REx-ID: 11762 |
M. H. Henzinger, “Algorithmic challenges in web search engines,” Internet Mathematics, vol. 1, no. 1. Internet Mathematics, pp. 115–123, 2004.
[Published Version]
View
| DOI
| Download Published Version (ext.)
2004 | Published | Journal Article | IST-REx-ID: 11877 |
M. H. Henzinger and S. Lawrence, “Extracting knowledge from the World Wide Web,” Proceedings of the National Academy of Sciences, vol. 101, no. suppl_1. Proceedings of the National Academy of Sciences, pp. 5186–5191, 2004.
[Published Version]
View
| DOI
| Download Published Version (ext.)
| PubMed | Europe PMC
2003 | Published | Journal Article | IST-REx-ID: 11766 |
M. H. Henzinger and S. Leonardi, “Scheduling multicasts on unit-capacity trees and meshes,” Journal of Computer and System Sciences, vol. 66, no. 3. Elsevier, pp. 567–611, 2003.
[Published Version]
View
| DOI
| Download Published Version (ext.)
2003 | Published | Conference Paper | IST-REx-ID: 11860
M. H. Henzinger, B.-W. Chang, B. Milch, and S. Brin, “Query-free news search,” in Proceedings of the 12th international conference on World Wide Web, Budapest, Hungary, 2003.
View
| Files available
| DOI
2003 | Published | Conference Paper | IST-REx-ID: 11897
K. Bharat and M. H. Henzinger, “Improved algorithms for topic distillation in a hyperlinked environment,” in 21st annual international ACM SIGIR conference on Research and development in information retrieval, Melbourne, Australia, 2003, pp. 104–111.
View
| DOI
2003 | Published | Conference Paper | IST-REx-ID: 11909 |
M. H. Henzinger, R. Motwani, and C. Silverstein, “Challenges in web search engines,” in 18th International Joint Conference on Artificial Intelligence, Acapulco, Mexico, 2003, pp. 1573–1579.
[Published Version]
View
| Download Published Version (ext.)
2000 | Published | Journal Article | IST-REx-ID: 11770 |
K. Bharat, A. Broder, J. Dean, and M. H. Henzinger, “A comparison of techniques to find mirrored hosts on the WWW,” Journal of the American Society for Information Science, vol. 51, no. 12. Wiley, pp. 1114–1122, 2000.
[Published Version]
View
| DOI
| Download Published Version (ext.)
1999 | Published | Journal Article | IST-REx-ID: 11679
M. H. Henzinger, V. King, and T. Warnow, “Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology,” Algorithmica, vol. 24. Springer Nature, pp. 1–13, 1999.
View
| Files available
| DOI
1999 | Published | Conference Paper | IST-REx-ID: 11691
A. Goel, M. H. Henzinger, S. Plotkin, and E. Tardos, “Scheduling data transfers in a network and the set scheduling problem,” in Proceedings of the 31st annual ACM symposium on Theory of computing, Atlanta, GA, United States, 1999, pp. 189–197.
View
| DOI
1999 | Published | Journal Article | IST-REx-ID: 11895 |
C. Silverstein, H. Marais, M. H. Henzinger, and M. Moricz, “Analysis of a very large web search engine query log,” ACM SIGIR Forum, vol. 33, no. 1. Association for Computing Machinery, pp. 6–12, 1999.
[Published Version]
View
| DOI
| Download Published Version (ext.)
1999 | Published | Conference Paper | IST-REx-ID: 11925
M. H. Henzinger and S. Leonardi , “Scheduling multicasts on unit-capacity trees and meshes,” in 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, United States, 1999, pp. 438–447.
View
1998 | Published | Journal Article | IST-REx-ID: 11680
D. Alberts and M. H. Henzinger, “Average-case analysis of dynamic graph algorithms,” Algorithmica, vol. 20. Springer Nature, pp. 31–60, 1998.
View
| Files available
| DOI
1998 | Published | Conference Paper | IST-REx-ID: 11682
P. K. Agarwal, D. EppsteinL. J. Guibas, and M. H. Henzinger, “Parametric and kinetic minimum spanning trees,” in Proceedings of the 39th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, United States, 1998, pp. 596–605.
View
| DOI
1998 | Published | Conference Paper | IST-REx-ID: 11926
A. Goel, M. H. Henzinger, and S. Plotkin, “An online throughput-competitive algorithm for multicast routing and admission control,” in 9th Annual ACM SIAM Symposium on Discrete Algorithms, San Francisco, CA, United States, 1998, pp. 97–106.
View
| Files available
1997 | Published | Journal Article | IST-REx-ID: 11767 |
M. H. Henzinger, P. Klein, S. Rao, and S. Subramanian, “Faster shortest-path algorithms for planar graphs,” Journal of Computer and System Sciences, vol. 55, no. 1. Elsevier, pp. 3–23, 1997.
[Published Version]
View
| DOI
| Download Published Version (ext.)
1997 | Published | Journal Article | IST-REx-ID: 11849 |
J. M. Anderson et al., “Continuous profiling: Where have all the cycles gone?,” ACM SIGOPS Operating Systems Review, vol. 31, no. 5. Association for Computing Machinery, pp. 1–14, 1997.
[Published Version]
View
| Files available
| DOI
| Download Published Version (ext.)
1996 | Published | Conference Paper | IST-REx-ID: 11927 |
M. H. Henzinger, V. King, and T. Warnow, “Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology,” in 7th Annual ACM-SIAM Symposium on Discrete Algorithms, Atlanta, GA, United States, 1996, pp. 333–340.
[Published Version]
View
| Files available
| Download Published Version (ext.)
1995 | Published | Conference Paper | IST-REx-ID: 11928 |
D. Alberts and M. H. Henzinger, “Average case analysis of dynamic graph algorithms,” in 6th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, United States, 1995, pp. 312–321.
[Published Version]
View
| Files available
| Download Published Version (ext.)