---
_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'
...