--- _id: '11785' abstract: - lang: eng 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 \U0001D45C(\U0001D45A\U0001D45B) total update time, where \U0001D45A is the number of edges and \U0001D45B 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 \U0001D45A vs. \U0001D45B trade-off. For the case of \U0001D45A=Θ(\U0001D45B1.5) the running time is \U0001D442(\U0001D45B2.47), just barely below \U0001D45A\U0001D45B=Θ(\U0001D45B2.5). In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of \U0001D442̃ (min(\U0001D45A7/6\U0001D45B2/3,\U0001D45A3/4\U0001D45B5/4+\U0001D45C(1),\U0001D45A2/3\U0001D45B4/3+\U0001D45C(1)+\U0001D45A3/7\U0001D45B12/7+\U0001D45C(1))). This gives, e.g., \U0001D442(\U0001D45B2.36) for the notorious case \U0001D45A=Θ(\U0001D45B1.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." alternative_title: - LNCS article_processing_charge: No author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Sebastian full_name: Krinninger, Sebastian last_name: Krinninger - first_name: Danupon full_name: Nanongkai, Danupon last_name: Nanongkai citation: 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' 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. 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. 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.' 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. short: M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, 42nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 725–736. conference: end_date: 2015-07-10 location: Kyoto, Japan name: 'ICALP: International Colloquium on Automata, Languages, and Programming' start_date: 2015-07-06 date_created: 2022-08-11T08:51:32Z date_published: 2015-01-01T00:00:00Z date_updated: 2023-02-10T09:10:26Z day: '01' doi: 10.1007/978-3-662-47672-7_59 extern: '1' external_id: arxiv: - '1612.03856' intvolume: ' 9134' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1612.03856 month: '01' oa: 1 oa_version: Preprint page: 725 - 736 publication: 42nd International Colloquium on Automata, Languages and Programming publication_identifier: isbn: - '9783662476710' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Improved algorithms for decremental single-source reachability on directed graphs type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 9134 year: '2015' ... --- _id: '11787' 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 \U0001D442(\U0001D45B2). For 2-edge strongly connected components our algorithm gives the first running time improvement in 20 years. Additionally we present an \U0001D442(\U0001D45A2/log\U0001D45B)-time algorithm for 2-edge strongly connected components, and thus improve over the O(m n) running time also when \U0001D45A=\U0001D442(\U0001D45B). Our approach extends to k-edge and k-vertex strongly connected components for any constant k with a running time of \U0001D442(\U0001D45B2log\U0001D45B) for k-edge-connectivity and \U0001D442(\U0001D45B3) for k-vertex-connectivity." alternative_title: - LNCS article_processing_charge: No author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Sebastian full_name: Krinninger, Sebastian last_name: Krinninger - first_name: Veronika full_name: Loitzenbauer, Veronika last_name: Loitzenbauer citation: 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' 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' 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. 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. 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.' 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. short: M.H. Henzinger, S. Krinninger, V. Loitzenbauer, in:, 2nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 713–724. conference: end_date: 2015-07-10 location: Kyoto, Japan name: 'ICALP: International Colloquium on Automata, Languages, and Programming' start_date: 2015-07-06 date_created: 2022-08-11T09:38:34Z date_published: 2015-07-06T00:00:00Z date_updated: 2023-02-10T09:21:47Z day: '06' doi: 10.1007/978-3-662-47672-7_58 extern: '1' external_id: arxiv: - '1412.6466' intvolume: ' 9134' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1412.6466 month: '07' oa: 1 oa_version: Preprint page: 713 - 724 publication: 2nd International Colloquium on Automata, Languages and Programming publication_identifier: isbn: - '9783662476710' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Finding 2-edge and 2-vertex strongly connected components in quadratic time type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 9134 year: '2015' ... --- _id: '11788' abstract: - lang: eng 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 \U0001D445\U0001D434\U0001D437\U0001D44B+\U0001D445\U0001D434(1−1/\U0001D452), where \U0001D445\U0001D434\U0001D437\U0001D44B is the revenue that the optimum algorithm achieves from the ad exchange and \U0001D445\U0001D434 is the revenue that the optimum algorithm achieves from the contracted advertisers." alternative_title: - LNCS article_processing_charge: No author: - first_name: Wolfgang full_name: Dvořák, Wolfgang last_name: Dvořák - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 citation: 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' 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. 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. 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.' 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. short: W. Dvořák, M.H. Henzinger, in:, 12th International Workshop of Approximation and Online Algorithms, Springer Nature, 2015, pp. 156–167. conference: end_date: 2014-09-12 location: Wroclaw, Poland name: 'WAOA: International Workshop on Approximation and Online Algorithms' start_date: 2014-09-11 date_created: 2022-08-11T09:43:32Z date_published: 2015-01-01T00:00:00Z date_updated: 2023-02-10T09:26:06Z day: '01' doi: 10.1007/978-3-319-18263-6_14 extern: '1' external_id: arxiv: - '1604.05603' intvolume: ' 8952' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1604.05603 month: '01' oa: 1 oa_version: Preprint page: 156–167 publication: 12th International Workshop of Approximation and Online Algorithms publication_identifier: issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Online ad assignment with an ad exchange type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 8952 year: '2015' ... --- _id: '11786' 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 \U0001D442(\U0001D4532)-approximately optimal solution in \U0001D442(\U0001D453⋅log(\U0001D45A+\U0001D45B)) amortized update time, where \U0001D453 is the maximum “frequency” of an element, \U0001D45B is the number of sets, and \U0001D45A is the maximum number of elements in the universe at any point in time. (2) For the dynamic \U0001D44F-matching problem, we maintain an \U0001D442(1)-approximately optimal solution in \U0001D442(log3\U0001D45B) amortized update time, where \U0001D45B is the number of nodes in the graph." alternative_title: - LNCS article_processing_charge: No author: - first_name: Sayan full_name: Bhattacharya, Sayan last_name: Bhattacharya - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Giuseppe F. full_name: Italiano, Giuseppe F. last_name: Italiano citation: 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' 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' 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. 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. 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.' 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. short: S. Bhattacharya, M.H. Henzinger, G.F. Italiano, in:, 42nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 206–218. conference: end_date: 2015-07-10 location: Kyoto, Japan name: 'ICALP: International Colloquium on Automata, Languages, and Programming' start_date: 2015-07-06 date_created: 2022-08-11T09:28:49Z date_published: 2015-01-01T00:00:00Z date_updated: 2023-02-10T09:13:31Z day: '01' doi: 10.1007/978-3-662-47672-7_17 extern: '1' external_id: arxiv: - '1604.05337' intvolume: ' 9134' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1604.05337 month: '01' oa: 1 oa_version: Preprint page: 206 - 218 publication: 42nd International Colloquium on Automata, Languages and Programming publication_identifier: isbn: - '9783662476710' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Design of dynamic algorithms via primal-dual method type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 9134 year: '2015' ... --- _id: '11845' 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." article_processing_charge: No article_type: original author: - first_name: Olga full_name: Chernomor, Olga last_name: Chernomor - first_name: Bui Quang full_name: Minh, Bui Quang last_name: Minh - first_name: Félix full_name: Forest, Félix last_name: Forest - first_name: Steffen full_name: Klaere, Steffen last_name: Klaere - first_name: Travis full_name: Ingram, Travis last_name: Ingram - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Arndt full_name: von Haeseler, Arndt last_name: von Haeseler citation: 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 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 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. 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. 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. 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. date_created: 2022-08-16T06:43:49Z date_published: 2015-01-01T00:00:00Z date_updated: 2023-02-17T09:30:08Z day: '01' ddc: - '570' doi: 10.1111/2041-210x.12299 extern: '1' external_id: pmid: - '25893087' file: - access_level: open_access checksum: 880e78f09f0ac99cb351c48dc97623b6 content_type: application/pdf creator: asandaue date_created: 2022-08-16T06:52:53Z date_updated: 2022-08-16T06:52:53Z file_id: '11846' file_name: 2015_MethodsInEcologyAndEvolutionChernomor.pdf file_size: 411415 relation: main_file success: 1 file_date_updated: 2022-08-16T06:52:53Z has_accepted_license: '1' intvolume: ' 6' issue: '1' language: - iso: eng month: '01' oa: 1 oa_version: Published Version page: 83-91 pmid: 1 publication: Methods in Ecology and Evolution publication_identifier: eissn: - 2041-210X publication_status: published publisher: Wiley quality_controlled: '1' scopus_import: '1' status: public title: Split diversity in constrained conservation prioritization using integer linear programming tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 6 year: '2015' ...