---
_id: '11657'
abstract:
- lang: eng
text: The minimum cut problem for an undirected edge-weighted graph asks us to divide
its set of nodes into two blocks while minimizing the weight sum of the cut edges.
Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm
is based on cluster contraction using label propagation and Padberg and Rinaldi’s
contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory
parallel implementations of our algorithm. Extensive experiments on both real-world
and generated instances show that our algorithm finds the optimal cut on nearly
all instances significantly faster than other state-of-the-art exact algorithms,
and our error rate is lower than that of other heuristic algorithms. In addition,
our parallel algorithm runs a factor 7.5× faster on average when using 32 threads.
To further speed up computations, we also give a version of our algorithm that
performs random edge contractions as preprocessing. This version achieves a lower
running time and better parallel scalability at the expense of a higher error
rate.
article_processing_charge: No
article_type: original
arxiv: 1
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: Alexander
full_name: Noe, Alexander
last_name: Noe
- first_name: Christian
full_name: Schulz, Christian
last_name: Schulz
- first_name: Darren
full_name: Strash, Darren
last_name: Strash
citation:
ama: Henzinger MH, Noe A, Schulz C, Strash D. Practical minimum cut algorithms.
ACM Journal of Experimental Algorithmics. 2018;23:1-22. doi:10.1145/3274662
apa: Henzinger, M. H., Noe, A., Schulz, C., & Strash, D. (2018). Practical minimum
cut algorithms. ACM Journal of Experimental Algorithmics. Association for
Computing Machinery. https://doi.org/10.1145/3274662
chicago: Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash.
“Practical Minimum Cut Algorithms.” ACM Journal of Experimental Algorithmics.
Association for Computing Machinery, 2018. https://doi.org/10.1145/3274662.
ieee: 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.
ista: Henzinger MH, Noe A, Schulz C, Strash D. 2018. Practical minimum cut algorithms.
ACM Journal of Experimental Algorithmics. 23, 1–22.
mla: Henzinger, Monika H., et al. “Practical Minimum Cut Algorithms.” ACM Journal
of Experimental Algorithmics, vol. 23, Association for Computing Machinery,
2018, pp. 1–22, doi:10.1145/3274662.
short: M.H. Henzinger, A. Noe, C. Schulz, D. Strash, ACM Journal of Experimental
Algorithmics 23 (2018) 1–22.
date_created: 2022-07-27T08:28:26Z
date_published: 2018-10-01T00:00:00Z
date_updated: 2022-09-09T11:32:52Z
day: '01'
doi: 10.1145/3274662
extern: '1'
external_id:
arxiv:
- '1708.06127'
intvolume: ' 23'
keyword:
- Theoretical Computer Science
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1708.06127
month: '10'
oa: 1
oa_version: Preprint
page: 1-22
publication: ACM Journal of Experimental Algorithmics
publication_identifier:
eissn:
- 1084-6654
issn:
- 1084-6654
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Practical minimum cut algorithms
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 23
year: '2018'
...
---
_id: '11664'
abstract:
- lang: eng
text: "We present a deterministic incremental algorithm for exactly maintaining
the size of a minimum cut with O(log3 n log log2 n) amortized time per edge insertion
and O(1) query time. This result partially answers an open question posed by Thorup
(2007). It also stays in sharp contrast to a polynomial conditional lower bound
for the fully dynamic weighted minimum cut problem. Our algorithm is obtained
by combining a sparsification technique of Kawarabayashi and Thorup (2015) or
its recent improvement by Henzinger, Rao, and Wang (2017), and an exact incremental
algorithm of Henzinger (1997).\r\n\r\nWe also study space-efficient incremental
algorithms for the minimum cut problem. Concretely, we show that there exists
an O(nlog n/ε2) space Monte Carlo algorithm that can process a stream of edge
insertions starting from an empty graph, and with high probability, the algorithm
maintains a (1+ε)-approximation to the minimum cut. The algorithm has O((α (n)
log3 n)/ε 2) amortized update time and constant query time, where α (n) stands
for the inverse of Ackermann function."
acknowledgement: "We thank the two anonymous reviewers for their suggestions and comments,
which improved the\r\nquality of the article."
article_number: '17'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Gramoz
full_name: Goranci, Gramoz
last_name: Goranci
- 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: Mikkel
full_name: Thorup, Mikkel
last_name: Thorup
citation:
ama: Goranci G, Henzinger MH, Thorup M. Incremental exact min-cut in polylogarithmic
amortized update time. ACM Transactions on Algorithms. 2018;14(2). doi:10.1145/3174803
apa: Goranci, G., Henzinger, M. H., & Thorup, M. (2018). Incremental exact min-cut
in polylogarithmic amortized update time. ACM Transactions on Algorithms.
Association for Computing Machinery. https://doi.org/10.1145/3174803
chicago: Goranci, Gramoz, Monika H Henzinger, and Mikkel Thorup. “Incremental Exact
Min-Cut in Polylogarithmic Amortized Update Time.” ACM Transactions on Algorithms.
Association for Computing Machinery, 2018. https://doi.org/10.1145/3174803.
ieee: 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.
ista: Goranci G, Henzinger MH, Thorup M. 2018. Incremental exact min-cut in polylogarithmic
amortized update time. ACM Transactions on Algorithms. 14(2), 17.
mla: Goranci, Gramoz, et al. “Incremental Exact Min-Cut in Polylogarithmic Amortized
Update Time.” ACM Transactions on Algorithms, vol. 14, no. 2, 17, Association
for Computing Machinery, 2018, doi:10.1145/3174803.
short: G. Goranci, M.H. Henzinger, M. Thorup, ACM Transactions on Algorithms 14
(2018).
date_created: 2022-07-27T11:29:39Z
date_published: 2018-04-01T00:00:00Z
date_updated: 2022-09-09T11:38:14Z
day: '01'
doi: 10.1145/3174803
extern: '1'
external_id:
arxiv:
- '1611.06500'
intvolume: ' 14'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1611.06500
month: '04'
oa: 1
oa_version: Preprint
publication: ACM Transactions on Algorithms
publication_identifier:
eissn:
- 1549-6333
issn:
- 1549-6325
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Incremental exact min-cut in polylogarithmic amortized update time
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14
year: '2018'
...
---
_id: '11667'
abstract:
- lang: eng
text: The focus of classic mechanism design has been on truthful direct-revelation
mechanisms. In the context of combinatorial auctions, the truthful direct-revelation
mechanism that maximizes social welfare is the Vickrey-Clarke-Groves mechanism.
For many valuation spaces, computing the allocation and payments of the VCG mechanism,
however, is a computationally hard problem. We thus study the performance of the
VCG mechanism when bidders are forced to choose bids from a subspace of the valuation
space for which the VCG outcome can be computed efficiently. We prove improved
upper bounds on the welfare loss for restrictions to additive bids and upper and
lower bounds for restrictions to non-additive bids. These bounds show that increased
expressiveness can give rise to additional equilibria of poorer efficiency.
article_number: '5'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Paul
full_name: Dütting, Paul
last_name: Dütting
- 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: Martin
full_name: Starnberger, Martin
last_name: Starnberger
citation:
ama: Dütting P, Henzinger MH, Starnberger M. Valuation compressions in VCG-based
combinatorial auctions. ACM Transactions on Economics and Computation.
2018;6(2). doi:10.1145/3232860
apa: Dütting, P., Henzinger, M. H., & Starnberger, M. (2018). Valuation compressions
in VCG-based combinatorial auctions. ACM Transactions on Economics and Computation.
Association for Computing Machinery. https://doi.org/10.1145/3232860
chicago: Dütting, Paul, Monika H Henzinger, and Martin Starnberger. “Valuation Compressions
in VCG-Based Combinatorial Auctions.” ACM Transactions on Economics and Computation.
Association for Computing Machinery, 2018. https://doi.org/10.1145/3232860.
ieee: 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.
ista: Dütting P, Henzinger MH, Starnberger M. 2018. Valuation compressions in VCG-based
combinatorial auctions. ACM Transactions on Economics and Computation. 6(2), 5.
mla: Dütting, Paul, et al. “Valuation Compressions in VCG-Based Combinatorial Auctions.”
ACM Transactions on Economics and Computation, vol. 6, no. 2, 5, Association
for Computing Machinery, 2018, doi:10.1145/3232860.
short: P. Dütting, M.H. Henzinger, M. Starnberger, ACM Transactions on Economics
and Computation 6 (2018).
date_created: 2022-07-27T11:46:46Z
date_published: 2018-05-01T00:00:00Z
date_updated: 2022-09-09T12:04:42Z
day: '01'
doi: 10.1145/3232860
extern: '1'
external_id:
arxiv:
- '1310.3153'
intvolume: ' 6'
issue: '2'
keyword:
- Theory of computation
- Algorithmic game theory and mechanism design
- Applied computing
- Economics
- Simplified mechanisms
- Combinatorial auctions with item bidding
- Price of anarchy
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1310.3153
month: '05'
oa: 1
oa_version: Preprint
publication: ACM Transactions on Economics and Computation
publication_identifier:
eissn:
- 2167-8383
issn:
- 2167-8375
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Valuation compressions in VCG-based combinatorial auctions
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6
year: '2018'
...
---
_id: '11757'
abstract:
- lang: eng
text: 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 O ( f 2)-approximately optimal solution in O ( f · log(m + n))
amortized update time, where f is the maximum “frequency” of an element, n is
the number of sets, and m is the maximum number of elements in the universe at
any point in time. (2) For the dynamic b-matching problem, we maintain an O (1)-approximately
optimal solution in O (log3 n) amortized update time, where n is the number of
nodes in the graph.
article_processing_charge: No
article_type: original
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
full_name: Italiano, Giuseppe
last_name: Italiano
citation:
ama: Bhattacharya S, Henzinger MH, Italiano G. Dynamic algorithms via the primal-dual
method. Information and Computation. 2018;261(08):219-239. doi:10.1016/j.ic.2018.02.005
apa: Bhattacharya, S., Henzinger, M. H., & Italiano, G. (2018). Dynamic algorithms
via the primal-dual method. Information and Computation. Elsevier. https://doi.org/10.1016/j.ic.2018.02.005
chicago: Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe Italiano. “Dynamic
Algorithms via the Primal-Dual Method.” Information and Computation. Elsevier,
2018. https://doi.org/10.1016/j.ic.2018.02.005.
ieee: 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.
ista: Bhattacharya S, Henzinger MH, Italiano G. 2018. Dynamic algorithms via the
primal-dual method. Information and Computation. 261(08), 219–239.
mla: Bhattacharya, Sayan, et al. “Dynamic Algorithms via the Primal-Dual Method.”
Information and Computation, vol. 261, no. 08, Elsevier, 2018, pp. 219–39,
doi:10.1016/j.ic.2018.02.005.
short: S. Bhattacharya, M.H. Henzinger, G. Italiano, Information and Computation
261 (2018) 219–239.
date_created: 2022-08-08T11:20:03Z
date_published: 2018-08-01T00:00:00Z
date_updated: 2023-02-10T07:27:39Z
day: '01'
doi: 10.1016/j.ic.2018.02.005
extern: '1'
intvolume: ' 261'
issue: '08'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1016/j.ic.2018.02.005
month: '08'
oa: 1
oa_version: Published Version
page: 219-239
publication: Information and Computation
publication_identifier:
issn:
- 0890-5401
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamic algorithms via the primal-dual method
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 261
year: '2018'
...
---
_id: '11768'
abstract:
- lang: eng
text: "In the decremental single-source shortest paths (SSSP) problem, we want to
maintain the distances between a given source node s and every other node in an
n-node m-edge graph G undergoing edge deletions. While its static counterpart
can be solved in near-linear time, this decremental problem is much more challenging
even in the undirected unweighted case. In this case, the classic O(mn) total
update time of Even and Shiloach [16] has been the fastest known algorithm for
three decades. At the cost of a (1+ϵ)-approximation factor, the running time was
recently improved to n2+o(1) by Bernstein and Roditty [9]. In this article, we
bring the running time down to near-linear: We give a (1+ϵ)-approximation algorithm
with m1+o(1) expected total update time, thus obtaining near-linear time. Moreover,
we obtain m1+o(1) log W time for the weighted case, where the edge weights are
integers from 1 to W. The only prior work on weighted graphs in o(mn) time is
the mn0.9 + o(1)-time algorithm by Henzinger et al. [18, 19], which works for
directed graphs with quasi-polynomial edge weights. The expected running time
bound of our algorithm holds against an oblivious adversary.\r\n\r\nIn contrast
to the previous results, which rely on maintaining a sparse emulator, our algorithm
relies on maintaining a so-called sparse (h, ϵ)-hop set introduced by Cohen [12]
in the PRAM literature. An (h, ϵ)-hop set of a graph G=(V, E) is a set F of weighted
edges such that the distance between any pair of nodes in G can be (1+ϵ)-approximated
by their h-hop distance (given by a path containing at most h edges) on G′=(V,
E ∪ F). Our algorithm can maintain an (no(1), ϵ)-hop set of near-linear size in
near-linear time under edge deletions. It is the first of its kind to the best
of our knowledge. To maintain approximate distances using this hop set, we extend
the monotone Even-Shiloach tree of Henzinger et al. [20] and combine it with the
bounded-hop SSSP technique of Bernstein [4, 5] and Mądry [27]. These two new tools
might be of independent interest."
article_processing_charge: No
article_type: original
arxiv: 1
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. Decremental single-source shortest
paths on undirected graphs in near-linear total update time. Journal of the
ACM. 2018;65(6):1-40. doi:10.1145/3218657
apa: Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2018). Decremental single-source
shortest paths on undirected graphs in near-linear total update time. Journal
of the ACM. Association for Computing Machinery. https://doi.org/10.1145/3218657
chicago: Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Decremental
Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update
Time.” Journal of the ACM. Association for Computing Machinery, 2018. https://doi.org/10.1145/3218657.
ieee: 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.
ista: Henzinger MH, Krinninger S, Nanongkai D. 2018. Decremental single-source shortest
paths on undirected graphs in near-linear total update time. Journal of the ACM.
65(6), 1–40.
mla: Henzinger, Monika H., et al. “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, 2018, pp. 1–40, doi:10.1145/3218657.
short: M.H. Henzinger, S. Krinninger, D. Nanongkai, Journal of the ACM 65 (2018)
1–40.
date_created: 2022-08-08T12:33:17Z
date_published: 2018-12-01T00:00:00Z
date_updated: 2023-02-21T16:30:41Z
day: '01'
doi: 10.1145/3218657
extern: '1'
external_id:
arxiv:
- '1512.08148'
intvolume: ' 65'
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1512.08148
month: '12'
oa: 1
oa_version: Preprint
page: 1-40
publication: Journal of the ACM
publication_identifier:
eissn:
- 1557-735X
issn:
- 0004-5411
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '11855'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Decremental single-source shortest paths on undirected graphs in near-linear
total update time
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 65
year: '2018'
...
---
_id: '11827'
abstract:
- lang: eng
text: We study the metric facility location problem with client insertions and deletions.
This setting differs from the classic dynamic facility location problem, where
the set of clients remains the same, but the metric space can change over time.
We show a deterministic algorithm that maintains a constant factor approximation
to the optimal solution in worst-case time O~(2^{O(kappa^2)}) per client insertion
or deletion in metric spaces while answering queries about the cost in O(1) time,
where kappa denotes the doubling dimension of the metric. For metric spaces with
bounded doubling dimension, the update time is polylogarithmic in the parameters
of the problem.
alternative_title:
- LIPIcs
article_number: '39'
article_processing_charge: No
arxiv: 1
author:
- first_name: 'Gramoz '
full_name: 'Goranci, Gramoz '
last_name: Goranci
- 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: Dariusz
full_name: Leniowski, Dariusz
last_name: Leniowski
citation:
ama: 'Goranci G, Henzinger MH, Leniowski D. A tree structure for dynamic facility
location. In: 26th Annual European Symposium on Algorithms. Vol 112. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPICS.ESA.2018.39'
apa: 'Goranci, G., Henzinger, M. H., & Leniowski, D. (2018). A tree structure
for dynamic facility location. In 26th Annual European Symposium on Algorithms
(Vol. 112). Helsinki, Finland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPICS.ESA.2018.39'
chicago: Goranci, Gramoz , Monika H Henzinger, and Dariusz Leniowski. “A Tree Structure
for Dynamic Facility Location.” In 26th Annual European Symposium on Algorithms,
Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPICS.ESA.2018.39.
ieee: 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.
ista: 'Goranci G, Henzinger MH, Leniowski D. 2018. A tree structure for dynamic
facility location. 26th Annual European Symposium on Algorithms. ESA: Annual European
Symposium on Algorithms, LIPIcs, vol. 112, 39.'
mla: Goranci, Gramoz, et al. “A Tree Structure for Dynamic Facility Location.” 26th
Annual European Symposium on Algorithms, vol. 112, 39, Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPICS.ESA.2018.39.
short: G. Goranci, M.H. Henzinger, D. Leniowski, in:, 26th Annual European Symposium
on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
conference:
end_date: 2018-08-22
location: Helsinki, Finland
name: 'ESA: Annual European Symposium on Algorithms'
start_date: 2018-08-20
date_created: 2022-08-12T08:20:57Z
date_published: 2018-08-14T00:00:00Z
date_updated: 2023-02-16T10:50:51Z
day: '14'
doi: 10.4230/LIPICS.ESA.2018.39
extern: '1'
external_id:
arxiv:
- '1909.06653'
intvolume: ' 112'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPIcs.ESA.2018.39
month: '08'
oa: 1
oa_version: Published Version
publication: 26th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783959770811'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: A tree structure for dynamic facility location
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 112
year: '2018'
...
---
_id: '11828'
abstract:
- lang: eng
text: "We consider the problem of dynamically maintaining (approximate) all-pairs
effective resistances in separable graphs, which are those that admit an n^{c}-separator
theorem for some c<1. We give a fully dynamic algorithm that maintains (1+epsilon)-approximations
of the all-pairs effective resistances of an n-vertex graph G undergoing edge
insertions and deletions with O~(sqrt{n}/epsilon^2) worst-case update time and
O~(sqrt{n}/epsilon^2) worst-case query time, if G is guaranteed to be sqrt{n}-separable
(i.e., it is taken from a class satisfying a sqrt{n}-separator theorem) and its
separator can be computed in O~(n) time. Our algorithm is built upon a dynamic
algorithm for maintaining approximate Schur complement that approximately preserves
pairwise effective resistances among a set of terminals for separable graphs,
which might be of independent interest.\r\nWe complement our result by proving
that for any two fixed vertices s and t, no incremental or decremental algorithm
can maintain the s-t effective resistance for sqrt{n}-separable graphs with worst-case
update time O(n^{1/2-delta}) and query time O(n^{1-delta}) for any delta>0, unless
the Online Matrix Vector Multiplication (OMv) conjecture is false.\r\nWe further
show that for general graphs, no incremental or decremental algorithm can maintain
the s-t effective resistance problem with worst-case update time O(n^{1-delta})
and query-time O(n^{2-delta}) for any delta >0, unless the OMv conjecture is false."
alternative_title:
- LIPIcs
article_number: '40'
article_processing_charge: No
arxiv: 1
author:
- first_name: Gramoz
full_name: Goranci, Gramoz
last_name: Goranci
- 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: Pan
full_name: Peng, Pan
last_name: Peng
citation:
ama: 'Goranci G, Henzinger MH, Peng P. Dynamic effective resistances and approximate
schur complement on separable graphs. In: 26th Annual European Symposium on
Algorithms. Vol 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018.
doi:10.4230/LIPICS.ESA.2018.40'
apa: 'Goranci, G., Henzinger, M. H., & Peng, P. (2018). Dynamic effective resistances
and approximate schur complement on separable graphs. In 26th Annual European
Symposium on Algorithms (Vol. 112). Helsinki, Finland: Schloss Dagstuhl -
Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ESA.2018.40'
chicago: Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “Dynamic Effective Resistances
and Approximate Schur Complement on Separable Graphs.” In 26th Annual European
Symposium on Algorithms, Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2018. https://doi.org/10.4230/LIPICS.ESA.2018.40.
ieee: 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.
ista: 'Goranci G, Henzinger MH, Peng P. 2018. Dynamic effective resistances and
approximate schur complement on separable graphs. 26th Annual European Symposium
on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 112,
40.'
mla: Goranci, Gramoz, et al. “Dynamic Effective Resistances and Approximate Schur
Complement on Separable Graphs.” 26th Annual European Symposium on Algorithms,
vol. 112, 40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPICS.ESA.2018.40.
short: G. Goranci, M.H. Henzinger, P. Peng, in:, 26th Annual European Symposium
on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
conference:
end_date: 2018-08-22
location: Helsinki, Finland
name: 'ESA: Annual European Symposium on Algorithms'
start_date: 2018-08-20
date_created: 2022-08-12T08:26:42Z
date_published: 2018-08-14T00:00:00Z
date_updated: 2023-02-16T11:08:08Z
day: '14'
doi: 10.4230/LIPICS.ESA.2018.40
extern: '1'
external_id:
arxiv:
- '1802.09111'
intvolume: ' 112'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPIcs.ESA.2018.40
month: '08'
oa: 1
oa_version: Published Version
publication: 26th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783959770811'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamic effective resistances and approximate schur complement on separable
graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 112
year: '2018'
...
---
_id: '11872'
abstract:
- lang: eng
text: We design fast dynamic algorithms for proper vertex and edge colorings in
a graph undergoing edge insertions and deletions. In the static setting, there
are simple linear time algorithms for (Δ + 1)- vertex coloring and (2Δ – 1)-edge
coloring in a graph with maximum degree Δ. It is natural to ask if we can efficiently
maintain such colorings in the dynamic setting as well. We get the following three
results. (1) We present a randomized algorithm which maintains a (Δ + 1)-vertex
coloring with O(log Δ) expected amortized update time. (2) We present a deterministic
algorithm which maintains a (1 + o(1)Δ-vertex coloring with O(polylog Δ) amortized
update time. (3) We present a simple, deterministic algorithm which maintains
a (2Δ – 1)-edge coloring with O(log Δ) worst-case update time. This improves the
recent O(Δ)-edge coloring algorithm with worst-case update time [4].
article_processing_charge: No
arxiv: 1
author:
- first_name: Sayan
full_name: Bhattacharya, Sayan
last_name: Bhattacharya
- first_name: Deeparnab
full_name: Chakrabarty, Deeparnab
last_name: Chakrabarty
- 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: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
citation:
ama: 'Bhattacharya S, Chakrabarty D, Henzinger MH, Nanongkai D. Dynamic algorithms
for graph coloring. In: 29th Annual ACM-SIAM Symposium on Discrete Algorithms.
Society for Industrial and Applied Mathematics; 2018:1-20. doi:10.1137/1.9781611975031.1'
apa: 'Bhattacharya, S., Chakrabarty, D., Henzinger, M. H., & Nanongkai, D. (2018).
Dynamic algorithms for graph coloring. In 29th Annual ACM-SIAM Symposium on
Discrete Algorithms (pp. 1–20). New Orleans, LA, United States: Society for
Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611975031.1'
chicago: Bhattacharya, Sayan, Deeparnab Chakrabarty, Monika H Henzinger, and Danupon
Nanongkai. “Dynamic Algorithms for Graph Coloring.” In 29th Annual ACM-SIAM
Symposium on Discrete Algorithms, 1–20. Society for Industrial and Applied
Mathematics, 2018. https://doi.org/10.1137/1.9781611975031.1.
ieee: 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.
ista: 'Bhattacharya S, Chakrabarty D, Henzinger MH, Nanongkai D. 2018. Dynamic algorithms
for graph coloring. 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA:
Symposium on Discrete Algorithms, 1–20.'
mla: Bhattacharya, Sayan, et al. “Dynamic Algorithms for Graph Coloring.” 29th
Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and
Applied Mathematics, 2018, pp. 1–20, doi:10.1137/1.9781611975031.1.
short: S. Bhattacharya, D. Chakrabarty, M.H. Henzinger, D. Nanongkai, in:, 29th
Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied
Mathematics, 2018, pp. 1–20.
conference:
end_date: 2018-01-10
location: New Orleans, LA, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2018-01-07
date_created: 2022-08-16T12:07:14Z
date_published: 2018-01-01T00:00:00Z
date_updated: 2023-02-17T11:39:01Z
day: '01'
doi: 10.1137/1.9781611975031.1
extern: '1'
external_id:
arxiv:
- '1711.04355'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1711.04355
month: '01'
oa: 1
oa_version: Preprint
page: 1 - 20
publication: 29th Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
eisbn:
- 978-161197503-1
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamic algorithms for graph coloring
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2018'
...
---
_id: '11882'
abstract:
- lang: eng
text: The minimum cut problem for an undirected edge-weighted graph asks us to divide
its set of nodes into two blocks while minimizing the weight sum of the cut edges.
Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm
is based on cluster contraction using label propagation and Padberg and Rinaldi's
contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory
parallel implementations of our algorithm. Extensive experiments on both real-world
and generated instances show that our algorithm finds the optimal cut on nearly
all instances significantly faster than other state-of-the-art exact algorithms,
and our error rate is lower than that of other heuristic algorithms. In addition,
our parallel algorithm shows good scalability.
article_processing_charge: No
arxiv: 1
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: Alexander
full_name: Noe, Alexander
last_name: Noe
- first_name: Christian
full_name: Schulz, Christian
last_name: Schulz
- first_name: Darren
full_name: Strash, Darren
last_name: Strash
citation:
ama: 'Henzinger MH, Noe A, Schulz C, Strash D. Practical minimum cut algorithms.
In: 20th Workshop on Algorithm Engineering and Experiments. Society for
Industrial and Applied Mathematics; 2018:48-61. doi:10.1137/1.9781611975055.5'
apa: 'Henzinger, M. H., Noe, A., Schulz, C., & Strash, D. (2018). Practical
minimum cut algorithms. In 20th Workshop on Algorithm Engineering and Experiments
(pp. 48–61). New Orleans, LA, United States: Society for Industrial and Applied
Mathematics. https://doi.org/10.1137/1.9781611975055.5'
chicago: Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash.
“Practical Minimum Cut Algorithms.” In 20th Workshop on Algorithm Engineering
and Experiments, 48–61. Society for Industrial and Applied Mathematics, 2018.
https://doi.org/10.1137/1.9781611975055.5.
ieee: 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.
ista: 'Henzinger MH, Noe A, Schulz C, Strash D. 2018. Practical minimum cut algorithms.
20th Workshop on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm
Engineering and Experiments, 48–61.'
mla: Henzinger, Monika H., et al. “Practical Minimum Cut Algorithms.” 20th Workshop
on Algorithm Engineering and Experiments, Society for Industrial and Applied
Mathematics, 2018, pp. 48–61, doi:10.1137/1.9781611975055.5.
short: M.H. Henzinger, A. Noe, C. Schulz, D. Strash, in:, 20th Workshop on Algorithm
Engineering and Experiments, Society for Industrial and Applied Mathematics, 2018,
pp. 48–61.
conference:
end_date: 2018-01-08
location: New Orleans, LA, United States
name: 'ALENEX: Symposium on Algorithm Engineering and Experiments'
start_date: 2018-01-07
date_created: 2022-08-17T07:04:57Z
date_published: 2018-01-01T00:00:00Z
date_updated: 2023-02-17T14:03:39Z
day: '01'
doi: 10.1137/1.9781611975055.5
extern: '1'
external_id:
arxiv:
- '1708.06127'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1708.06127
month: '01'
oa: 1
oa_version: Preprint
page: 48-61
publication: 20th Workshop on Algorithm Engineering and Experiments
publication_identifier:
eisbn:
- 978-1-61197-505-5
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Practical minimum cut algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2018'
...
---
_id: '11890'
abstract:
- lang: eng
text: "We present the first deterministic data structures for maintaining approximate
minimum vertex cover and maximum matching in a fully dynamic graph \U0001D43A=(\U0001D449,\U0001D438),
with |\U0001D449|=\U0001D45B and |\U0001D438|=\U0001D45A, in \U0001D45C(\U0001D45A‾‾√)
time per update. In particular, for minimum vertex cover, we provide deterministic
data structures for maintaining a (2+\U0001D716) approximation in \U0001D442(log\U0001D45B/\U0001D7162)
amortized time per update. For maximum matching, we show how to maintain a (3+\U0001D716)
approximation in \U0001D442(min(\U0001D45B√/\U0001D716,\U0001D45A1/3/\U0001D7162)
amortized time per update and a (4+\U0001D716) approximation in \U0001D442(\U0001D45A1/3/\U0001D7162)
worst-case time per update. Our data structure for fully dynamic minimum vertex
cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld
[in 42nd ACM Symposium on Theory of Computing, Cambridge, MA, ACM, 2010, pp. 457--464]."
article_processing_charge: No
article_type: original
arxiv: 1
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. Deterministic fully dynamic data
structures for vertex cover and matching. SIAM Journal on Computing. 2018;47(3):859-887.
doi:10.1137/140998925
apa: Bhattacharya, S., Henzinger, M. H., & Italiano, G. F. (2018). Deterministic
fully dynamic data structures for vertex cover and matching. SIAM Journal on
Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/140998925
chicago: Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe F. Italiano. “Deterministic
Fully Dynamic Data Structures for Vertex Cover and Matching.” SIAM Journal
on Computing. Society for Industrial & Applied Mathematics, 2018. https://doi.org/10.1137/140998925.
ieee: 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.
ista: Bhattacharya S, Henzinger MH, Italiano GF. 2018. Deterministic fully dynamic
data structures for vertex cover and matching. SIAM Journal on Computing. 47(3),
859–887.
mla: Bhattacharya, Sayan, et al. “Deterministic Fully Dynamic Data Structures for
Vertex Cover and Matching.” SIAM Journal on Computing, vol. 47, no. 3,
Society for Industrial & Applied Mathematics, 2018, pp. 859–87, doi:10.1137/140998925.
short: S. Bhattacharya, M.H. Henzinger, G.F. Italiano, SIAM Journal on Computing
47 (2018) 859–887.
date_created: 2022-08-17T08:21:23Z
date_published: 2018-05-01T00:00:00Z
date_updated: 2023-02-21T16:31:30Z
day: '01'
doi: 10.1137/140998925
extern: '1'
external_id:
arxiv:
- '1412.1318'
intvolume: ' 47'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1412.1318
month: '05'
oa: 1
oa_version: Preprint
page: 859-887
publication: SIAM Journal on Computing
publication_identifier:
eissn:
- 1095-7111
issn:
- 0097-5397
publication_status: published
publisher: Society for Industrial & Applied Mathematics
quality_controlled: '1'
related_material:
record:
- id: '11875'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Deterministic fully dynamic data structures for vertex cover and matching
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 47
year: '2018'
...
---
_id: '11911'
abstract:
- lang: eng
text: It is common knowledge that there is no single best strategy for graph clustering,
which justifies a plethora of existing approaches. In this paper, we present a
general memetic algorithm, VieClus, to tackle the graph clustering problem. This
algorithm can be adapted to optimize different objective functions. A key component
of our contribution are natural recombine operators that employ ensemble clusterings
as well as multi-level techniques. Lastly, we combine these techniques with a
scalable communication protocol, producing a system that is able to compute high-quality
solutions in a short amount of time. We instantiate our scheme with local search
for modularity and show that our algorithm successfully improves or reproduces
all entries of the 10th DIMACS implementation challenge under consideration using
a small amount of time.
alternative_title:
- LIPIcs
article_number: '3'
article_processing_charge: No
arxiv: 1
author:
- first_name: Sonja
full_name: Biedermann, Sonja
last_name: Biedermann
- 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: Christian
full_name: Schulz, Christian
last_name: Schulz
- first_name: Bernhard
full_name: Schuster, Bernhard
last_name: Schuster
citation:
ama: 'Biedermann S, Henzinger MH, Schulz C, Schuster B. Memetic graph clustering.
In: 17th International Symposium on Experimental Algorithms. Vol 103. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPICS.SEA.2018.3'
apa: 'Biedermann, S., Henzinger, M. H., Schulz, C., & Schuster, B. (2018). Memetic
graph clustering. In 17th International Symposium on Experimental Algorithms
(Vol. 103). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPICS.SEA.2018.3'
chicago: Biedermann, Sonja, Monika H Henzinger, Christian Schulz, and Bernhard Schuster.
“Memetic Graph Clustering.” In 17th International Symposium on Experimental
Algorithms, Vol. 103. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
https://doi.org/10.4230/LIPICS.SEA.2018.3.
ieee: 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.
ista: 'Biedermann S, Henzinger MH, Schulz C, Schuster B. 2018. Memetic graph clustering.
17th International Symposium on Experimental Algorithms. SEA: Symposium on Experimental
Algorithms, LIPIcs, vol. 103, 3.'
mla: Biedermann, Sonja, et al. “Memetic Graph Clustering.” 17th International
Symposium on Experimental Algorithms, vol. 103, 3, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2018, doi:10.4230/LIPICS.SEA.2018.3.
short: S. Biedermann, M.H. Henzinger, C. Schulz, B. Schuster, in:, 17th International
Symposium on Experimental Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2018.
conference:
end_date: 2018-07-29
location: L'Aquila, Italy
name: 'SEA: Symposium on Experimental Algorithms'
start_date: 2018-07-27
date_created: 2022-08-18T06:49:40Z
date_published: 2018-07-01T00:00:00Z
date_updated: 2023-02-16T11:45:14Z
day: '01'
doi: 10.4230/LIPICS.SEA.2018.3
extern: '1'
external_id:
arxiv:
- '1802.07034'
intvolume: ' 103'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPICS.SEA.2018.3
month: '07'
oa: 1
oa_version: Published Version
publication: 17th International Symposium on Experimental Algorithms
publication_identifier:
isbn:
- '9783959770705'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Memetic graph clustering
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 103
year: '2018'
...
---
_id: '11958'
abstract:
- lang: eng
text: Solid reagents, leaching catalysts, and heterogeneous photocatalysts are commonly
employed in batch processes but are ill-suited for continuous-flow chemistry.
Heterogeneous catalysts for thermal reactions are typically used in packed-bed
reactors, which cannot be penetrated by light and thus are not suitable for photocatalytic
reactions involving solids. We demonstrate that serial micro-batch reactors (SMBRs)
allow for the continuous utilization of solid materials together with liquids
and gases in flow. This technology was utilized to develop selective and efficient
fluorination reactions using a modified graphitic carbon nitride heterogeneous
catalyst instead of costly homogeneous metal polypyridyl complexes. The merger
of this inexpensive, recyclable catalyst and the SMBR approach enables sustainable
and scalable photocatalysis.
article_processing_charge: No
article_type: letter_note
author:
- first_name: Bartholomäus
full_name: Pieber, Bartholomäus
id: 93e5e5b2-0da6-11ed-8a41-af589a024726
last_name: Pieber
orcid: 0000-0001-8689-388X
- first_name: Menny
full_name: Shalom, Menny
last_name: Shalom
- first_name: Markus
full_name: Antonietti, Markus
last_name: Antonietti
- first_name: Peter H.
full_name: Seeberger, Peter H.
last_name: Seeberger
- first_name: Kerry
full_name: Gilmore, Kerry
last_name: Gilmore
citation:
ama: Pieber B, Shalom M, Antonietti M, Seeberger PH, Gilmore K. Continuous heterogeneous
photocatalysis in serial micro-batch reactors. Angewandte Chemie International
Edition. 2018;57(31):9976-9979. doi:10.1002/anie.201712568
apa: Pieber, B., Shalom, M., Antonietti, M., Seeberger, P. H., & Gilmore, K.
(2018). Continuous heterogeneous photocatalysis in serial micro-batch reactors.
Angewandte Chemie International Edition. Wiley. https://doi.org/10.1002/anie.201712568
chicago: Pieber, Bartholomäus, Menny Shalom, Markus Antonietti, Peter H. Seeberger,
and Kerry Gilmore. “Continuous Heterogeneous Photocatalysis in Serial Micro-Batch
Reactors.” Angewandte Chemie International Edition. Wiley, 2018. https://doi.org/10.1002/anie.201712568.
ieee: B. Pieber, M. Shalom, M. Antonietti, P. H. Seeberger, and K. Gilmore, “Continuous
heterogeneous photocatalysis in serial micro-batch reactors,” Angewandte Chemie
International Edition, vol. 57, no. 31. Wiley, pp. 9976–9979, 2018.
ista: Pieber B, Shalom M, Antonietti M, Seeberger PH, Gilmore K. 2018. Continuous
heterogeneous photocatalysis in serial micro-batch reactors. Angewandte Chemie
International Edition. 57(31), 9976–9979.
mla: Pieber, Bartholomäus, et al. “Continuous Heterogeneous Photocatalysis in Serial
Micro-Batch Reactors.” Angewandte Chemie International Edition, vol. 57,
no. 31, Wiley, 2018, pp. 9976–79, doi:10.1002/anie.201712568.
short: B. Pieber, M. Shalom, M. Antonietti, P.H. Seeberger, K. Gilmore, Angewandte
Chemie International Edition 57 (2018) 9976–9979.
date_created: 2022-08-24T10:57:25Z
date_published: 2018-07-26T00:00:00Z
date_updated: 2023-02-21T10:09:18Z
day: '26'
doi: 10.1002/anie.201712568
extern: '1'
external_id:
pmid:
- '29377383'
intvolume: ' 57'
issue: '31'
language:
- iso: eng
month: '07'
oa_version: None
page: 9976-9979
pmid: 1
publication: Angewandte Chemie International Edition
publication_identifier:
eissn:
- ' 1521-3773'
issn:
- 1433-7851
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Continuous heterogeneous photocatalysis in serial micro-batch reactors
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 57
year: '2018'
...
---
_id: '12'
abstract:
- lang: eng
text: Molding is a popular mass production method, in which the initial expenses
for the mold are offset by the low per-unit production cost. However, the physical
fabrication constraints of the molding technique commonly restrict the shape of
moldable objects. For a complex shape, a decomposition of the object into moldable
parts is a common strategy to address these constraints, with plastic model kits
being a popular and illustrative example. However, conducting such a decomposition
requires considerable expertise, and it depends on the technical aspects of the
fabrication technique, as well as aesthetic considerations. We present an interactive
technique to create such decompositions for two-piece molding, in which each part
of the object is cast between two rigid mold pieces. Given the surface description
of an object, we decompose its thin-shell equivalent into moldable parts by first
performing a coarse decomposition and then utilizing an active contour model for
the boundaries between individual parts. Formulated as an optimization problem,
the movement of the contours is guided by an energy reflecting fabrication constraints
to ensure the moldability of each part. Simultaneously, the user is provided with
editing capabilities to enforce aesthetic guidelines. Our interactive interface
provides control of the contour positions by allowing, for example, the alignment
of part boundaries with object features. Our technique enables a novel workflow,
as it empowers novice users to explore the design space, and it generates fabrication-ready
two-piece molds that can be used either for casting or industrial injection molding
of free-form objects.
article_number: '135'
article_processing_charge: No
author:
- first_name: Kazutaka
full_name: Nakashima, Kazutaka
last_name: Nakashima
- first_name: Thomas
full_name: Auzinger, Thomas
id: 4718F954-F248-11E8-B48F-1D18A9856A87
last_name: Auzinger
orcid: 0000-0002-1546-3265
- first_name: Emmanuel
full_name: Iarussi, Emmanuel
id: 33F19F16-F248-11E8-B48F-1D18A9856A87
last_name: Iarussi
- first_name: Ran
full_name: Zhang, Ran
id: 4DDBCEB0-F248-11E8-B48F-1D18A9856A87
last_name: Zhang
orcid: 0000-0002-3808-281X
- first_name: Takeo
full_name: Igarashi, Takeo
last_name: Igarashi
- first_name: Bernd
full_name: Bickel, Bernd
id: 49876194-F248-11E8-B48F-1D18A9856A87
last_name: Bickel
orcid: 0000-0001-6511-9385
citation:
ama: 'Nakashima K, Auzinger T, Iarussi E, Zhang R, Igarashi T, Bickel B. CoreCavity:
Interactive shell decomposition for fabrication with two-piece rigid molds. ACM
Transaction on Graphics. 2018;37(4). doi:10.1145/3197517.3201341'
apa: 'Nakashima, K., Auzinger, T., Iarussi, E., Zhang, R., Igarashi, T., & Bickel,
B. (2018). CoreCavity: Interactive shell decomposition for fabrication with two-piece
rigid molds. ACM Transaction on Graphics. ACM. https://doi.org/10.1145/3197517.3201341'
chicago: 'Nakashima, Kazutaka, Thomas Auzinger, Emmanuel Iarussi, Ran Zhang, Takeo
Igarashi, and Bernd Bickel. “CoreCavity: Interactive Shell Decomposition for Fabrication
with Two-Piece Rigid Molds.” ACM Transaction on Graphics. ACM, 2018. https://doi.org/10.1145/3197517.3201341.'
ieee: 'K. Nakashima, T. Auzinger, E. Iarussi, R. Zhang, T. Igarashi, and B. Bickel,
“CoreCavity: Interactive shell decomposition for fabrication with two-piece rigid
molds,” ACM Transaction on Graphics, vol. 37, no. 4. ACM, 2018.'
ista: 'Nakashima K, Auzinger T, Iarussi E, Zhang R, Igarashi T, Bickel B. 2018.
CoreCavity: Interactive shell decomposition for fabrication with two-piece rigid
molds. ACM Transaction on Graphics. 37(4), 135.'
mla: 'Nakashima, Kazutaka, et al. “CoreCavity: Interactive Shell Decomposition for
Fabrication with Two-Piece Rigid Molds.” ACM Transaction on Graphics, vol.
37, no. 4, 135, ACM, 2018, doi:10.1145/3197517.3201341.'
short: K. Nakashima, T. Auzinger, E. Iarussi, R. Zhang, T. Igarashi, B. Bickel,
ACM Transaction on Graphics 37 (2018).
date_created: 2018-12-11T11:44:09Z
date_published: 2018-08-04T00:00:00Z
date_updated: 2023-09-11T12:48:09Z
day: '04'
ddc:
- '004'
- '516'
- '670'
department:
- _id: BeBi
doi: 10.1145/3197517.3201341
ec_funded: 1
external_id:
isi:
- '000448185000096'
file:
- access_level: open_access
checksum: 6a5368bc86c4e1a9fcfe588fd1f14ee8
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:18:38Z
date_updated: 2020-07-14T12:44:38Z
file_id: '5360'
file_name: IST-2018-1037-v1+1_CoreCavity-AuthorVersion.pdf
file_size: 104225664
relation: main_file
- access_level: open_access
checksum: 3861e693ba47c51f3ec7b7867d573a61
content_type: application/zip
creator: system
date_created: 2018-12-12T10:18:39Z
date_updated: 2020-07-14T12:44:38Z
file_id: '5361'
file_name: IST-2018-1037-v1+2_CoreCavity-Supplemental.zip
file_size: 377743553
relation: main_file
- access_level: open_access
checksum: 490040c685ed869536e2a18f5a906b94
content_type: video/vnd.objectvideo
creator: system
date_created: 2018-12-12T10:18:41Z
date_updated: 2020-07-14T12:44:38Z
file_id: '5362'
file_name: IST-2018-1037-v1+3_CoreCavity-Video.mp4
file_size: 162634396
relation: main_file
- access_level: open_access
checksum: be7fc8b229adda727419b6504b3b9352
content_type: image/jpeg
creator: system
date_created: 2018-12-12T10:18:42Z
date_updated: 2020-07-14T12:44:38Z
file_id: '5363'
file_name: IST-2018-1037-v1+4_CoreCavity-RepresentativeImage.jpg
file_size: 527972
relation: main_file
file_date_updated: 2020-07-14T12:44:38Z
has_accepted_license: '1'
intvolume: ' 37'
isi: 1
issue: '4'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
project:
- _id: 24F9549A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '715767'
name: 'MATERIALIZABLE: Intelligent fabrication-oriented Computational Design and
Modeling'
- _id: 2508E324-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '642841'
name: Distributed 3D Object Design
publication: ACM Transaction on Graphics
publication_status: published
publisher: ACM
publist_id: '8044'
pubrep_id: '1037'
quality_controlled: '1'
related_material:
link:
- description: News on IST Homepage
relation: press_release
url: https://ist.ac.at/en/news/interactive-software-tool-makes-complex-mold-design-simple/
scopus_import: '1'
status: public
title: 'CoreCavity: Interactive shell decomposition for fabrication with two-piece
rigid molds'
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 37
year: '2018'
...
---
_id: '21'
abstract:
- lang: eng
text: Parvalbumin-positive (PV+) GABAergic interneurons in hippocampal microcircuits
are thought to play a key role in several higher network functions, such as feedforward
and feedback inhibition, network oscillations, and pattern separation. Fast lateral
inhibition mediated by GABAergic interneurons may implement a winner-takes-all
mechanism in the hippocampal input layer. However, it is not clear whether the
functional connectivity rules of granule cells (GCs) and interneurons in the dentate
gyrus are consistent with such a mechanism. Using simultaneous patch-clamp recordings
from up to seven GCs and up to four PV+ interneurons in the dentate gyrus, we
find that connectivity is structured in space, synapse-specific, and enriched
in specific disynaptic motifs. In contrast to the neocortex, lateral inhibition
in the dentate gyrus (in which a GC inhibits neighboring GCs via a PV+ interneuron)
is ~ 10-times more abundant than recurrent inhibition (in which a GC inhibits
itself). Thus, unique connectivity rules may enable the dentate gyrus to perform
specific higher-order computations
acknowledgement: This project received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No 692692) and the Fond zur Förderung der Wissenschaftlichen Forschung
(Z 312-B27, Wittgenstein award), both to P.J..
article_number: '4605'
article_processing_charge: No
article_type: original
author:
- first_name: 'Claudia '
full_name: 'Espinoza Martinez, Claudia '
id: 31FFEE2E-F248-11E8-B48F-1D18A9856A87
last_name: Espinoza Martinez
orcid: 0000-0003-4710-2082
- first_name: José
full_name: Guzmán, José
id: 30CC5506-F248-11E8-B48F-1D18A9856A87
last_name: Guzmán
orcid: 0000-0003-2209-5242
- first_name: Xiaomin
full_name: Zhang, Xiaomin
id: 423EC9C2-F248-11E8-B48F-1D18A9856A87
last_name: Zhang
- first_name: Peter M
full_name: Jonas, Peter M
id: 353C1B58-F248-11E8-B48F-1D18A9856A87
last_name: Jonas
orcid: 0000-0001-5001-4804
citation:
ama: Espinoza Martinez C, Guzmán J, Zhang X, Jonas PM. Parvalbumin+ interneurons
obey unique connectivity rules and establish a powerful lateral-inhibition microcircuit
in dentate gyrus. Nature Communications. 2018;9(1). doi:10.1038/s41467-018-06899-3
apa: Espinoza Martinez, C., Guzmán, J., Zhang, X., & Jonas, P. M. (2018). Parvalbumin+
interneurons obey unique connectivity rules and establish a powerful lateral-inhibition
microcircuit in dentate gyrus. Nature Communications. Nature Publishing
Group. https://doi.org/10.1038/s41467-018-06899-3
chicago: Espinoza Martinez, Claudia , José Guzmán, Xiaomin Zhang, and Peter M Jonas.
“Parvalbumin+ Interneurons Obey Unique Connectivity Rules and Establish a Powerful
Lateral-Inhibition Microcircuit in Dentate Gyrus.” Nature Communications.
Nature Publishing Group, 2018. https://doi.org/10.1038/s41467-018-06899-3.
ieee: C. Espinoza Martinez, J. Guzmán, X. Zhang, and P. M. Jonas, “Parvalbumin+
interneurons obey unique connectivity rules and establish a powerful lateral-inhibition
microcircuit in dentate gyrus,” Nature Communications, vol. 9, no. 1. Nature
Publishing Group, 2018.
ista: Espinoza Martinez C, Guzmán J, Zhang X, Jonas PM. 2018. Parvalbumin+ interneurons
obey unique connectivity rules and establish a powerful lateral-inhibition microcircuit
in dentate gyrus. Nature Communications. 9(1), 4605.
mla: Espinoza Martinez, Claudia, et al. “Parvalbumin+ Interneurons Obey Unique Connectivity
Rules and Establish a Powerful Lateral-Inhibition Microcircuit in Dentate Gyrus.”
Nature Communications, vol. 9, no. 1, 4605, Nature Publishing Group, 2018,
doi:10.1038/s41467-018-06899-3.
short: C. Espinoza Martinez, J. Guzmán, X. Zhang, P.M. Jonas, Nature Communications
9 (2018).
date_created: 2018-12-11T11:44:12Z
date_published: 2018-11-02T00:00:00Z
date_updated: 2024-03-25T23:30:16Z
day: '02'
ddc:
- '570'
department:
- _id: PeJo
doi: 10.1038/s41467-018-06899-3
ec_funded: 1
external_id:
isi:
- '000449069700009'
file:
- access_level: open_access
checksum: 9fe2a63bd95a5067d896c087d07998f3
content_type: application/pdf
creator: dernst
date_created: 2018-12-17T15:41:57Z
date_updated: 2020-07-14T12:45:28Z
file_id: '5715'
file_name: 2018_NatureComm_Espinoza.pdf
file_size: 4651930
relation: main_file
file_date_updated: 2020-07-14T12:45:28Z
has_accepted_license: '1'
intvolume: ' 9'
isi: 1
issue: '1'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
project:
- _id: 25B7EB9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '692692'
name: Biophysics and circuit function of a giant cortical glumatergic synapse
- _id: 25C5A090-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00312
name: The Wittgenstein Prize
publication: Nature Communications
publication_status: published
publisher: Nature Publishing Group
publist_id: '8034'
quality_controlled: '1'
related_material:
link:
- description: News on IST Homepage
relation: press_release
url: https://ist.ac.at/en/news/lateral-inhibition-keeps-similar-memories-apart/
record:
- id: '6363'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Parvalbumin+ interneurons obey unique connectivity rules and establish a powerful
lateral-inhibition microcircuit in dentate gyrus
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 9
year: '2018'
...
---
_id: '22'
abstract:
- lang: eng
text: Conventional ultra-high sensitivity detectors in the millimeter-wave range
are usually cooled as their own thermal noise at room temperature would mask the
weak received radiation. The need for cryogenic systems increases the cost and
complexity of the instruments, hindering the development of, among others, airborne
and space applications. In this work, the nonlinear parametric upconversion of
millimeter-wave radiation to the optical domain inside high-quality (Q) lithium
niobate whispering-gallery mode (WGM) resonators is proposed for ultra-low noise
detection. We experimentally demonstrate coherent upconversion of millimeter-wave
signals to a 1550 nm telecom carrier, with a photon conversion efficiency surpassing
the state-of-the-art by 2 orders of magnitude. Moreover, a theoretical model shows
that the thermal equilibrium of counterpropagating WGMs is broken by overcoupling
the millimeter-wave WGM, effectively cooling the upconverted mode and allowing
ultra-low noise detection. By theoretically estimating the sensitivity of a correlation
radiometer based on the presented scheme, it is found that room-temperature radiometers
with better sensitivity than state-of-the-art high-electron-mobility transistor
(HEMT)-based radiometers can be designed. This detection paradigm can be used
to develop room-temperature instrumentation for radio astronomy, earth observation,
planetary missions, and imaging systems.
article_processing_charge: No
article_type: original
author:
- first_name: Gabriel
full_name: Botello, Gabriel
last_name: Botello
- first_name: Florian
full_name: Sedlmeir, Florian
last_name: Sedlmeir
- first_name: Alfredo R
full_name: Rueda Sanchez, Alfredo R
id: 3B82B0F8-F248-11E8-B48F-1D18A9856A87
last_name: Rueda Sanchez
orcid: 0000-0001-6249-5860
- first_name: Kerlos
full_name: Abdalmalak, Kerlos
last_name: Abdalmalak
- first_name: Elliott
full_name: Brown, Elliott
last_name: Brown
- first_name: Gerd
full_name: Leuchs, Gerd
last_name: Leuchs
- first_name: Sascha
full_name: Preu, Sascha
last_name: Preu
- first_name: Daniel
full_name: Segovia Vargas, Daniel
last_name: Segovia Vargas
- first_name: Dmitry
full_name: Strekalov, Dmitry
last_name: Strekalov
- first_name: Luis
full_name: Munoz, Luis
last_name: Munoz
- first_name: Harald
full_name: Schwefel, Harald
last_name: Schwefel
citation:
ama: Botello G, Sedlmeir F, Rueda Sanchez AR, et al. Sensitivity limits of millimeter-wave
photonic radiometers based on efficient electro-optic upconverters. Optica.
2018;5(10):1210-1219. doi:10.1364/OPTICA.5.001210
apa: Botello, G., Sedlmeir, F., Rueda Sanchez, A. R., Abdalmalak, K., Brown, E.,
Leuchs, G., … Schwefel, H. (2018). Sensitivity limits of millimeter-wave photonic
radiometers based on efficient electro-optic upconverters. Optica. https://doi.org/10.1364/OPTICA.5.001210
chicago: Botello, Gabriel, Florian Sedlmeir, Alfredo R Rueda Sanchez, Kerlos Abdalmalak,
Elliott Brown, Gerd Leuchs, Sascha Preu, et al. “Sensitivity Limits of Millimeter-Wave
Photonic Radiometers Based on Efficient Electro-Optic Upconverters.” Optica,
2018. https://doi.org/10.1364/OPTICA.5.001210.
ieee: G. Botello et al., “Sensitivity limits of millimeter-wave photonic
radiometers based on efficient electro-optic upconverters,” Optica, vol.
5, no. 10. pp. 1210–1219, 2018.
ista: Botello G, Sedlmeir F, Rueda Sanchez AR, Abdalmalak K, Brown E, Leuchs G,
Preu S, Segovia Vargas D, Strekalov D, Munoz L, Schwefel H. 2018. Sensitivity
limits of millimeter-wave photonic radiometers based on efficient electro-optic
upconverters. Optica. 5(10), 1210–1219.
mla: Botello, Gabriel, et al. “Sensitivity Limits of Millimeter-Wave Photonic Radiometers
Based on Efficient Electro-Optic Upconverters.” Optica, vol. 5, no. 10,
2018, pp. 1210–19, doi:10.1364/OPTICA.5.001210.
short: G. Botello, F. Sedlmeir, A.R. Rueda Sanchez, K. Abdalmalak, E. Brown, G.
Leuchs, S. Preu, D. Segovia Vargas, D. Strekalov, L. Munoz, H. Schwefel, Optica
5 (2018) 1210–1219.
date_created: 2018-12-11T11:44:12Z
date_published: 2018-10-20T00:00:00Z
date_updated: 2023-10-17T12:12:40Z
day: '20'
department:
- _id: JoFi
doi: 10.1364/OPTICA.5.001210
external_id:
isi:
- '000447853100007'
intvolume: ' 5'
isi: 1
issue: '10'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: 'www.doi.org/10.1364/OPTICA.5.001210 '
month: '10'
oa: 1
oa_version: Published Version
page: 1210 - 1219
publication: Optica
publication_identifier:
issn:
- '23342536'
publication_status: published
publist_id: '8033'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Sensitivity limits of millimeter-wave photonic radiometers based on efficient
electro-optic upconverters
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 5
year: '2018'
...
---
_id: '23'
abstract:
- lang: eng
text: The strong atomistic spin–orbit coupling of holes makes single-shot spin readout
measurements difficult because it reduces the spin lifetimes. By integrating the
charge sensor into a high bandwidth radio frequency reflectometry setup, we were
able to demonstrate single-shot readout of a germanium quantum dot hole spin and
measure the spin lifetime. Hole spin relaxation times of about 90 μs at 500 mT
are reported, with a total readout visibility of about 70%. By analyzing separately
the spin-to-charge conversion and charge readout fidelities, we have obtained
insight into the processes limiting the visibilities of hole spins. The analyses
suggest that high hole visibilities are feasible at realistic experimental conditions,
underlying the potential of hole spins for the realization of viable qubit devices.
acknowledged_ssus:
- _id: M-Shop
- _id: NanoFab
article_processing_charge: No
author:
- first_name: Lada
full_name: Vukušić, Lada
id: 31E9F056-F248-11E8-B48F-1D18A9856A87
last_name: Vukušić
orcid: 0000-0003-2424-8636
- first_name: Josip
full_name: Kukucka, Josip
id: 3F5D8856-F248-11E8-B48F-1D18A9856A87
last_name: Kukucka
- first_name: Hannes
full_name: Watzinger, Hannes
id: 35DF8E50-F248-11E8-B48F-1D18A9856A87
last_name: Watzinger
- first_name: Joshua M
full_name: Milem, Joshua M
id: 4CDE0A96-F248-11E8-B48F-1D18A9856A87
last_name: Milem
- first_name: Friedrich
full_name: Schäffler, Friedrich
last_name: Schäffler
- first_name: Georgios
full_name: Katsaros, Georgios
id: 38DB5788-F248-11E8-B48F-1D18A9856A87
last_name: Katsaros
orcid: 0000-0001-8342-202X
citation:
ama: Vukušić L, Kukucka J, Watzinger H, Milem JM, Schäffler F, Katsaros G. Single-shot
readout of hole spins in Ge. Nano Letters. 2018;18(11):7141-7145. doi:10.1021/acs.nanolett.8b03217
apa: Vukušić, L., Kukucka, J., Watzinger, H., Milem, J. M., Schäffler, F., &
Katsaros, G. (2018). Single-shot readout of hole spins in Ge. Nano Letters.
American Chemical Society. https://doi.org/10.1021/acs.nanolett.8b03217
chicago: Vukušić, Lada, Josip Kukucka, Hannes Watzinger, Joshua M Milem, Friedrich
Schäffler, and Georgios Katsaros. “Single-Shot Readout of Hole Spins in Ge.” Nano
Letters. American Chemical Society, 2018. https://doi.org/10.1021/acs.nanolett.8b03217.
ieee: L. Vukušić, J. Kukucka, H. Watzinger, J. M. Milem, F. Schäffler, and G. Katsaros,
“Single-shot readout of hole spins in Ge,” Nano Letters, vol. 18, no. 11.
American Chemical Society, pp. 7141–7145, 2018.
ista: Vukušić L, Kukucka J, Watzinger H, Milem JM, Schäffler F, Katsaros G. 2018.
Single-shot readout of hole spins in Ge. Nano Letters. 18(11), 7141–7145.
mla: Vukušić, Lada, et al. “Single-Shot Readout of Hole Spins in Ge.” Nano Letters,
vol. 18, no. 11, American Chemical Society, 2018, pp. 7141–45, doi:10.1021/acs.nanolett.8b03217.
short: L. Vukušić, J. Kukucka, H. Watzinger, J.M. Milem, F. Schäffler, G. Katsaros,
Nano Letters 18 (2018) 7141–7145.
date_created: 2018-12-11T11:44:13Z
date_published: 2018-10-25T00:00:00Z
date_updated: 2023-09-18T09:30:37Z
day: '25'
ddc:
- '530'
department:
- _id: GeKa
doi: 10.1021/acs.nanolett.8b03217
ec_funded: 1
external_id:
isi:
- '000451102100064'
pmid:
- '30359041'
file:
- access_level: open_access
checksum: 3e6034a94c6b5335e939145d88bdb371
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:08Z
date_updated: 2020-07-14T12:45:37Z
file_id: '5194'
file_name: IST-2018-1065-v1+1_ACS_nanoletters_8b03217.pdf
file_size: 1361441
relation: main_file
file_date_updated: 2020-07-14T12:45:37Z
has_accepted_license: '1'
intvolume: ' 18'
isi: 1
issue: '11'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: 7141 - 7145
pmid: 1
project:
- _id: 25517E86-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '335497'
name: Towards Spin qubits and Majorana fermions in Germanium selfassembled hut-wires
publication: Nano Letters
publication_identifier:
issn:
- '15306984'
publication_status: published
publisher: American Chemical Society
publist_id: '8032'
pubrep_id: '1065'
quality_controlled: '1'
related_material:
record:
- id: '7977'
relation: popular_science
- id: '69'
relation: dissertation_contains
status: public
- id: '7996'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Single-shot readout of hole spins in Ge
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 18
year: '2018'
...
---
_id: '24'
abstract:
- lang: eng
text: Partially-observable Markov decision processes (POMDPs) with discounted-sum
payoff are a standard framework to model a wide range of problems related to decision
making under uncertainty. Traditionally, the goal has been to obtain policies
that optimize the expectation of the discounted-sum payoff. A key drawback of
the expectation measure is that even low probability events with extreme payoff
can significantly affect the expectation, and thus the obtained policies are not
necessarily risk-averse. An alternate approach is to optimize the probability
that the payoff is above a certain threshold, which allows obtaining risk-averse
policies, but ignores optimization of the expectation. We consider the expectation
optimization with probabilistic guarantee (EOPG) problem, where the goal is to
optimize the expectation ensuring that the payoff is above a given threshold with
at least a specified probability. We present several results on the EOPG problem,
including the first algorithm to solve it.
acknowledgement: "This research was supported by the Vienna Science and Technology
Fund (WWTF) grant ICT15-003; Austrian Science Fund (FWF): S11407-N23(RiSE/SHiNE);and
an ERC Start Grant (279307:Graph Games).\r\n"
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Adrian
full_name: Elgyütt, Adrian
id: 4A2E9DBA-F248-11E8-B48F-1D18A9856A87
last_name: Elgyütt
- first_name: Petr
full_name: Novotny, Petr
id: 3CC3B868-F248-11E8-B48F-1D18A9856A87
last_name: Novotny
- first_name: Owen
full_name: Rouillé, Owen
last_name: Rouillé
citation:
ama: 'Chatterjee K, Elgyütt A, Novotný P, Rouillé O. Expectation optimization with
probabilistic guarantees in POMDPs with discounted-sum objectives. In: Vol 2018.
IJCAI; 2018:4692-4699. doi:10.24963/ijcai.2018/652'
apa: 'Chatterjee, K., Elgyütt, A., Novotný, P., & Rouillé, O. (2018). Expectation
optimization with probabilistic guarantees in POMDPs with discounted-sum objectives
(Vol. 2018, pp. 4692–4699). Presented at the IJCAI: International Joint Conference
on Artificial Intelligence, Stockholm, Sweden: IJCAI. https://doi.org/10.24963/ijcai.2018/652'
chicago: Chatterjee, Krishnendu, Adrian Elgyütt, Petr Novotný, and Owen Rouillé.
“Expectation Optimization with Probabilistic Guarantees in POMDPs with Discounted-Sum
Objectives,” 2018:4692–99. IJCAI, 2018. https://doi.org/10.24963/ijcai.2018/652.
ieee: 'K. Chatterjee, A. Elgyütt, P. Novotný, and O. Rouillé, “Expectation optimization
with probabilistic guarantees in POMDPs with discounted-sum objectives,” presented
at the IJCAI: International Joint Conference on Artificial Intelligence, Stockholm,
Sweden, 2018, vol. 2018, pp. 4692–4699.'
ista: 'Chatterjee K, Elgyütt A, Novotný P, Rouillé O. 2018. Expectation optimization
with probabilistic guarantees in POMDPs with discounted-sum objectives. IJCAI:
International Joint Conference on Artificial Intelligence vol. 2018, 4692–4699.'
mla: Chatterjee, Krishnendu, et al. Expectation Optimization with Probabilistic
Guarantees in POMDPs with Discounted-Sum Objectives. Vol. 2018, IJCAI, 2018,
pp. 4692–99, doi:10.24963/ijcai.2018/652.
short: K. Chatterjee, A. Elgyütt, P. Novotný, O. Rouillé, in:, IJCAI, 2018, pp.
4692–4699.
conference:
end_date: 2018-07-19
location: Stockholm, Sweden
name: 'IJCAI: International Joint Conference on Artificial Intelligence'
start_date: 2018-07-13
date_created: 2018-12-11T11:44:13Z
date_published: 2018-07-01T00:00:00Z
date_updated: 2025-06-02T08:53:48Z
day: '01'
department:
- _id: KrCh
- _id: ToHe
doi: 10.24963/ijcai.2018/652
ec_funded: 1
external_id:
arxiv:
- '1804.10601'
isi:
- '000764175404117'
intvolume: ' 2018'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1804.10601
month: '07'
oa: 1
oa_version: Preprint
page: 4692 - 4699
project:
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication_status: published
publisher: IJCAI
publist_id: '8031'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Expectation optimization with probabilistic guarantees in POMDPs with discounted-sum
objectives
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 2018
year: '2018'
...
---
_id: '25'
abstract:
- lang: eng
text: 'Partially observable Markov decision processes (POMDPs) are the standard
models for planning under uncertainty with both finite and infinite horizon. Besides
the well-known discounted-sum objective, indefinite-horizon objective (aka Goal-POMDPs)
is another classical objective for POMDPs. In this case, given a set of target
states and a positive cost for each transition, the optimization objective is
to minimize the expected total cost until a target state is reached. In the literature,
RTDP-Bel or heuristic search value iteration (HSVI) have been used for solving
Goal-POMDPs. Neither of these algorithms has theoretical convergence guarantees,
and HSVI may even fail to terminate its trials. We give the following contributions:
(1) We discuss the challenges introduced in Goal-POMDPs and illustrate how they
prevent the original HSVI from converging. (2) We present a novel algorithm inspired
by HSVI, termed Goal-HSVI, and show that our algorithm has convergence guarantees.
(3) We show that Goal-HSVI outperforms RTDP-Bel on a set of well-known examples.'
acknowledgement: '∗This work has been supported by Vienna Science and Technology Fund
(WWTF) Project ICT15-003, Austrian Science Fund (FWF) NFN Grant No S11407-N23 (RiSE/SHiNE),
and ERC Starting grant (279307: Graph Games). This research was sponsored by the
Army Research Laboratory and was accomplished under Cooperative Agreement Number
W911NF-13-2-0045 (ARL Cyber Security CRA). '
article_processing_charge: No
author:
- first_name: Karel
full_name: Horák, Karel
last_name: Horák
- first_name: Branislav
full_name: Bošanský, Branislav
last_name: Bošanský
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: 'Horák K, Bošanský B, Chatterjee K. Goal-HSVI: Heuristic search value iteration
for goal-POMDPs. In: Proceedings of the Twenty-Seventh International Joint
Conference on Artificial Intelligence. Vol 2018-July. IJCAI; 2018:4764-4770.
doi:10.24963/ijcai.2018/662'
apa: 'Horák, K., Bošanský, B., & Chatterjee, K. (2018). Goal-HSVI: Heuristic
search value iteration for goal-POMDPs. In Proceedings of the Twenty-Seventh
International Joint Conference on Artificial Intelligence (Vol. 2018–July,
pp. 4764–4770). Stockholm, Sweden: IJCAI. https://doi.org/10.24963/ijcai.2018/662'
chicago: 'Horák, Karel, Branislav Bošanský, and Krishnendu Chatterjee. “Goal-HSVI:
Heuristic Search Value Iteration for Goal-POMDPs.” In Proceedings of the Twenty-Seventh
International Joint Conference on Artificial Intelligence, 2018–July:4764–70.
IJCAI, 2018. https://doi.org/10.24963/ijcai.2018/662.'
ieee: 'K. Horák, B. Bošanský, and K. Chatterjee, “Goal-HSVI: Heuristic search value
iteration for goal-POMDPs,” in Proceedings of the Twenty-Seventh International
Joint Conference on Artificial Intelligence, Stockholm, Sweden, 2018, vol.
2018–July, pp. 4764–4770.'
ista: 'Horák K, Bošanský B, Chatterjee K. 2018. Goal-HSVI: Heuristic search value
iteration for goal-POMDPs. Proceedings of the Twenty-Seventh International Joint
Conference on Artificial Intelligence. IJCAI: International Joint Conference on
Artificial Intelligence vol. 2018–July, 4764–4770.'
mla: 'Horák, Karel, et al. “Goal-HSVI: Heuristic Search Value Iteration for Goal-POMDPs.”
Proceedings of the Twenty-Seventh International Joint Conference on Artificial
Intelligence, vol. 2018–July, IJCAI, 2018, pp. 4764–70, doi:10.24963/ijcai.2018/662.'
short: K. Horák, B. Bošanský, K. Chatterjee, in:, Proceedings of the Twenty-Seventh
International Joint Conference on Artificial Intelligence, IJCAI, 2018, pp. 4764–4770.
conference:
end_date: 2018-07-19
location: Stockholm, Sweden
name: 'IJCAI: International Joint Conference on Artificial Intelligence'
start_date: 2018-07-13
date_created: 2018-12-11T11:44:13Z
date_published: 2018-07-01T00:00:00Z
date_updated: 2025-06-02T08:53:40Z
day: '01'
department:
- _id: KrCh
doi: 10.24963/ijcai.2018/662
ec_funded: 1
external_id:
isi:
- '000764175404127'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.24963/ijcai.2018/662
month: '07'
oa: 1
oa_version: Published Version
page: 4764 - 4770
project:
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication: Proceedings of the Twenty-Seventh International Joint Conference on Artificial
Intelligence
publication_status: published
publisher: IJCAI
publist_id: '8030'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Goal-HSVI: Heuristic search value iteration for goal-POMDPs'
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 2018-July
year: '2018'
...
---
_id: '26'
abstract:
- lang: eng
text: Expression of genes is a fundamental molecular phenotype that is subject to
evolution by different types of mutations. Both the rate and the effect of mutations
may depend on the DNA sequence context of a particular gene or a particular promoter
sequence. In this thesis I investigate the nature of this dependence using simple
genetic systems in Escherichia coli. With these systems I explore the evolution
of constitutive gene expression from random starting sequences at different loci
on the chromosome and at different locations in sequence space. First, I dissect
chromosomal neighborhood effects that underlie locus-dependent differences in
the potential of a gene under selection to become more highly expressed. Next,
I find that the effects of point mutations in promoter sequences are dependent
on sequence context, and that an existing energy matrix model performs poorly
in predicting relative expression of unrelated sequences. Finally, I show that
a substantial fraction of random sequences contain functional promoters and I
present an extended thermodynamic model that predicts promoter strength in full
sequence space. Taken together, these results provide new insights and guides
on how to integrate information on sequence context to improve our qualitative
and quantitative understanding of bacterial gene expression, with implications
for rapid evolution of drug resistance, de novo evolution of genes, and horizontal
gene transfer.
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Magdalena
full_name: Steinrück, Magdalena
id: 2C023F40-F248-11E8-B48F-1D18A9856A87
last_name: Steinrück
orcid: 0000-0003-1229-9719
citation:
ama: Steinrück M. The influence of sequence context on the evolution of bacterial
gene expression. 2018. doi:10.15479/AT:ISTA:th1059
apa: Steinrück, M. (2018). The influence of sequence context on the evolution
of bacterial gene expression. Institute of Science and Technology Austria.
https://doi.org/10.15479/AT:ISTA:th1059
chicago: Steinrück, Magdalena. “The Influence of Sequence Context on the Evolution
of Bacterial Gene Expression.” Institute of Science and Technology Austria, 2018.
https://doi.org/10.15479/AT:ISTA:th1059.
ieee: M. Steinrück, “The influence of sequence context on the evolution of bacterial
gene expression,” Institute of Science and Technology Austria, 2018.
ista: Steinrück M. 2018. The influence of sequence context on the evolution of bacterial
gene expression. Institute of Science and Technology Austria.
mla: Steinrück, Magdalena. The Influence of Sequence Context on the Evolution
of Bacterial Gene Expression. Institute of Science and Technology Austria,
2018, doi:10.15479/AT:ISTA:th1059.
short: M. Steinrück, The Influence of Sequence Context on the Evolution of Bacterial
Gene Expression, Institute of Science and Technology Austria, 2018.
date_created: 2018-12-11T11:44:14Z
date_published: 2018-10-30T00:00:00Z
date_updated: 2023-09-07T12:48:43Z
day: '30'
ddc:
- '576'
- '579'
degree_awarded: PhD
department:
- _id: CaGu
doi: 10.15479/AT:ISTA:th1059
file:
- access_level: closed
checksum: 413cbce1cd1debeae3abe2a25dbc70d1
content_type: application/vnd.openxmlformats-officedocument.wordprocessingml.document
creator: dernst
date_created: 2019-02-08T10:51:22Z
date_updated: 2020-07-14T12:45:43Z
embargo_to: open_access
file_id: '5941'
file_name: Thesis_Steinrueck_final.docx
file_size: 9190845
relation: source_file
- access_level: open_access
checksum: 3def8b7854c8b42d643597ce0215efac
content_type: application/pdf
creator: dernst
date_created: 2019-02-08T10:51:22Z
date_updated: 2021-02-11T11:17:14Z
embargo: 2019-11-02
file_id: '5942'
file_name: Thesis_Steinrueck_final.pdf
file_size: 7521973
relation: main_file
file_date_updated: 2021-02-11T11:17:14Z
has_accepted_license: '1'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: '109'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '8029'
pubrep_id: '1059'
related_material:
record:
- id: '704'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Calin C
full_name: Guet, Calin C
id: 47F8433E-F248-11E8-B48F-1D18A9856A87
last_name: Guet
orcid: 0000-0001-6220-2052
title: The influence of sequence context on the evolution of bacterial gene expression
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2018'
...
---
_id: '273'
abstract:
- lang: eng
text: The accuracy of information retrieval systems is often measured using complex
loss functions such as the average precision (AP) or the normalized discounted
cumulative gain (NDCG). Given a set of positive and negative samples, the parameters
of a retrieval system can be estimated by minimizing these loss functions. However,
the non-differentiability and non-decomposability of these loss functions does
not allow for simple gradient based optimization algorithms. This issue is generally
circumvented by either optimizing a structured hinge-loss upper bound to the loss
function or by using asymptotic methods like the direct-loss minimization framework.
Yet, the high computational complexity of loss-augmented inference, which is necessary
for both the frameworks, prohibits its use in large training data sets. To alleviate
this deficiency, we present a novel quicksort flavored algorithm for a large class
of non-decomposable loss functions. We provide a complete characterization of
the loss functions that are amenable to our algorithm, and show that it includes
both AP and NDCG based loss functions. Furthermore, we prove that no comparison
based algorithm can improve upon the computational complexity of our approach
asymptotically. We demonstrate the effectiveness of our approach in the context
of optimizing the structured hinge loss upper bound of AP and NDCG loss for learning
models for a variety of vision tasks. We show that our approach provides significantly
better results than simpler decomposable loss functions, while requiring a comparable
training time.
article_processing_charge: No
arxiv: 1
author:
- first_name: Pritish
full_name: Mohapatra, Pritish
last_name: Mohapatra
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
- first_name: C V
full_name: Jawahar, C V
last_name: Jawahar
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: M Pawan
full_name: Kumar, M Pawan
last_name: Kumar
citation:
ama: 'Mohapatra P, Rolinek M, Jawahar CV, Kolmogorov V, Kumar MP. Efficient optimization
for rank-based loss functions. In: 2018 IEEE/CVF Conference on Computer Vision
and Pattern Recognition. IEEE; 2018:3693-3701. doi:10.1109/cvpr.2018.00389'
apa: 'Mohapatra, P., Rolinek, M., Jawahar, C. V., Kolmogorov, V., & Kumar, M.
P. (2018). Efficient optimization for rank-based loss functions. In 2018 IEEE/CVF
Conference on Computer Vision and Pattern Recognition (pp. 3693–3701). Salt
Lake City, UT, USA: IEEE. https://doi.org/10.1109/cvpr.2018.00389'
chicago: Mohapatra, Pritish, Michal Rolinek, C V Jawahar, Vladimir Kolmogorov, and
M Pawan Kumar. “Efficient Optimization for Rank-Based Loss Functions.” In 2018
IEEE/CVF Conference on Computer Vision and Pattern Recognition, 3693–3701.
IEEE, 2018. https://doi.org/10.1109/cvpr.2018.00389.
ieee: P. Mohapatra, M. Rolinek, C. V. Jawahar, V. Kolmogorov, and M. P. Kumar, “Efficient
optimization for rank-based loss functions,” in 2018 IEEE/CVF Conference on
Computer Vision and Pattern Recognition, Salt Lake City, UT, USA, 2018, pp.
3693–3701.
ista: 'Mohapatra P, Rolinek M, Jawahar CV, Kolmogorov V, Kumar MP. 2018. Efficient
optimization for rank-based loss functions. 2018 IEEE/CVF Conference on Computer
Vision and Pattern Recognition. CVPR: Conference on Computer Vision and Pattern
Recognition, 3693–3701.'
mla: Mohapatra, Pritish, et al. “Efficient Optimization for Rank-Based Loss Functions.”
2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, IEEE,
2018, pp. 3693–701, doi:10.1109/cvpr.2018.00389.
short: P. Mohapatra, M. Rolinek, C.V. Jawahar, V. Kolmogorov, M.P. Kumar, in:, 2018
IEEE/CVF Conference on Computer Vision and Pattern Recognition, IEEE, 2018, pp.
3693–3701.
conference:
end_date: 2018-06-22
location: Salt Lake City, UT, USA
name: 'CVPR: Conference on Computer Vision and Pattern Recognition'
start_date: 2018-06-18
date_created: 2018-12-11T11:45:33Z
date_published: 2018-06-28T00:00:00Z
date_updated: 2023-09-11T13:24:43Z
day: '28'
department:
- _id: VlKo
doi: 10.1109/cvpr.2018.00389
ec_funded: 1
external_id:
arxiv:
- '1604.08269'
isi:
- '000457843603087'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1604.08269
month: '06'
oa: 1
oa_version: Preprint
page: 3693-3701
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition
publication_identifier:
isbn:
- '9781538664209'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Efficient optimization for rank-based loss functions
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2018'
...