[{"extern":"1","date_updated":"2023-02-10T09:10:26Z","status":"public","conference":{"start_date":"2015-07-06","end_date":"2015-07-10","location":"Kyoto, Japan","name":"ICALP: International Colloquium on Automata, Languages, and Programming"},"type":"conference","_id":"11785","volume":9134,"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"isbn":["9783662476710"],"issn":["0302-9743"]},"intvolume":" 9134","month":"01","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1612.03856"}],"alternative_title":["LNCS"],"scopus_import":"1","oa_version":"Preprint","abstract":[{"text":"Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with 𝑜(𝑚𝑛) total update time, where 𝑚 is the number of edges and 𝑛 is the number of nodes in the graph [Henzinger et al. STOC 2014]. The algorithm is a combination of several different algorithms, each for a different 𝑚 vs. 𝑛 trade-off. For the case of 𝑚=Θ(𝑛1.5) the running time is 𝑂(𝑛2.47), just barely below 𝑚𝑛=Θ(𝑛2.5). In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of 𝑂̃ (min(𝑚7/6𝑛2/3,𝑚3/4𝑛5/4+𝑜(1),𝑚2/3𝑛4/3+𝑜(1)+𝑚3/7𝑛12/7+𝑜(1))). This gives, e.g., 𝑂(𝑛2.36) for the notorious case 𝑚=Θ(𝑛1.5). We obtain the same upper bounds for the problem of maintaining the strongly connected components of a directed graph undergoing edge deletions. Our algorithms are correct with high probabililty against an oblivious adversary.","lang":"eng"}],"title":"Improved algorithms for decremental single-source reachability on directed graphs","article_processing_charge":"No","external_id":{"arxiv":["1612.03856"]},"author":[{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"last_name":"Krinninger","full_name":"Krinninger, Sebastian","first_name":"Sebastian"},{"first_name":"Danupon","last_name":"Nanongkai","full_name":"Nanongkai, Danupon"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Henzinger, Monika H., et al. “Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.” 42nd International Colloquium on Automata, Languages and Programming, vol. 9134, Springer Nature, 2015, pp. 725–36, doi:10.1007/978-3-662-47672-7_59.","ama":"Henzinger MH, Krinninger S, Nanongkai D. Improved algorithms for decremental single-source reachability on directed graphs. In: 42nd International Colloquium on Automata, Languages and Programming. Vol 9134. Springer Nature; 2015:725-736. doi:10.1007/978-3-662-47672-7_59","apa":"Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2015). Improved algorithms for decremental single-source reachability on directed graphs. In 42nd International Colloquium on Automata, Languages and Programming (Vol. 9134, pp. 725–736). Kyoto, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-47672-7_59","ieee":"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.","short":"M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, 42nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 725–736.","chicago":"Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.” In 42nd International Colloquium on Automata, Languages and Programming, 9134:725–36. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47672-7_59.","ista":"Henzinger MH, Krinninger S, Nanongkai D. 2015. Improved algorithms for decremental single-source reachability on directed graphs. 42nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 725–736."},"date_created":"2022-08-11T08:51:32Z","date_published":"2015-01-01T00:00:00Z","doi":"10.1007/978-3-662-47672-7_59","page":"725 - 736","publication":"42nd International Colloquium on Automata, Languages and Programming","day":"01","year":"2015","oa":1,"quality_controlled":"1","publisher":"Springer Nature"},{"type":"conference","conference":{"start_date":"2015-07-06","end_date":"2015-07-10","location":"Kyoto, Japan","name":"ICALP: International Colloquium on Automata, Languages, and Programming"},"status":"public","_id":"11787","date_updated":"2023-02-10T09:21:47Z","extern":"1","alternative_title":["LNCS"],"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1412.6466"}],"month":"07","intvolume":" 9134","abstract":[{"lang":"eng","text":"We present faster algorithms for computing the 2-edge and 2-vertex strongly connected components of a directed graph. While in undirected graphs the 2-edge and 2-vertex connected components can be found in linear time, in directed graphs with m edges and n vertices only rather simple O(m n)-time algorithms were known. We use a hierarchical sparsification technique to obtain algorithms that run in time 𝑂(𝑛2). For 2-edge strongly connected components our algorithm gives the first running time improvement in 20 years. Additionally we present an 𝑂(𝑚2/log𝑛)-time algorithm for 2-edge strongly connected components, and thus improve over the O(m n) running time also when 𝑚=𝑂(𝑛). Our approach extends to k-edge and k-vertex strongly connected components for any constant k with a running time of 𝑂(𝑛2log𝑛) for k-edge-connectivity and 𝑂(𝑛3) for k-vertex-connectivity."}],"oa_version":"Preprint","volume":9134,"publication_identifier":{"issn":["0302-9743"],"isbn":["9783662476710"]},"publication_status":"published","language":[{"iso":"eng"}],"author":[{"last_name":"Henzinger","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Krinninger","full_name":"Krinninger, Sebastian","first_name":"Sebastian"},{"first_name":"Veronika","full_name":"Loitzenbauer, Veronika","last_name":"Loitzenbauer"}],"external_id":{"arxiv":["1412.6466"]},"article_processing_charge":"No","title":"Finding 2-edge and 2-vertex strongly connected components in quadratic time","citation":{"apa":"Henzinger, M. H., Krinninger, S., & Loitzenbauer, V. (2015). Finding 2-edge and 2-vertex strongly connected components in quadratic time. In 2nd International Colloquium on Automata, Languages and Programming (Vol. 9134, pp. 713–724). Kyoto, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-47672-7_58","ama":"Henzinger MH, Krinninger S, Loitzenbauer V. Finding 2-edge and 2-vertex strongly connected components in quadratic time. In: 2nd International Colloquium on Automata, Languages and Programming. Vol 9134. Springer Nature; 2015:713-724. doi:10.1007/978-3-662-47672-7_58","ieee":"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.","short":"M.H. Henzinger, S. Krinninger, V. Loitzenbauer, in:, 2nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 713–724.","mla":"Henzinger, Monika H., et al. “Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.” 2nd International Colloquium on Automata, Languages and Programming, vol. 9134, Springer Nature, 2015, pp. 713–24, doi:10.1007/978-3-662-47672-7_58.","ista":"Henzinger MH, Krinninger S, Loitzenbauer V. 2015. Finding 2-edge and 2-vertex strongly connected components in quadratic time. 2nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 713–724.","chicago":"Henzinger, Monika H, Sebastian Krinninger, and Veronika Loitzenbauer. “Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.” In 2nd International Colloquium on Automata, Languages and Programming, 9134:713–24. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47672-7_58."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Springer Nature","quality_controlled":"1","oa":1,"page":"713 - 724","doi":"10.1007/978-3-662-47672-7_58","date_published":"2015-07-06T00:00:00Z","date_created":"2022-08-11T09:38:34Z","year":"2015","day":"06","publication":"2nd International Colloquium on Automata, Languages and Programming"},{"publisher":"Springer Nature","quality_controlled":"1","oa":1,"day":"01","publication":"12th International Workshop of Approximation and Online Algorithms","year":"2015","doi":"10.1007/978-3-319-18263-6_14","date_published":"2015-01-01T00:00:00Z","date_created":"2022-08-11T09:43:32Z","page":"156–167","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Dvořák, Wolfgang, and Monika H. Henzinger. “Online Ad Assignment with an Ad Exchange.” 12th International Workshop of Approximation and Online Algorithms, vol. 8952, Springer Nature, 2015, pp. 156–167, doi:10.1007/978-3-319-18263-6_14.","ama":"Dvořák W, Henzinger MH. Online ad assignment with an ad exchange. In: 12th International Workshop of Approximation and Online Algorithms. Vol 8952. Springer Nature; 2015:156–167. doi:10.1007/978-3-319-18263-6_14","apa":"Dvořák, W., & Henzinger, M. H. (2015). Online ad assignment with an ad exchange. In 12th International Workshop of Approximation and Online Algorithms (Vol. 8952, pp. 156–167). Wroclaw, Poland: Springer Nature. https://doi.org/10.1007/978-3-319-18263-6_14","ieee":"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.","short":"W. Dvořák, M.H. Henzinger, in:, 12th International Workshop of Approximation and Online Algorithms, Springer Nature, 2015, pp. 156–167.","chicago":"Dvořák, Wolfgang, and Monika H Henzinger. “Online Ad Assignment with an Ad Exchange.” In 12th International Workshop of Approximation and Online Algorithms, 8952:156–167. Springer Nature, 2015. https://doi.org/10.1007/978-3-319-18263-6_14.","ista":"Dvořák W, Henzinger MH. 2015. Online ad assignment with an ad exchange. 12th International Workshop of Approximation and Online Algorithms. WAOA: International Workshop on Approximation and Online Algorithms, LNCS, vol. 8952, 156–167."},"title":"Online ad assignment with an ad exchange","author":[{"full_name":"Dvořák, Wolfgang","last_name":"Dvořák","first_name":"Wolfgang"},{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"}],"article_processing_charge":"No","external_id":{"arxiv":["1604.05603"]},"oa_version":"Preprint","abstract":[{"text":"Ad exchanges are becoming an increasingly popular way to sell advertisement slots on the internet. An ad exchange is basically a spot market for ad impressions. A publisher who has already signed contracts reserving advertisement impressions on his pages can choose between assigning a new ad impression for a new page view to a contracted advertiser or to sell it at an ad exchange. This leads to an online revenue maximization problem for the publisher. Given a new impression to sell decide whether (a) to assign it to a contracted advertiser and if so to which one or (b) to sell it at the ad exchange and if so at which reserve price. We make no assumptions about the distribution of the advertiser valuations that participate in the ad exchange and show that there exists a simple primal-dual based online algorithm, whose lower bound for the revenue converges to 𝑅𝐴𝐷𝑋+𝑅𝐴(1−1/𝑒), where 𝑅𝐴𝐷𝑋 is the revenue that the optimum algorithm achieves from the ad exchange and 𝑅𝐴 is the revenue that the optimum algorithm achieves from the contracted advertisers.","lang":"eng"}],"month":"01","intvolume":" 8952","scopus_import":"1","alternative_title":["LNCS"],"main_file_link":[{"url":"https://arxiv.org/abs/1604.05603","open_access":"1"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["0302-9743"]},"publication_status":"published","volume":8952,"_id":"11788","status":"public","type":"conference","conference":{"start_date":"2014-09-11","end_date":"2014-09-12","location":"Wroclaw, Poland","name":"WAOA: International Workshop on Approximation and Online Algorithms"},"extern":"1","date_updated":"2023-02-10T09:26:06Z"},{"date_created":"2022-08-11T09:28:49Z","date_published":"2015-01-01T00:00:00Z","doi":"10.1007/978-3-662-47672-7_17","page":"206 - 218","publication":"42nd International Colloquium on Automata, Languages and Programming","day":"01","year":"2015","oa":1,"quality_controlled":"1","publisher":"Springer Nature","title":"Design of dynamic algorithms via primal-dual method","external_id":{"arxiv":["1604.05337"]},"article_processing_charge":"No","author":[{"first_name":"Sayan","full_name":"Bhattacharya, Sayan","last_name":"Bhattacharya"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger"},{"first_name":"Giuseppe F.","last_name":"Italiano","full_name":"Italiano, Giuseppe F."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"apa":"Bhattacharya, S., Henzinger, M. H., & Italiano, G. F. (2015). Design of dynamic algorithms via primal-dual method. In 42nd International Colloquium on Automata, Languages and Programming (Vol. 9134, pp. 206–218). Kyoto, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-47672-7_17","ama":"Bhattacharya S, Henzinger MH, Italiano GF. Design of dynamic algorithms via primal-dual method. In: 42nd International Colloquium on Automata, Languages and Programming. Vol 9134. Springer Nature; 2015:206-218. doi:10.1007/978-3-662-47672-7_17","short":"S. Bhattacharya, M.H. Henzinger, G.F. Italiano, in:, 42nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 206–218.","ieee":"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.","mla":"Bhattacharya, Sayan, et al. “Design of Dynamic Algorithms via Primal-Dual Method.” 42nd International Colloquium on Automata, Languages and Programming, vol. 9134, Springer Nature, 2015, pp. 206–18, doi:10.1007/978-3-662-47672-7_17.","ista":"Bhattacharya S, Henzinger MH, Italiano GF. 2015. Design of dynamic algorithms via primal-dual method. 42nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 206–218.","chicago":"Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe F. Italiano. “Design of Dynamic Algorithms via Primal-Dual Method.” In 42nd International Colloquium on Automata, Languages and Programming, 9134:206–18. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47672-7_17."},"volume":9134,"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"isbn":["9783662476710"],"issn":["0302-9743"]},"intvolume":" 9134","month":"01","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1604.05337"}],"alternative_title":["LNCS"],"scopus_import":"1","oa_version":"Preprint","abstract":[{"lang":"eng","text":"In this paper, we develop a dynamic version of the primal-dual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an 𝑂(𝑓2)-approximately optimal solution in 𝑂(𝑓⋅log(𝑚+𝑛)) amortized update time, where 𝑓 is the maximum “frequency” of an element, 𝑛 is the number of sets, and 𝑚 is the maximum number of elements in the universe at any point in time. (2) For the dynamic 𝑏-matching problem, we maintain an 𝑂(1)-approximately optimal solution in 𝑂(log3𝑛) amortized update time, where 𝑛 is the number of nodes in the graph."}],"extern":"1","date_updated":"2023-02-10T09:13:31Z","status":"public","conference":{"start_date":"2015-07-06","location":"Kyoto, Japan","end_date":"2015-07-10","name":"ICALP: International Colloquium on Automata, Languages, and Programming"},"type":"conference","_id":"11786"},{"citation":{"chicago":"Chernomor, Olga, Bui Quang Minh, Félix Forest, Steffen Klaere, Travis Ingram, Monika H Henzinger, and Arndt von Haeseler. “Split Diversity in Constrained Conservation Prioritization Using Integer Linear Programming.” Methods in Ecology and Evolution. Wiley, 2015. https://doi.org/10.1111/2041-210x.12299.","ista":"Chernomor O, Minh BQ, Forest F, Klaere S, Ingram T, Henzinger MH, von Haeseler A. 2015. Split diversity in constrained conservation prioritization using integer linear programming. Methods in Ecology and Evolution. 6(1), 83–91.","mla":"Chernomor, Olga, et al. “Split Diversity in Constrained Conservation Prioritization Using Integer Linear Programming.” Methods in Ecology and Evolution, vol. 6, no. 1, Wiley, 2015, pp. 83–91, doi:10.1111/2041-210x.12299.","apa":"Chernomor, O., Minh, B. Q., Forest, F., Klaere, S., Ingram, T., Henzinger, M. H., & von Haeseler, A. (2015). Split diversity in constrained conservation prioritization using integer linear programming. Methods in Ecology and Evolution. Wiley. https://doi.org/10.1111/2041-210x.12299","ama":"Chernomor O, Minh BQ, Forest F, et al. Split diversity in constrained conservation prioritization using integer linear programming. Methods in Ecology and Evolution. 2015;6(1):83-91. doi:10.1111/2041-210x.12299","ieee":"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.","short":"O. Chernomor, B.Q. Minh, F. Forest, S. Klaere, T. Ingram, M.H. Henzinger, A. von Haeseler, Methods in Ecology and Evolution 6 (2015) 83–91."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"pmid":["25893087"]},"article_processing_charge":"No","author":[{"full_name":"Chernomor, Olga","last_name":"Chernomor","first_name":"Olga"},{"first_name":"Bui Quang","last_name":"Minh","full_name":"Minh, Bui Quang"},{"first_name":"Félix","full_name":"Forest, Félix","last_name":"Forest"},{"full_name":"Klaere, Steffen","last_name":"Klaere","first_name":"Steffen"},{"first_name":"Travis","last_name":"Ingram","full_name":"Ingram, Travis"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"full_name":"von Haeseler, Arndt","last_name":"von Haeseler","first_name":"Arndt"}],"title":"Split diversity in constrained conservation prioritization using integer linear programming","year":"2015","has_accepted_license":"1","publication":"Methods in Ecology and Evolution","day":"01","page":"83-91","date_created":"2022-08-16T06:43:49Z","date_published":"2015-01-01T00:00:00Z","doi":"10.1111/2041-210x.12299","oa":1,"quality_controlled":"1","publisher":"Wiley","date_updated":"2023-02-17T09:30:08Z","ddc":["570"],"extern":"1","file_date_updated":"2022-08-16T06:52:53Z","_id":"11845","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_type":"original","type":"journal_article","status":"public","publication_status":"published","publication_identifier":{"eissn":["2041-210X"]},"language":[{"iso":"eng"}],"file":[{"date_updated":"2022-08-16T06:52:53Z","file_size":411415,"creator":"asandaue","date_created":"2022-08-16T06:52:53Z","file_name":"2015_MethodsInEcologyAndEvolutionChernomor.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"11846","checksum":"880e78f09f0ac99cb351c48dc97623b6","success":1}],"volume":6,"issue":"1","abstract":[{"lang":"eng","text":"Phylogenetic diversity (PD) is a measure of biodiversity based on the evolutionary history of species. Here, we discuss several optimization problems related to the use of PD, and the more general measure split diversity (SD), in conservation prioritization.\r\nDepending on the conservation goal and the information available about species, one can construct optimization routines that incorporate various conservation constraints. We demonstrate how this information can be used to select sets of species for conservation action. Specifically, we discuss the use of species' geographic distributions, the choice of candidates under economic pressure, and the use of predator–prey interactions between the species in a community to define viability constraints.\r\nDespite such optimization problems falling into the area of NP hard problems, it is possible to solve them in a reasonable amount of time using integer programming. We apply integer linear programming to a variety of models for conservation prioritization that incorporate the SD measure.\r\nWe exemplarily show the results for two data sets: the Cape region of South Africa and a Caribbean coral reef community. Finally, we provide user-friendly software at http://www.cibiv.at/software/pda."}],"oa_version":"Published Version","pmid":1,"scopus_import":"1","intvolume":" 6","month":"01"},{"status":"public","type":"conference","conference":{"name":"STOC: Symposium on Theory of Computing","location":"Portland, OR, United States","end_date":"2015-06-17","start_date":"2015-06-14"},"article_number":"21-30","_id":"11868","title":"Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"first_name":"Sebastian","full_name":"Krinninger, Sebastian","last_name":"Krinninger"},{"full_name":"Nanongkai, Danupon","last_name":"Nanongkai","first_name":"Danupon"},{"last_name":"Saranurak","full_name":"Saranurak, Thatchaphol","first_name":"Thatchaphol"}],"article_processing_charge":"No","external_id":{"arxiv":["1511.06773"]},"extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-17T11:09:54Z","citation":{"chicago":"Henzinger, Monika H, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. “Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.” In 47th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, 2015. https://doi.org/10.1145/2746539.2746609.","ista":"Henzinger MH, Krinninger S, Nanongkai D, Saranurak T. 2015. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. 47th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 21–30.","mla":"Henzinger, Monika H., et al. “Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.” 47th Annual ACM Symposium on Theory of Computing, 21–30, Association for Computing Machinery, 2015, doi:10.1145/2746539.2746609.","ieee":"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.","short":"M.H. Henzinger, S. Krinninger, D. Nanongkai, T. Saranurak, in:, 47th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2015.","apa":"Henzinger, M. H., Krinninger, S., Nanongkai, D., & Saranurak, T. (2015). 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: Association for Computing Machinery. https://doi.org/10.1145/2746539.2746609","ama":"Henzinger MH, Krinninger S, Nanongkai D, Saranurak T. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In: 47th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery; 2015. doi:10.1145/2746539.2746609"},"month":"06","scopus_import":"1","publisher":"Association for Computing Machinery","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1511.06773"}],"oa":1,"oa_version":"Preprint","abstract":[{"lang":"eng","text":"Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an n x n matrix M and will receive n column-vectors of size n, denoted by v1, ..., vn, one by one. After seeing each vector vi, we have to output the product Mvi before we can see the next vector. A naive algorithm can solve this problem using O(n3) time in total, and its running time can be slightly improved to O(n3/log2 n) [Williams SODA'07]. We show that a conjecture that there is no truly subcubic (O(n3-ε)) time algorithm for this problem can be used to exhibit the underlying polynomial time hardness shared by many dynamic problems. For a number of problems, such as subgraph connectivity, Pagh's problem, d-failure connectivity, decremental single-source shortest paths, and decremental transitive closure, this conjecture implies tight hardness results. Thus, proving or disproving this conjecture will be very interesting as it will either imply several tight unconditional lower bounds or break through a common barrier that blocks progress with these problems. This conjecture might also be considered as strong evidence against any further improvement for these problems since refuting it will imply a major breakthrough for combinatorial Boolean matrix multiplication and other long-standing problems if the term \"combinatorial algorithms\" is interpreted as \"Strassen-like algorithms\" [Ballard et al. SPAA'11].\r\n\r\nThe conjecture also leads to hardness results for problems that were previously based on diverse problems and conjectures -- such as 3SUM, combinatorial Boolean matrix multiplication, triangle detection, and multiphase -- thus providing a uniform way to prove polynomial hardness results for dynamic algorithms; some of the new proofs are also simpler or even become trivial. The conjecture also leads to stronger and new, non-trivial, hardness results, e.g., for the fully-dynamic densest subgraph and diameter problems."}],"date_published":"2015-06-14T00:00:00Z","doi":"10.1145/2746539.2746609","date_created":"2022-08-16T09:31:21Z","day":"14","language":[{"iso":"eng"}],"publication":"47th Annual ACM Symposium on Theory of Computing","publication_identifier":{"issn":["0737.8017"],"isbn":["978-145033536-2"]},"year":"2015","publication_status":"published"},{"citation":{"ista":"Bhattacharya S, Henzinger MH, Nanongkai D, Tsourakakis C. 2015. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. 47th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 173–182.","chicago":"Bhattacharya, Sayan, Monika H Henzinger, Danupon Nanongkai, and Charalampos Tsourakakis. “Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.” In 47th Annual ACM Symposium on Theory of Computing, 173–82. Association for Computing Machinery, 2015. https://doi.org/10.1145/2746539.2746592.","apa":"Bhattacharya, S., Henzinger, M. H., Nanongkai, D., & Tsourakakis, C. (2015). Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In 47th Annual ACM Symposium on Theory of Computing (pp. 173–182). Portland, OR, United States: Association for Computing Machinery. https://doi.org/10.1145/2746539.2746592","ama":"Bhattacharya S, Henzinger MH, Nanongkai D, Tsourakakis C. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In: 47th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery; 2015:173-182. doi:10.1145/2746539.2746592","ieee":"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.","short":"S. Bhattacharya, M.H. Henzinger, D. Nanongkai, C. Tsourakakis, in:, 47th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2015, pp. 173–182.","mla":"Bhattacharya, Sayan, et al. “Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.” 47th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2015, pp. 173–82, doi:10.1145/2746539.2746592."},"date_updated":"2023-02-17T11:17:03Z","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Bhattacharya","full_name":"Bhattacharya, Sayan","first_name":"Sayan"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger"},{"first_name":"Danupon","full_name":"Nanongkai, Danupon","last_name":"Nanongkai"},{"first_name":"Charalampos","last_name":"Tsourakakis","full_name":"Tsourakakis, Charalampos"}],"external_id":{"arxiv":["1504.02268"]},"article_processing_charge":"No","title":"Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams","_id":"11869","type":"conference","conference":{"name":"STOC: Symposium on Theory of Computing","end_date":"2015-06-17","location":"Portland, OR, United States","start_date":"2015-06-14"},"status":"public","publication_identifier":{"issn":["0737-8017"],"isbn":["978-145033536-2"]},"year":"2015","publication_status":"published","day":"01","language":[{"iso":"eng"}],"publication":"47th Annual ACM Symposium on Theory of Computing","page":"173 - 182","doi":"10.1145/2746539.2746592","date_published":"2015-06-01T00:00:00Z","date_created":"2022-08-16T09:36:48Z","abstract":[{"lang":"eng","text":"While in many graph mining applications it is crucial to handle a stream of updates efficiently in terms of both time and space, not much was known about achieving such type of algorithm. In this paper we study this issue for a problem which lies at the core of many graph mining applications called densest subgraph problem. We develop an algorithm that achieves time- and space-efficiency for this problem simultaneously. It is one of the first of its kind for graph problems to the best of our knowledge.\r\n\r\nGiven an input graph, the densest subgraph is the subgraph that maximizes the ratio between the number of edges and the number of nodes. For any ε>0, our algorithm can, with high probability, maintain a (4+ε)-approximate solution under edge insertions and deletions using ~O(n) space and ~O(1) amortized time per update; here, $n$ is the number of nodes in the graph and ~O hides the O(polylog_{1+ε} n) term. The approximation ratio can be improved to (2+ε) with more time. It can be extended to a (2+ε)-approximation sublinear-time algorithm and a distributed-streaming algorithm. Our algorithm is the first streaming algorithm that can maintain the densest subgraph in one pass. Prior to this, no algorithm could do so even in the special case of an incremental stream and even when there is no time restriction. The previously best algorithm in this setting required O(log n) passes [BahmaniKV12]. The space required by our algorithm is tight up to a polylogarithmic factor."}],"oa_version":"Preprint","publisher":"Association for Computing Machinery","quality_controlled":"1","scopus_import":"1","oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1504.02268"}],"month":"06"},{"author":[{"first_name":"Sayan","full_name":"Bhattacharya, Sayan","last_name":"Bhattacharya"},{"last_name":"Dvorák","full_name":"Dvorák, Wolfgang","first_name":"Wolfgang"},{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"first_name":" Martin","last_name":"Starnberger","full_name":"Starnberger, Martin"}],"article_processing_charge":"No","title":"Welfare maximization with friends-of-friends network externalities","citation":{"mla":"Bhattacharya, Sayan, et al. “Welfare Maximization with Friends-of-Friends Network Externalities.” 32nd International Symposium on Theoretical Aspects of Computer Science, vol. 30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 90–102, doi:10.4230/LIPICS.STACS.2015.90.","short":"S. Bhattacharya, W. Dvorák, M.H. Henzinger, Martin Starnberger, in:, 32nd International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 90–102.","ieee":"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.","apa":"Bhattacharya, S., Dvorák, W., Henzinger, M. H., & Starnberger, Martin. (2015). Welfare maximization with friends-of-friends network externalities. In 32nd International Symposium on Theoretical Aspects of Computer Science (Vol. 30, pp. 90–102). Garching, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.STACS.2015.90","ama":"Bhattacharya S, Dvorák W, Henzinger MH, Starnberger Martin. Welfare maximization with friends-of-friends network externalities. In: 32nd International Symposium on Theoretical Aspects of Computer Science. Vol 30. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:90-102. doi:10.4230/LIPICS.STACS.2015.90","chicago":"Bhattacharya, Sayan, Wolfgang Dvorák, Monika H Henzinger, and Martin Starnberger. “Welfare Maximization with Friends-of-Friends Network Externalities.” In 32nd International Symposium on Theoretical Aspects of Computer Science, 30:90–102. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. https://doi.org/10.4230/LIPICS.STACS.2015.90.","ista":"Bhattacharya S, Dvorák W, Henzinger MH, Starnberger Martin. 2015. Welfare maximization with friends-of-friends network externalities. 32nd International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 30, 90–102."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"page":"90-102","doi":"10.4230/LIPICS.STACS.2015.90","date_published":"2015-02-26T00:00:00Z","date_created":"2022-08-12T11:39:40Z","year":"2015","day":"26","publication":"32nd International Symposium on Theoretical Aspects of Computer Science","type":"conference","conference":{"name":"STACS: Symposium on Theoretical Aspects of Computer Science","location":"Garching, Germany","end_date":"2015-03-07","start_date":"2015-03-04"},"status":"public","_id":"11837","date_updated":"2023-02-21T16:32:37Z","extern":"1","alternative_title":["LIPIcs"],"scopus_import":"1","main_file_link":[{"url":"https://doi.org/10.4230/LIPICS.STACS.2015.90","open_access":"1"}],"month":"02","intvolume":" 30","abstract":[{"text":"Online social networks allow the collection of large amounts of data about the influence between users connected by a friendship-like relationship. When distributing items among agents forming a social network, this information allows us to exploit network externalities that each agent receives from his neighbors that get the same item. In this paper we consider Friends-of-Friends (2-hop) network externalities, i.e., externalities that not only depend on the neighbors that get the same item but also on neighbors of neighbors. For these externalities we study a setting where multiple different items are assigned to unit-demand agents. Specifically, we study the problem of welfare maximization under different types of externality functions. Let n be the number of agents and m be the number of items. Our contributions are the following: (1) We show that welfare maximization is APX-hard; we show that even for step functions with 2-hop (and also with 1-hop) externalities it is NP-hard to approximate social welfare better than (1-1/e). (2) On the positive side we present (i) an O(sqrt n)-approximation algorithm for general concave externality functions,\r\n(ii) an O(\\log m)-approximation algorithm for linear externality functions, and (iii) an (1-1/e)\\frac{1}{6}-approximation algorithm for 2-hop step function externalities. We also improve the result from [6] for 1-hop step function externalities by giving a (1-1/e)/2-approximation algorithm.","lang":"eng"}],"oa_version":"Published Version","related_material":{"record":[{"id":"11903","status":"public","relation":"later_version"}]},"volume":30,"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-939897-78-1"]},"publication_status":"published","language":[{"iso":"eng"}]},{"title":"Truthful unit-demand auctions with budgets revisited","article_processing_charge":"No","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger"},{"full_name":"Loitzenbauer, Veronika","last_name":"Loitzenbauer","first_name":"Veronika"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Henzinger, Monika H, and Veronika Loitzenbauer. “Truthful Unit-Demand Auctions with Budgets Revisited.” Theoretical Computer Science. Elsevier, 2015. https://doi.org/10.1016/j.tcs.2015.01.033.","ista":"Henzinger MH, Loitzenbauer V. 2015. Truthful unit-demand auctions with budgets revisited. Theoretical Computer Science. 573, 1–15.","mla":"Henzinger, Monika H., and Veronika Loitzenbauer. “Truthful Unit-Demand Auctions with Budgets Revisited.” Theoretical Computer Science, vol. 573, Elsevier, 2015, pp. 1–15, doi:10.1016/j.tcs.2015.01.033.","short":"M.H. Henzinger, V. Loitzenbauer, Theoretical Computer Science 573 (2015) 1–15.","ieee":"M. H. Henzinger and V. Loitzenbauer, “Truthful unit-demand auctions with budgets revisited,” Theoretical Computer Science, vol. 573. Elsevier, pp. 1–15, 2015.","ama":"Henzinger MH, Loitzenbauer V. Truthful unit-demand auctions with budgets revisited. Theoretical Computer Science. 2015;573:1-15. doi:10.1016/j.tcs.2015.01.033","apa":"Henzinger, M. H., & Loitzenbauer, V. (2015). Truthful unit-demand auctions with budgets revisited. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2015.01.033"},"oa":1,"quality_controlled":"1","publisher":"Elsevier","date_created":"2022-08-17T09:06:53Z","date_published":"2015-03-30T00:00:00Z","doi":"10.1016/j.tcs.2015.01.033","page":"1-15","publication":"Theoretical Computer Science","day":"30","year":"2015","status":"public","article_type":"original","type":"journal_article","_id":"11901","extern":"1","date_updated":"2023-02-17T14:50:04Z","intvolume":" 573","month":"03","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1016/j.tcs.2015.01.033"}],"scopus_import":"1","oa_version":"None","abstract":[{"text":"We consider auctions of indivisible items to unit-demand bidders with budgets. This setting was suggested as an expressive model for single sponsored search auctions. Prior work presented mechanisms that compute bidder-optimal outcomes and are truthful for a restricted set of inputs, i.e., inputs in so-called general position. This condition is easily violated. We provide the first mechanism that is truthful in expectation for all inputs and achieves for each bidder no worse utility than the bidder-optimal outcome. Additionally we give a complete characterization for which inputs mechanisms that compute bidder-optimal outcomes are truthful.","lang":"eng"}],"volume":573,"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"issn":["0304-3975"]}},{"title":"Continuous flow reduction of artemisinic acid utilizing multi-injection strategies-closing the gap towards a fully continuous synthesis of antimalarial drugs","author":[{"last_name":"Pieber","orcid":"0000-0001-8689-388X","full_name":"Pieber, Bartholomäus","first_name":"Bartholomäus","id":"93e5e5b2-0da6-11ed-8a41-af589a024726"},{"full_name":"Glasnov, Toma","last_name":"Glasnov","first_name":"Toma"},{"first_name":"C. Oliver","full_name":"Kappe, C. Oliver","last_name":"Kappe"}],"external_id":{"pmid":["25655090"]},"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ieee":"B. Pieber, T. Glasnov, and C. O. Kappe, “Continuous flow reduction of artemisinic acid utilizing multi-injection strategies-closing the gap towards a fully continuous synthesis of antimalarial drugs,” Chemistry - A European Journal, vol. 21, no. 11. Wiley, pp. 4368–4376, 2015.","short":"B. Pieber, T. Glasnov, C.O. Kappe, Chemistry - A European Journal 21 (2015) 4368–4376.","ama":"Pieber B, Glasnov T, Kappe CO. Continuous flow reduction of artemisinic acid utilizing multi-injection strategies-closing the gap towards a fully continuous synthesis of antimalarial drugs. Chemistry - A European Journal. 2015;21(11):4368-4376. doi:10.1002/chem.201406439","apa":"Pieber, B., Glasnov, T., & Kappe, C. O. (2015). Continuous flow reduction of artemisinic acid utilizing multi-injection strategies-closing the gap towards a fully continuous synthesis of antimalarial drugs. Chemistry - A European Journal. Wiley. https://doi.org/10.1002/chem.201406439","mla":"Pieber, Bartholomäus, et al. “Continuous Flow Reduction of Artemisinic Acid Utilizing Multi-Injection Strategies-Closing the Gap towards a Fully Continuous Synthesis of Antimalarial Drugs.” Chemistry - A European Journal, vol. 21, no. 11, Wiley, 2015, pp. 4368–76, doi:10.1002/chem.201406439.","ista":"Pieber B, Glasnov T, Kappe CO. 2015. Continuous flow reduction of artemisinic acid utilizing multi-injection strategies-closing the gap towards a fully continuous synthesis of antimalarial drugs. Chemistry - A European Journal. 21(11), 4368–4376.","chicago":"Pieber, Bartholomäus, Toma Glasnov, and C. Oliver Kappe. “Continuous Flow Reduction of Artemisinic Acid Utilizing Multi-Injection Strategies-Closing the Gap towards a Fully Continuous Synthesis of Antimalarial Drugs.” Chemistry - A European Journal. Wiley, 2015. https://doi.org/10.1002/chem.201406439."},"publisher":"Wiley","quality_controlled":"1","date_published":"2015-03-09T00:00:00Z","doi":"10.1002/chem.201406439","date_created":"2022-08-24T11:11:10Z","page":"4368-4376","day":"09","publication":"Chemistry - A European Journal","year":"2015","status":"public","article_type":"original","type":"journal_article","_id":"11962","extern":"1","date_updated":"2023-02-21T10:09:30Z","month":"03","intvolume":" 21","scopus_import":"1","pmid":1,"oa_version":"None","abstract":[{"lang":"eng","text":"One of the rare alternative reagents for the reduction of carbon–carbon double bonds is diimide (HNNH), which can be generated in situ from hydrazine hydrate (N2H4⋅H2O) and O2. Although this selective method is extremely clean and powerful, it is rarely used, as the rate-determining oxidation of hydrazine in the absence of a catalyst is relatively slow using conventional batch protocols. A continuous high-temperature/high-pressure methodology dramatically enhances the initial oxidation step, at the same time allowing for a safe and scalable processing of the hazardous reaction mixture. Simple alkenes can be selectively reduced within 10–20 min at 100–120 °C and 20 bar O2 pressure. The development of a multi-injection reactor platform for the periodic addition of N2H4⋅H2O enables the reduction of less reactive olefins even at lower reaction temperatures. This concept was utilized for the highly selective reduction of artemisinic acid to dihydroartemisinic acid, the precursor molecule for the semisynthesis of the antimalarial drug artemisinin. The industrially relevant reduction was achieved by using four consecutive liquid feeds (of N2H4⋅H2O) and residence time units resulting in a highly selective reduction within approximately 40 min at 60 °C and 20 bar O2 pressure, providing dihydroartemisinic acid in ≥93 % yield and ≥95 % selectivity."}],"issue":"11","volume":21,"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1521-3765"],"issn":["0947-6539"]},"publication_status":"published"}]