---
_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 M, 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., & 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 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. 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 M, 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. 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: 2024-11-06T12:05:51Z
day: '01'
doi: 10.1145/3174803
extern: '1'
external_id:
arxiv:
- '1611.06500'
fulldoi: https://doi.org/10.1145/3174803
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 M, 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., & 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 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. 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 M, 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. 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: 2024-11-06T12:06:28Z
day: '01'
doi: 10.1145/3232860
extern: '1'
external_id:
arxiv:
- '1310.3153'
fulldoi: https://doi.org/10.1145/3232860
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 M, 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., & 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 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. 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 M, 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. 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: 2024-11-06T08:13:33Z
day: '01'
doi: 10.1016/j.ic.2018.02.005
extern: '1'
fulldoi: https://doi.org/10.1016/j.ic.2018.02.005
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 M, 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., 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, 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. 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 M, 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, 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. 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: 2024-11-06T12:18:17Z
day: '01'
doi: 10.1145/3218657
extern: '1'
external_id:
arxiv:
- '1512.08148'
fulldoi: https://doi.org/10.1145/3218657
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 M, 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., & 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 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. 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 M, 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. 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: 2024-11-06T11:57:41Z
day: '14'
doi: 10.4230/LIPICS.ESA.2018.39
extern: '1'
external_id:
arxiv:
- '1909.06653'
fulldoi: https://doi.org/10.4230/LIPICS.ESA.2018.39
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 M, 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., & 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 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. 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 M, 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. 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
corr_author: '1'
date_created: 2022-08-12T08:26:42Z
date_published: 2018-08-14T00:00:00Z
date_updated: 2024-11-06T12:16:31Z
day: '14'
doi: 10.4230/LIPICS.ESA.2018.40
extern: '1'
external_id:
arxiv:
- '1802.09111'
fulldoi: https://doi.org/10.4230/LIPICS.ESA.2018.40
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 M, 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., & 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 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. 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 M, 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. 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: 2024-11-06T12:20:35Z
day: '01'
doi: 10.1137/1.9781611975031.1
extern: '1'
external_id:
arxiv:
- '1711.04355'
fulldoi: https://doi.org/10.1137/1.9781611975031.1
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 M, 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., 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, 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. 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 M, 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, 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. 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: 2024-11-06T12:22:09Z
day: '01'
doi: 10.1137/1.9781611975055.5
extern: '1'
external_id:
arxiv:
- '1708.06127'
fulldoi: https://doi.org/10.1137/1.9781611975055.5
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 M, 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., & 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 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. 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 M, 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. 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: 2024-11-06T12:22:54Z
day: '01'
doi: 10.1137/140998925
extern: '1'
external_id:
arxiv:
- '1412.1318'
fulldoi: https://doi.org/10.1137/140998925
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 M, 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., 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 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. 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 M, 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. 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: 2024-11-06T11:57:15Z
day: '01'
doi: 10.4230/LIPICS.SEA.2018.3
extern: '1'
external_id:
arxiv:
- '1802.07034'
fulldoi: https://doi.org/10.4230/LIPICS.SEA.2018.3
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'
fulldoi: https://doi.org/10.1002/anie.201712568
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: '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: 2026-04-08T14:09:47Z
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
fulldoi: https://doi.org/10.1021/acs.nanolett.8b03217
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 self assembled hut-wires
publication: Nano Letters
publication_identifier:
issn:
- 1530-6984
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: '7996'
relation: dissertation_contains
status: public
- id: '69'
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
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-04-14T13:51:04Z
day: '01'
department:
- _id: KrCh
- _id: ToHe
doi: 10.24963/ijcai.2018/652
ec_funded: 1
external_id:
arxiv:
- '1804.10601'
isi:
- '000764175404117'
fulldoi: https://doi.org/10.24963/ijcai.2018/652
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: 2026-06-18T18:34:17Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.24963/ijcai.2018/662
ec_funded: 1
external_id:
isi:
- '000764175404127'
fulldoi: https://doi.org/10.24963/ijcai.2018/662
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2018-July
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: 2024-11-04T13:52:32Z
day: '28'
department:
- _id: VlKo
doi: 10.1109/cvpr.2018.00389
ec_funded: 1
external_id:
arxiv:
- '1604.08269'
isi:
- '000457843603087'
fulldoi: https://doi.org/10.1109/cvpr.2018.00389
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'
...
---
_id: '275'
abstract:
- lang: eng
text: Lymphatic endothelial cells (LECs) release extracellular chemokines to guide
the migration of dendritic cells. In this study, we report that LECs also release
basolateral exosome-rich endothelial vesicles (EEVs) that are secreted in greater
numbers in the presence of inflammatory cytokines and accumulate in the perivascular
stroma of small lymphatic vessels in human chronic inflammatory diseases. Proteomic
analyses of EEV fractions identified > 1,700 cargo proteins and revealed a
dominant motility-promoting protein signature. In vitro and ex vivo EEV fractions
augmented cellular protrusion formation in a CX3CL1/fractalkine-dependent fashion
and enhanced the directional migratory response of human dendritic cells along
guidance cues. We conclude that perilymphatic LEC exosomes enhance exploratory
behavior and thus promote directional migration of CX3CR1-expressing cells in
complex tissue environments.
acknowledgement: M. Brown was supported by the Cell Communication in Health and Disease
Graduate Study Program of the Austrian Science Fund and Medizinische Universität
Wien, M. Sixt by the European Research Council (ERC GA 281556) and an Austrian Science
Fund START award, K.L. Bennett by the Austrian Academy of Sciences, D.G. Jackson
and L.A. Johnson by Unit Funding (MC_UU_12010/2) and project grants from the Medical
Research Council (G1100134 and MR/L008610/1), and M. Detmar by the Schweizerischer
Nationalfonds zur Förderung der Wissenschaftlichen Forschung and Advanced European
Research Council grant LYVICAM. K. Vaahtomeri was supported by an Academy of Finland
postdoctoral research grant (287853). This project has received funding from the
European Union’s Horizon 2020 research and innovation program under grant agreement
No. 668036 (RELENT).
article_processing_charge: No
author:
- first_name: Markus
full_name: Brown, Markus
id: 3DAB9AFC-F248-11E8-B48F-1D18A9856A87
last_name: Brown
- first_name: Louise
full_name: Johnson, Louise
last_name: Johnson
- first_name: Dario
full_name: Leone, Dario
last_name: Leone
- first_name: Peter
full_name: Májek, Peter
last_name: Májek
- first_name: Kari
full_name: Vaahtomeri, Kari
id: 368EE576-F248-11E8-B48F-1D18A9856A87
last_name: Vaahtomeri
orcid: 0000-0001-7829-3518
- first_name: Daniel
full_name: Senfter, Daniel
last_name: Senfter
- first_name: Nora
full_name: Bukosza, Nora
last_name: Bukosza
- first_name: Helga
full_name: Schachner, Helga
last_name: Schachner
- first_name: Gabriele
full_name: Asfour, Gabriele
last_name: Asfour
- first_name: Brigitte
full_name: Langer, Brigitte
last_name: Langer
- first_name: Robert
full_name: Hauschild, Robert
id: 4E01D6B4-F248-11E8-B48F-1D18A9856A87
last_name: Hauschild
orcid: 0000-0001-9843-3522
- first_name: Katja
full_name: Parapatics, Katja
last_name: Parapatics
- first_name: Young
full_name: Hong, Young
last_name: Hong
- first_name: Keiryn
full_name: Bennett, Keiryn
last_name: Bennett
- first_name: Renate
full_name: Kain, Renate
last_name: Kain
- first_name: Michael
full_name: Detmar, Michael
last_name: Detmar
- first_name: Michael K
full_name: Sixt, Michael K
id: 41E9FBEA-F248-11E8-B48F-1D18A9856A87
last_name: Sixt
orcid: 0000-0002-6620-9179
- first_name: David
full_name: Jackson, David
last_name: Jackson
- first_name: Dontscho
full_name: Kerjaschki, Dontscho
last_name: Kerjaschki
citation:
ama: Brown M, Johnson L, Leone D, et al. Lymphatic exosomes promote dendritic cell
migration along guidance cues. Journal of Cell Biology. 2018;217(6):2205-2221.
doi:10.1083/jcb.201612051
apa: Brown, M., Johnson, L., Leone, D., Májek, P., Vaahtomeri, K., Senfter, D.,
… Kerjaschki, D. (2018). Lymphatic exosomes promote dendritic cell migration along
guidance cues. Journal of Cell Biology. Rockefeller University Press. https://doi.org/10.1083/jcb.201612051
chicago: Brown, Markus, Louise Johnson, Dario Leone, Peter Májek, Kari Vaahtomeri,
Daniel Senfter, Nora Bukosza, et al. “Lymphatic Exosomes Promote Dendritic Cell
Migration along Guidance Cues.” Journal of Cell Biology. Rockefeller University
Press, 2018. https://doi.org/10.1083/jcb.201612051.
ieee: M. Brown et al., “Lymphatic exosomes promote dendritic cell migration
along guidance cues,” Journal of Cell Biology, vol. 217, no. 6. Rockefeller
University Press, pp. 2205–2221, 2018.
ista: Brown M, Johnson L, Leone D, Májek P, Vaahtomeri K, Senfter D, Bukosza N,
Schachner H, Asfour G, Langer B, Hauschild R, Parapatics K, Hong Y, Bennett K,
Kain R, Detmar M, Sixt MK, Jackson D, Kerjaschki D. 2018. Lymphatic exosomes promote
dendritic cell migration along guidance cues. Journal of Cell Biology. 217(6),
2205–2221.
mla: Brown, Markus, et al. “Lymphatic Exosomes Promote Dendritic Cell Migration
along Guidance Cues.” Journal of Cell Biology, vol. 217, no. 6, Rockefeller
University Press, 2018, pp. 2205–21, doi:10.1083/jcb.201612051.
short: M. Brown, L. Johnson, D. Leone, P. Májek, K. Vaahtomeri, D. Senfter, N. Bukosza,
H. Schachner, G. Asfour, B. Langer, R. Hauschild, K. Parapatics, Y. Hong, K. Bennett,
R. Kain, M. Detmar, M.K. Sixt, D. Jackson, D. Kerjaschki, Journal of Cell Biology
217 (2018) 2205–2221.
corr_author: '1'
date_created: 2018-12-11T11:45:33Z
date_published: 2018-04-12T00:00:00Z
date_updated: 2025-04-14T13:10:20Z
day: '12'
ddc:
- '570'
department:
- _id: MiSi
- _id: Bio
doi: 10.1083/jcb.201612051
ec_funded: 1
external_id:
isi:
- '000438077800026'
pmid:
- '29650776'
file:
- access_level: open_access
checksum: 9c7eba51a35c62da8c13f98120b64df4
content_type: application/pdf
creator: dernst
date_created: 2018-12-17T12:50:07Z
date_updated: 2020-07-14T12:45:45Z
file_id: '5704'
file_name: 2018_JournalCellBiology_Brown.pdf
file_size: 2252043
relation: main_file
file_date_updated: 2020-07-14T12:45:45Z
fulldoi: https://doi.org/10.1083/jcb.201612051
has_accepted_license: '1'
intvolume: ' 217'
isi: 1
issue: '6'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: 2205 - 2221
pmid: 1
project:
- _id: 25A8E5EA-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Y 564-B12
name: Cytoskeletal force generation and force transduction of migrating leukocytes
- _id: 25A603A2-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '281556'
name: Cytoskeletal force generation and force transduction of migrating leukocytes
publication: Journal of Cell Biology
publication_status: published
publisher: Rockefeller University Press
publist_id: '7627'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lymphatic exosomes promote dendritic cell migration along guidance cues
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: 217
year: '2018'
...
---
_id: '276'
abstract:
- lang: eng
text: Directed migration of cells relies on their ability to sense directional guidance
cues and to interact with pericellular structures in order to transduce contractile
cytoskeletal- into mechanical forces. These biomechanical processes depend highly
on microenvironmental factors such as exposure to 2D surfaces or 3D matrices.
In vivo, the majority of cells are exposed to 3D environments. Data on 3D cell
migration are mostly derived from intravital microscopy or collagen-based in vitro
assays. Both approaches offer only limited controlla-bility of experimental conditions.
Here, we developed an automated microfluidic system that allows positioning of
cells in 3D microenvironments containing highly controlled diffusion-based chemokine
gradients. Tracking migration in such gradients was feasible in real time at the
single cell level. Moreover, the setup allowed on-chip immunocytochemistry and
thus linking of functional with phenotypical properties in individual cells. Spatially
defined retrieval of cells from the device allows down-stream off-chip analysis.
Using dendritic cells as a model, our setup specifically allowed us for the first
time to quantitate key migration characteristics of cells exposed to identical
gradients of the chemokine CCL19 yet placed on 2D vs in 3D environments. Migration
properties between 2D and 3D migration were distinct. Morphological features of
cells migrating in an in vitro 3D environment were similar to those of cells migrating
in animal tissues, but different from cells migrating on a surface. Our system
thus offers a highly controllable in vitro-mimic of a 3D environment that cells
traffic in vivo.
acknowledgement: This work was supported by the Swiss National Science Foundation
(MD-PhD fellowships, 323530_164221 to C.F.; and 323630_151483 to A.J.; grant PZ00P3_144863
to M.R, grant 31003A_156431 to T.S.; PZ00P3_148000 to C.T.B.; PZ00P3_154733 to M.M.),
a Novartis “FreeNovation” grant to M.M. and T.S. and an EMBO long-term fellowship
(ALTF 1396-2014) co-funded by the European Commission (LTFCOFUND2013, GA-2013-609409)
to J.R.. M.R. was supported by the Gebert Rüf Foundation (GRS 058/14). The funders
had no role in study design, data collection and analysis, decision to publish,
or preparation of the manuscript.
article_number: e0198330
article_processing_charge: No
article_type: original
author:
- first_name: Corina
full_name: Frick, Corina
last_name: Frick
- first_name: Philip
full_name: Dettinger, Philip
last_name: Dettinger
- first_name: Jörg
full_name: Renkawitz, Jörg
id: 3F0587C8-F248-11E8-B48F-1D18A9856A87
last_name: Renkawitz
orcid: 0000-0003-2856-3369
- first_name: Annaïse
full_name: Jauch, Annaïse
last_name: Jauch
- first_name: Christoph
full_name: Berger, Christoph
last_name: Berger
- first_name: Mike
full_name: Recher, Mike
last_name: Recher
- first_name: Timm
full_name: Schroeder, Timm
last_name: Schroeder
- first_name: Matthias
full_name: Mehling, Matthias
last_name: Mehling
citation:
ama: Frick C, Dettinger P, Renkawitz J, et al. Nano-scale microfluidics to study
3D chemotaxis at the single cell level. PLoS One. 2018;13(6). doi:10.1371/journal.pone.0198330
apa: Frick, C., Dettinger, P., Renkawitz, J., Jauch, A., Berger, C., Recher, M.,
… Mehling, M. (2018). Nano-scale microfluidics to study 3D chemotaxis at the single
cell level. PLoS One. Public Library of Science. https://doi.org/10.1371/journal.pone.0198330
chicago: Frick, Corina, Philip Dettinger, Jörg Renkawitz, Annaïse Jauch, Christoph
Berger, Mike Recher, Timm Schroeder, and Matthias Mehling. “Nano-Scale Microfluidics
to Study 3D Chemotaxis at the Single Cell Level.” PLoS One. Public Library
of Science, 2018. https://doi.org/10.1371/journal.pone.0198330.
ieee: C. Frick et al., “Nano-scale microfluidics to study 3D chemotaxis at
the single cell level,” PLoS One, vol. 13, no. 6. Public Library of Science,
2018.
ista: Frick C, Dettinger P, Renkawitz J, Jauch A, Berger C, Recher M, Schroeder
T, Mehling M. 2018. Nano-scale microfluidics to study 3D chemotaxis at the single
cell level. PLoS One. 13(6), e0198330.
mla: Frick, Corina, et al. “Nano-Scale Microfluidics to Study 3D Chemotaxis at the
Single Cell Level.” PLoS One, vol. 13, no. 6, e0198330, Public Library
of Science, 2018, doi:10.1371/journal.pone.0198330.
short: C. Frick, P. Dettinger, J. Renkawitz, A. Jauch, C. Berger, M. Recher, T.
Schroeder, M. Mehling, PLoS One 13 (2018).
date_created: 2018-12-11T11:45:34Z
date_published: 2018-06-07T00:00:00Z
date_updated: 2023-09-13T09:00:15Z
day: '07'
ddc:
- '570'
department:
- _id: MiSi
doi: 10.1371/journal.pone.0198330
external_id:
isi:
- '000434384900031'
file:
- access_level: open_access
checksum: 95fc5dc3938b3ad3b7697d10c83cc143
content_type: application/pdf
creator: dernst
date_created: 2018-12-17T14:10:32Z
date_updated: 2020-07-14T12:45:45Z
file_id: '5709'
file_name: 2018_Plos_Frick.pdf
file_size: 7682167
relation: main_file
file_date_updated: 2020-07-14T12:45:45Z
fulldoi: https://doi.org/10.1371/journal.pone.0198330
has_accepted_license: '1'
intvolume: ' 13'
isi: 1
issue: '6'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: PLoS One
publication_status: published
publisher: Public Library of Science
publist_id: '7626'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Nano-scale microfluidics to study 3D chemotaxis at the single cell level
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: 13
year: '2018'
...
---
_id: '277'
abstract:
- lang: eng
text: 'Arabidopsis and human ARM protein interact with telomerase. Deregulated mRNA
levels of DNA repair and ribosomal protein genes in an Arabidopsis arm mutant
suggest non-telomeric ARM function. The human homolog ARMC6 interacts with hTRF2.
Abstract: Telomerase maintains telomeres and has proposed non-telomeric functions.
We previously identified interaction of the C-terminal domain of Arabidopsis telomerase
reverse transcriptase (AtTERT) with an armadillo/β-catenin-like repeat (ARM) containing
protein. Here we explore protein–protein interactions of the ARM protein, AtTERT
domains, POT1a, TRF-like family and SMH family proteins, and the chromatin remodeling
protein CHR19 using bimolecular fluorescence complementation (BiFC), yeast two-hybrid
(Y2H) analysis, and co-immunoprecipitation. The ARM protein interacts with both
the N- and C-terminal domains of AtTERT in different cellular compartments. ARM
interacts with CHR19 and TRF-like I family proteins that also bind AtTERT directly
or through interaction with POT1a. The putative human ARM homolog co-precipitates
telomerase activity and interacts with hTRF2 protein in vitro. Analysis of Arabidopsis
arm mutants shows no obvious changes in telomere length or telomerase activity,
suggesting that ARM is not essential for telomere maintenance. The observed interactions
with telomerase and Myb-like domain proteins (TRF-like family I) may therefore
reflect possible non-telomeric functions. Transcript levels of several DNA repair
and ribosomal genes are affected in arm mutants, and ARM, likely in association
with other proteins, suppressed expression of XRCC3 and RPSAA promoter constructs
in luciferase reporter assays. In conclusion, ARM can participate in non-telomeric
functions of telomerase, and can also perform its own telomerase-independent functions.'
article_processing_charge: No
article_type: original
author:
- first_name: Ladislav
full_name: Dokládal, Ladislav
last_name: Dokládal
- first_name: Eva
full_name: Benková, Eva
id: 38F4F166-F248-11E8-B48F-1D18A9856A87
last_name: Benková
orcid: 0000-0002-8510-9739
- first_name: David
full_name: Honys, David
last_name: Honys
- first_name: Nikoleta
full_name: Dupláková, Nikoleta
last_name: Dupláková
- first_name: Lan
full_name: Lee, Lan
last_name: Lee
- first_name: Stanton
full_name: Gelvin, Stanton
last_name: Gelvin
- first_name: Eva
full_name: Sýkorová, Eva
last_name: Sýkorová
citation:
ama: Dokládal L, Benková E, Honys D, et al. An armadillo-domain protein participates
in a telomerase interaction network. Plant Molecular Biology. 2018;97(5):407-420.
doi:10.1007/s11103-018-0747-4
apa: Dokládal, L., Benková, E., Honys, D., Dupláková, N., Lee, L., Gelvin, S., &
Sýkorová, E. (2018). An armadillo-domain protein participates in a telomerase
interaction network. Plant Molecular Biology. Springer. https://doi.org/10.1007/s11103-018-0747-4
chicago: Dokládal, Ladislav, Eva Benková, David Honys, Nikoleta Dupláková, Lan Lee,
Stanton Gelvin, and Eva Sýkorová. “An Armadillo-Domain Protein Participates in
a Telomerase Interaction Network.” Plant Molecular Biology. Springer, 2018.
https://doi.org/10.1007/s11103-018-0747-4.
ieee: L. Dokládal et al., “An armadillo-domain protein participates in a
telomerase interaction network,” Plant Molecular Biology, vol. 97, no.
5. Springer, pp. 407–420, 2018.
ista: Dokládal L, Benková E, Honys D, Dupláková N, Lee L, Gelvin S, Sýkorová E.
2018. An armadillo-domain protein participates in a telomerase interaction network.
Plant Molecular Biology. 97(5), 407–420.
mla: Dokládal, Ladislav, et al. “An Armadillo-Domain Protein Participates in a Telomerase
Interaction Network.” Plant Molecular Biology, vol. 97, no. 5, Springer,
2018, pp. 407–20, doi:10.1007/s11103-018-0747-4.
short: L. Dokládal, E. Benková, D. Honys, N. Dupláková, L. Lee, S. Gelvin, E. Sýkorová,
Plant Molecular Biology 97 (2018) 407–420.
date_created: 2018-12-11T11:45:34Z
date_published: 2018-06-12T00:00:00Z
date_updated: 2023-09-08T13:21:05Z
day: '12'
ddc:
- '580'
department:
- _id: EvBe
doi: 10.1007/s11103-018-0747-4
external_id:
isi:
- '000438981700009'
file:
- access_level: open_access
checksum: 451ae47616e6af2533099f596b2a47fb
content_type: application/pdf
creator: dernst
date_created: 2020-05-14T12:23:08Z
date_updated: 2020-07-14T12:45:45Z
file_id: '7834'
file_name: 2018_PlantMolecBio_Dokladal.pdf
file_size: 1150679
relation: main_file
file_date_updated: 2020-07-14T12:45:45Z
fulldoi: https://doi.org/10.1007/s11103-018-0747-4
has_accepted_license: '1'
intvolume: ' 97'
isi: 1
issue: '5'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
page: 407 - 420
publication: Plant Molecular Biology
publication_status: published
publisher: Springer
publist_id: '7625'
quality_controlled: '1'
scopus_import: '1'
status: public
title: An armadillo-domain protein participates in a telomerase interaction network
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 97
year: '2018'
...
---
OA_place: publisher
_id: '278'
abstract:
- lang: eng
text: 'Consortial subscription contracts regulate the digital access to publications
between publishers and scientific libraries. However, since a couple of years
the tendency towards a freely accessible publishing (Open Access) intensifies.
As a consequence of this trend the contractual relationship between licensor and
licensee is gradually changing as well: More and more contracts exercise influence
on open access publishing. The present study attempts to compare Austrian examples
of consortial licence contracts, which include components of open access. It describes
the difference between pure subscription contracts and differing innovative deals
including open access components. Thereby it becomes obvious that for the evaluation
of this licence contracts new methods are needed. An essential new element of
such analyses is the evaluation of the open access publication numbers. So this
study tries to carry out such publication analyses for Austrian open access deals
focusing on quantitative questions: How does the number of publications evolve?
How does the open access share change? Publications reports of the publishers
and database queries from Scopus form the data basis. The analysis of the data
points out that differing approaches of contracts result in highly divergent results:
Particular deals can prioritize a saving in costs or else the increase of the
open access rate. It is to be assumed that within the following years further
numerous open access deals will be negotiated. The finding of this study shall
provide guidance.'
article_processing_charge: No
author:
- first_name: Márton
full_name: Villányi, Márton
id: 3FFCCD3A-F248-11E8-B48F-1D18A9856A87
last_name: Villányi
orcid: 0000-0001-8126-0426
citation:
ama: Villányi M. Lizenzverträge mit Open-Access-Komponenten an österreichischen
Bibliotheken. 2018.
apa: Villányi, M. (2018). Lizenzverträge mit Open-Access-Komponenten an österreichischen
Bibliotheken. Universität Wien.
chicago: Villányi, Márton. “Lizenzverträge mit Open-Access-Komponenten an österreichischen
Bibliotheken.” Universität Wien, 2018.
ieee: M. Villányi, “Lizenzverträge mit Open-Access-Komponenten an österreichischen
Bibliotheken,” Universität Wien, 2018.
ista: Villányi M. 2018. Lizenzverträge mit Open-Access-Komponenten an österreichischen
Bibliotheken. Universität Wien.
mla: Villányi, Márton. Lizenzverträge mit Open-Access-Komponenten an österreichischen
Bibliotheken. Universität Wien, 2018.
short: M. Villányi, Lizenzverträge mit Open-Access-Komponenten an österreichischen
Bibliotheken, Universität Wien, 2018.
date_created: 2018-12-11T11:45:34Z
date_published: 2018-04-06T00:00:00Z
date_updated: 2026-06-18T18:35:07Z
day: '06'
ddc:
- '020'
department:
- _id: E-Lib
language:
- iso: ger
main_file_link:
- open_access: '1'
url: http://othes.univie.ac.at/51113/
month: '04'
oa: 1
oa_version: Published Version
page: '94'
publication_status: published
publisher: Universität Wien
publist_id: '7624'
related_material:
record:
- id: '5577'
relation: dissertation_contains
status: public
- id: '5574'
relation: dissertation_contains
status: public
- id: '5578'
relation: dissertation_contains
status: public
- id: '5579'
relation: dissertation_contains
status: public
- id: '5576'
relation: dissertation_contains
status: public
- id: '5575'
relation: dissertation_contains
status: public
- id: '5582'
relation: dissertation_contains
status: public
- id: '5581'
relation: dissertation_contains
status: public
- id: '5580'
relation: dissertation_contains
status: public
status: public
supervisor:
- first_name: Brigitte
full_name: Kromp, Brigitte
last_name: Kromp
title: Lizenzverträge mit Open-Access-Komponenten an österreichischen Bibliotheken
type: dissertation
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2018'
...
---
_id: '279'
abstract:
- lang: eng
text: 'Background: Natural selection shapes cancer genomes. Previous studies used
signatures of positive selection to identify genes driving malignant transformation.
However, the contribution of negative selection against somatic mutations that
affect essential tumor functions or specific domains remains a controversial topic.
Results: Here, we analyze 7546 individual exomes from 26 tumor types from TCGA
data to explore the portion of the cancer exome under negative selection. Although
we find most of the genes neutrally evolving in a pan-cancer framework, we identify
essential cancer genes and immune-exposed protein regions under significant negative
selection. Moreover, our simulations suggest that the amount of negative selection
is underestimated. We therefore choose an empirical approach to identify genes,
functions, and protein regions under negative selection. We find that expression
and mutation status of negatively selected genes is indicative of patient survival.
Processes that are most strongly conserved are those that play fundamental cellular
roles such as protein synthesis, glucose metabolism, and molecular transport.
Intriguingly, we observe strong signals of selection in the immunopeptidome and
proteins controlling peptide exposition, highlighting the importance of immune
surveillance evasion. Additionally, tumor type-specific immune activity correlates
with the strength of negative selection on human epitopes. Conclusions: In summary,
our results show that negative selection is a hallmark of cell essentiality and
immune response in cancer. The functional domains identified could be exploited
therapeutically, ultimately allowing for the development of novel cancer treatments.'
article_number: '67'
article_processing_charge: No
author:
- first_name: Luis
full_name: Zapata, Luis
last_name: Zapata
- first_name: Oriol
full_name: Pich, Oriol
last_name: Pich
- first_name: Luis
full_name: Serrano, Luis
last_name: Serrano
- first_name: Fyodor
full_name: Kondrashov, Fyodor
id: 44FDEF62-F248-11E8-B48F-1D18A9856A87
last_name: Kondrashov
orcid: 0000-0001-8243-4694
- first_name: Stephan
full_name: Ossowski, Stephan
last_name: Ossowski
- first_name: Martin
full_name: Schaefer, Martin
last_name: Schaefer
citation:
ama: Zapata L, Pich O, Serrano L, Kondrashov F, Ossowski S, Schaefer M. Negative
selection in tumor genome evolution acts on essential cellular functions and the
immunopeptidome. Genome Biology. 2018;19. doi:10.1186/s13059-018-1434-0
apa: Zapata, L., Pich, O., Serrano, L., Kondrashov, F., Ossowski, S., & Schaefer,
M. (2018). Negative selection in tumor genome evolution acts on essential cellular
functions and the immunopeptidome. Genome Biology. BioMed Central. https://doi.org/10.1186/s13059-018-1434-0
chicago: Zapata, Luis, Oriol Pich, Luis Serrano, Fyodor Kondrashov, Stephan Ossowski,
and Martin Schaefer. “Negative Selection in Tumor Genome Evolution Acts on Essential
Cellular Functions and the Immunopeptidome.” Genome Biology. BioMed Central,
2018. https://doi.org/10.1186/s13059-018-1434-0.
ieee: L. Zapata, O. Pich, L. Serrano, F. Kondrashov, S. Ossowski, and M. Schaefer,
“Negative selection in tumor genome evolution acts on essential cellular functions
and the immunopeptidome,” Genome Biology, vol. 19. BioMed Central, 2018.
ista: Zapata L, Pich O, Serrano L, Kondrashov F, Ossowski S, Schaefer M. 2018. Negative
selection in tumor genome evolution acts on essential cellular functions and the
immunopeptidome. Genome Biology. 19, 67.
mla: Zapata, Luis, et al. “Negative Selection in Tumor Genome Evolution Acts on
Essential Cellular Functions and the Immunopeptidome.” Genome Biology,
vol. 19, 67, BioMed Central, 2018, doi:10.1186/s13059-018-1434-0.
short: L. Zapata, O. Pich, L. Serrano, F. Kondrashov, S. Ossowski, M. Schaefer,
Genome Biology 19 (2018).
date_created: 2018-12-11T11:45:35Z
date_published: 2018-05-31T00:00:00Z
date_updated: 2025-04-15T08:30:30Z
day: '31'
ddc:
- '570'
department:
- _id: FyKo
doi: 10.1186/s13059-018-1434-0
ec_funded: 1
external_id:
isi:
- '000433986200001'
file:
- access_level: open_access
checksum: f3e4922486bd9bf1483271bdbed394a7
content_type: application/pdf
creator: dernst
date_created: 2018-12-17T14:05:01Z
date_updated: 2020-07-14T12:45:47Z
file_id: '5708'
file_name: 2018_GenomeBiology_Zapata.pdf
file_size: 1414722
relation: main_file
file_date_updated: 2020-07-14T12:45:47Z
fulldoi: https://doi.org/10.1186/s13059-018-1434-0
has_accepted_license: '1'
intvolume: ' 19'
isi: 1
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
project:
- _id: 26120F5C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '335980'
name: Systematic investigation of epistasis in molecular evolution
publication: Genome Biology
publication_status: published
publisher: BioMed Central
publist_id: '7620'
quality_controlled: '1'
related_material:
record:
- id: '9811'
relation: research_data
status: public
- id: '9812'
relation: research_data
status: public
scopus_import: '1'
status: public
title: Negative selection in tumor genome evolution acts on essential cellular functions
and the immunopeptidome
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: 19
year: '2018'
...