---
_id: '10898'
abstract:
- lang: eng
text: A prominent remedy to multicore scalability issues in concurrent data structure
implementations is to relax the sequential specification of the data structure.
We present distributed queues (DQ), a new family of relaxed concurrent queue implementations.
DQs implement relaxed queues with linearizable emptiness check and either configurable
or bounded out-of-order behavior or pool behavior. Our experiments show that DQs
outperform and outscale in micro- and macrobenchmarks all strict and relaxed queue
as well as pool implementations that we considered.
acknowledgement: This work has been supported by the European Research Council advanced
grant on Quantitative Reactive Modeling (QUAREM) and the National Research Network
RiSE on Rigorous Systems Engineering (Austrian Science Fund S11402-N23 and S11404-N23).
article_number: '17'
article_processing_charge: No
author:
- first_name: Andreas
full_name: Haas, Andreas
last_name: Haas
- first_name: Michael
full_name: Lippautz, Michael
last_name: Lippautz
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Hannes
full_name: Payer, Hannes
last_name: Payer
- first_name: Ana
full_name: Sokolova, Ana
last_name: Sokolova
- first_name: Christoph M.
full_name: Kirsch, Christoph M.
last_name: Kirsch
- first_name: Ali
full_name: Sezgin, Ali
id: 4C7638DA-F248-11E8-B48F-1D18A9856A87
last_name: Sezgin
citation:
ama: 'Haas A, Lippautz M, Henzinger TA, et al. Distributed queues in shared memory:
Multicore performance and scalability through quantitative relaxation. In: Proceedings
of the ACM International Conference on Computing Frontiers - CF ’13. ACM;
2013. doi:10.1145/2482767.2482789'
apa: 'Haas, A., Lippautz, M., Henzinger, T. A., Payer, H., Sokolova, A., Kirsch,
C. M., & Sezgin, A. (2013). Distributed queues in shared memory: Multicore
performance and scalability through quantitative relaxation. In Proceedings
of the ACM International Conference on Computing Frontiers - CF ’13. Ischia,
Italy: ACM. https://doi.org/10.1145/2482767.2482789'
chicago: 'Haas, Andreas, Michael Lippautz, Thomas A Henzinger, Hannes Payer, Ana
Sokolova, Christoph M. Kirsch, and Ali Sezgin. “Distributed Queues in Shared Memory:
Multicore Performance and Scalability through Quantitative Relaxation.” In Proceedings
of the ACM International Conference on Computing Frontiers - CF ’13. ACM,
2013. https://doi.org/10.1145/2482767.2482789.'
ieee: 'A. Haas et al., “Distributed queues in shared memory: Multicore performance
and scalability through quantitative relaxation,” in Proceedings of the ACM
International Conference on Computing Frontiers - CF ’13, Ischia, Italy, 2013,
no. 5.'
ista: 'Haas A, Lippautz M, Henzinger TA, Payer H, Sokolova A, Kirsch CM, Sezgin
A. 2013. Distributed queues in shared memory: Multicore performance and scalability
through quantitative relaxation. Proceedings of the ACM International Conference
on Computing Frontiers - CF ’13. CF: Conference on Computing Frontiers, 17.'
mla: 'Haas, Andreas, et al. “Distributed Queues in Shared Memory: Multicore Performance
and Scalability through Quantitative Relaxation.” Proceedings of the ACM International
Conference on Computing Frontiers - CF ’13, no. 5, 17, ACM, 2013, doi:10.1145/2482767.2482789.'
short: A. Haas, M. Lippautz, T.A. Henzinger, H. Payer, A. Sokolova, C.M. Kirsch,
A. Sezgin, in:, Proceedings of the ACM International Conference on Computing Frontiers
- CF ’13, ACM, 2013.
conference:
end_date: 2013-05-16
location: Ischia, Italy
name: 'CF: Conference on Computing Frontiers'
start_date: 2013-05-14
date_created: 2022-03-21T07:33:22Z
date_published: 2013-05-14T00:00:00Z
date_updated: 2025-05-14T11:23:58Z
day: '14'
department:
- _id: ToHe
doi: 10.1145/2482767.2482789
ec_funded: 1
issue: '5'
language:
- iso: eng
month: '05'
oa_version: None
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication: Proceedings of the ACM International Conference on Computing Frontiers
- CF '13
publication_identifier:
isbn:
- 978-145032053-5
publication_status: published
publisher: ACM
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Distributed queues in shared memory: Multicore performance and scalability
through quantitative relaxation'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '10899'
article_processing_charge: No
author:
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
citation:
ama: 'Barton NH. Differentiation. In: Encyclopedia of Biodiversity. 2nd ed.
Elsevier; 2013:508-515. doi:10.1016/b978-0-12-384719-5.00031-9'
apa: Barton, N. H. (2013). Differentiation. In Encyclopedia of Biodiversity
(2nd ed., pp. 508–515). Elsevier. https://doi.org/10.1016/b978-0-12-384719-5.00031-9
chicago: Barton, Nicholas H. “Differentiation.” In Encyclopedia of Biodiversity,
2nd ed., 508–15. Elsevier, 2013. https://doi.org/10.1016/b978-0-12-384719-5.00031-9.
ieee: N. H. Barton, “Differentiation,” in Encyclopedia of Biodiversity, 2nd
ed., Elsevier, 2013, pp. 508–515.
ista: 'Barton NH. 2013.Differentiation. In: Encyclopedia of Biodiversity. , 508–515.'
mla: Barton, Nicholas H. “Differentiation.” Encyclopedia of Biodiversity,
2nd ed., Elsevier, 2013, pp. 508–15, doi:10.1016/b978-0-12-384719-5.00031-9.
short: N.H. Barton, in:, Encyclopedia of Biodiversity, 2nd ed., Elsevier, 2013,
pp. 508–515.
corr_author: '1'
date_created: 2022-03-21T07:46:22Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2024-10-09T21:02:37Z
day: '01'
department:
- _id: NiBa
doi: 10.1016/b978-0-12-384719-5.00031-9
edition: '2'
keyword:
- Adaptive landscape
- Cline
- Coalescent process
- Gene flow
- Hybrid zone
- Local adaptation
- Natural selection
- Neutral theory
- Population structure
- Speciation
language:
- iso: eng
month: '01'
oa_version: None
page: 508-515
publication: Encyclopedia of Biodiversity
publication_identifier:
isbn:
- 978-0-12-384720-1
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Differentiation
type: book_chapter
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '10900'
abstract:
- lang: eng
text: Leukocyte migration through the interstitial space is crucial for the maintenance
of tolerance and immunity. The main cues for leukocyte trafficking are chemokines
thought to directionally guide these cells towards their targets. However, model
systems that facilitate quantification of chemokine-guided leukocyte migration
in vivo are uncommon. Here we describe an ex vivo crawl-in assay using explanted
mouse ears that allows the visualization of chemokine-dependent dendritic cell
(DC) motility in the dermal interstitium in real time. We present methods for
the preparation of mouse ear sheets and their use in multidimensional confocal
imaging experiments to monitor and analyze the directional migration of fluorescently
labelled DCs through the dermis and into afferent lymphatic vessels. The assay
provides a more physiological approach to study leukocyte migration than in vitro
three-dimensional (3D) or 2-dimensional (2D) migration assays such as collagen
gels and transwell assays.
acknowledgement: We would like to thank Alexander Eichner and Ingrid de Vries for
discussion and critical reading of the manuscript, and Mary Frank for assistance
with the recording of videos and images in Fig. 1. M.S. is supported through funding
from the German Research Foundation (DFG). M.W. acknowledges the Alexander von Humboldt
Foundation for funding.
alternative_title:
- Methods in Molecular Biology
article_processing_charge: No
author:
- first_name: Michele
full_name: Weber, Michele
id: 3A3FC708-F248-11E8-B48F-1D18A9856A87
last_name: Weber
- first_name: Michael K
full_name: Sixt, Michael K
id: 41E9FBEA-F248-11E8-B48F-1D18A9856A87
last_name: Sixt
orcid: 0000-0002-6620-9179
citation:
ama: 'Weber M, Sixt MK. Live Cell Imaging of Chemotactic Dendritic Cell Migration
in Explanted Mouse Ear Preparations. In: Cardona A, Ubogu E, eds. Chemokines.
Vol 1013. MIMB. Totowa, NJ: Humana Press; 2013:215-226. doi:10.1007/978-1-62703-426-5_14'
apa: 'Weber, M., & Sixt, M. K. (2013). Live Cell Imaging of Chemotactic Dendritic
Cell Migration in Explanted Mouse Ear Preparations. In A. Cardona & E. Ubogu
(Eds.), Chemokines (Vol. 1013, pp. 215–226). Totowa, NJ: Humana Press.
https://doi.org/10.1007/978-1-62703-426-5_14'
chicago: 'Weber, Michele, and Michael K Sixt. “Live Cell Imaging of Chemotactic
Dendritic Cell Migration in Explanted Mouse Ear Preparations.” In Chemokines,
edited by Astrid Cardona and Eroboghene Ubogu, 1013:215–26. MIMB. Totowa, NJ:
Humana Press, 2013. https://doi.org/10.1007/978-1-62703-426-5_14.'
ieee: 'M. Weber and M. K. Sixt, “Live Cell Imaging of Chemotactic Dendritic Cell
Migration in Explanted Mouse Ear Preparations,” in Chemokines, vol. 1013,
A. Cardona and E. Ubogu, Eds. Totowa, NJ: Humana Press, 2013, pp. 215–226.'
ista: 'Weber M, Sixt MK. 2013.Live Cell Imaging of Chemotactic Dendritic Cell Migration
in Explanted Mouse Ear Preparations. In: Chemokines. Methods in Molecular Biology,
vol. 1013, 215–226.'
mla: Weber, Michele, and Michael K. Sixt. “Live Cell Imaging of Chemotactic Dendritic
Cell Migration in Explanted Mouse Ear Preparations.” Chemokines, edited
by Astrid Cardona and Eroboghene Ubogu, vol. 1013, Humana Press, 2013, pp. 215–26,
doi:10.1007/978-1-62703-426-5_14.
short: M. Weber, M.K. Sixt, in:, A. Cardona, E. Ubogu (Eds.), Chemokines, Humana
Press, Totowa, NJ, 2013, pp. 215–226.
corr_author: '1'
date_created: 2022-03-21T07:47:41Z
date_published: 2013-04-03T00:00:00Z
date_updated: 2024-10-09T21:02:37Z
day: '03'
department:
- _id: MiSi
doi: 10.1007/978-1-62703-426-5_14
editor:
- first_name: Astrid
full_name: Cardona, Astrid
last_name: Cardona
- first_name: Eroboghene
full_name: Ubogu, Eroboghene
last_name: Ubogu
external_id:
pmid:
- '23625502'
intvolume: ' 1013'
language:
- iso: eng
month: '04'
oa_version: None
page: 215-226
place: Totowa, NJ
pmid: 1
publication: Chemokines
publication_identifier:
eisbn:
- '9781627034265'
eissn:
- 1940-6029
isbn:
- '9781627034258'
issn:
- 1064-3745
publication_status: published
publisher: Humana Press
quality_controlled: '1'
scopus_import: '1'
series_title: MIMB
status: public
title: Live Cell Imaging of Chemotactic Dendritic Cell Migration in Explanted Mouse
Ear Preparations
type: book_chapter
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 1013
year: '2013'
...
---
_id: '10902'
abstract:
- lang: eng
text: We consider how to edit strings from a source language so that the edited
strings belong to a target language, where the languages are given as deterministic
finite automata. Non-streaming (or offline) transducers perform edits given the
whole source string. We show that the class of deterministic one-pass transducers
with registers along with increment and min operation suffices for computing optimal
edit distance, whereas the same class of transducers without the min operation
is not sufficient. Streaming (or online) transducers perform edits as the letters
of the source string are received. We present a polynomial time algorithm for
the partial-repair problem that given a bound α asks for the construction of a
deterministic streaming transducer (if one exists) that ensures that the ‘maximum
fraction’ η of the strings of the source language are edited, within cost α, to
the target language.
acknowledgement: 'The research was supported by Austrian Science Fund (FWF) Grant
No P 23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph
Games), and Microsoft faculty fellows award. Thanks to Gabriele Puppis for suggesting
the problem of identifying a deterministic transducer to compute the optimal cost,
and to Martin Chmelik for his comments on the introduction.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Siddhesh
full_name: Chaubal, Siddhesh
last_name: Chaubal
- first_name: Sasha
full_name: Rubin, Sasha
id: 2EC51194-F248-11E8-B48F-1D18A9856A87
last_name: Rubin
citation:
ama: 'Chatterjee K, Chaubal S, Rubin S. How to travel between languages. In: 7th
International Conference on Language and Automata Theory and Applications.
Vol 7810. LNCS. Berlin, Heidelberg: Springer Nature; 2013:214-225. doi:10.1007/978-3-642-37064-9_20'
apa: 'Chatterjee, K., Chaubal, S., & Rubin, S. (2013). How to travel between
languages. In 7th International Conference on Language and Automata Theory
and Applications (Vol. 7810, pp. 214–225). Berlin, Heidelberg: Springer Nature.
https://doi.org/10.1007/978-3-642-37064-9_20'
chicago: 'Chatterjee, Krishnendu, Siddhesh Chaubal, and Sasha Rubin. “How to Travel
between Languages.” In 7th International Conference on Language and Automata
Theory and Applications, 7810:214–25. LNCS. Berlin, Heidelberg: Springer Nature,
2013. https://doi.org/10.1007/978-3-642-37064-9_20.'
ieee: K. Chatterjee, S. Chaubal, and S. Rubin, “How to travel between languages,”
in 7th International Conference on Language and Automata Theory and Applications,
Bilbao, Spain, 2013, vol. 7810, pp. 214–225.
ista: 'Chatterjee K, Chaubal S, Rubin S. 2013. How to travel between languages.
7th International Conference on Language and Automata Theory and Applications.
LATA: Language and Automata Theory and ApplicationsLNCS, LNCS, vol. 7810, 214–225.'
mla: Chatterjee, Krishnendu, et al. “How to Travel between Languages.” 7th International
Conference on Language and Automata Theory and Applications, vol. 7810, Springer
Nature, 2013, pp. 214–25, doi:10.1007/978-3-642-37064-9_20.
short: K. Chatterjee, S. Chaubal, S. Rubin, in:, 7th International Conference on
Language and Automata Theory and Applications, Springer Nature, Berlin, Heidelberg,
2013, pp. 214–225.
conference:
end_date: 2013-04-05
location: Bilbao, Spain
name: 'LATA: Language and Automata Theory and Applications'
start_date: 2013-04-02
corr_author: '1'
date_created: 2022-03-21T07:56:21Z
date_published: 2013-04-15T00:00:00Z
date_updated: 2025-07-10T11:50:03Z
day: '15'
department:
- _id: KrCh
doi: 10.1007/978-3-642-37064-9_20
ec_funded: 1
intvolume: ' 7810'
language:
- iso: eng
month: '04'
oa_version: None
page: 214-225
place: Berlin, Heidelberg
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: 7th International Conference on Language and Automata Theory and Applications
publication_identifier:
eisbn:
- '9783642370649'
eissn:
- 1611-3349
isbn:
- '9783642370632'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: How to travel between languages
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7810
year: '2013'
...
---
_id: '11083'
abstract:
- lang: eng
text: Nuclear pore complex (NPC) proteins are known for their critical roles in
regulating nucleocytoplasmic traffic of macromolecules across the nuclear envelope.
However, recent findings suggest that some nucleoporins (Nups), including Nup98,
have additional functions in developmental gene regulation. Nup98, which exhibits
transcription-dependent mobility at the NPC but can also bind chromatin away from
the nuclear envelope, is frequently involved in chromosomal translocations in
a subset of patients suffering from acute myeloid leukemia (AML). A common paradigm
suggests that Nup98 translocations cause aberrant transcription when they are
recuited to aberrant genomic loci. Importantly, this model fails to account for
the potential loss of wild type (WT) Nup98 function in the presence of Nup98 translocation
mutants. Here we examine how the cell might regulate Nup98 nucleoplasmic protein
levels to control transcription in healthy cells. In addition, we discuss the
possibility that dominant negative Nup98 fusion proteins disrupt the transcriptional
activity of WT Nup98 in the nucleoplasm to drive AML.
article_processing_charge: No
article_type: letter_note
author:
- first_name: Tobias M.
full_name: Franks, Tobias M.
last_name: Franks
- first_name: Martin W
full_name: HETZER, Martin W
id: 86c0d31b-b4eb-11ec-ac5a-eae7b2e135ed
last_name: HETZER
orcid: 0000-0002-2111-992X
citation:
ama: Franks TM, Hetzer M. The role of Nup98 in transcription regulation in healthy
and diseased cells. Trends in Cell Biology. 2013;23(3):112-117. doi:10.1016/j.tcb.2012.10.013
apa: Franks, T. M., & Hetzer, M. (2013). The role of Nup98 in transcription
regulation in healthy and diseased cells. Trends in Cell Biology. Elsevier.
https://doi.org/10.1016/j.tcb.2012.10.013
chicago: Franks, Tobias M., and Martin Hetzer. “The Role of Nup98 in Transcription
Regulation in Healthy and Diseased Cells.” Trends in Cell Biology. Elsevier,
2013. https://doi.org/10.1016/j.tcb.2012.10.013.
ieee: T. M. Franks and M. Hetzer, “The role of Nup98 in transcription regulation
in healthy and diseased cells,” Trends in Cell Biology, vol. 23, no. 3.
Elsevier, pp. 112–117, 2013.
ista: Franks TM, Hetzer M. 2013. The role of Nup98 in transcription regulation in
healthy and diseased cells. Trends in Cell Biology. 23(3), 112–117.
mla: Franks, Tobias M., and Martin Hetzer. “The Role of Nup98 in Transcription Regulation
in Healthy and Diseased Cells.” Trends in Cell Biology, vol. 23, no. 3,
Elsevier, 2013, pp. 112–17, doi:10.1016/j.tcb.2012.10.013.
short: T.M. Franks, M. Hetzer, Trends in Cell Biology 23 (2013) 112–117.
date_created: 2022-04-07T07:50:33Z
date_published: 2013-03-01T00:00:00Z
date_updated: 2024-10-14T11:23:44Z
day: '01'
doi: 10.1016/j.tcb.2012.10.013
extern: '1'
external_id:
pmid:
- '23246429'
intvolume: ' 23'
issue: '3'
keyword:
- Cell Biology
language:
- iso: eng
month: '03'
oa_version: None
page: 112-117
pmid: 1
publication: Trends in Cell Biology
publication_identifier:
issn:
- 0962-8924
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: The role of Nup98 in transcription regulation in healthy and diseased cells
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 23
year: '2013'
...
---
_id: '11084'
abstract:
- lang: eng
text: Protein turnover is an effective way of maintaining a functional proteome,
as old and potentially damaged polypeptides are destroyed and replaced by newly
synthesized copies. An increasing number of intracellular proteins, however, have
been identified that evade this turnover process and instead are maintained over
a cell's lifetime. This diverse group of long-lived proteins might be particularly
prone to accumulation of damage and thus have a crucial role in the functional
deterioration of key regulatory processes during ageing.
article_processing_charge: No
article_type: original
author:
- first_name: Brandon H.
full_name: Toyama, Brandon H.
last_name: Toyama
- first_name: Martin W
full_name: HETZER, Martin W
id: 86c0d31b-b4eb-11ec-ac5a-eae7b2e135ed
last_name: HETZER
orcid: 0000-0002-2111-992X
citation:
ama: 'Toyama BH, Hetzer M. Protein homeostasis: Live long, won’t prosper. Nature
Reviews Molecular Cell Biology. 2013;14:55-61. doi:10.1038/nrm3496'
apa: 'Toyama, B. H., & Hetzer, M. (2013). Protein homeostasis: Live long, won’t
prosper. Nature Reviews Molecular Cell Biology. Springer Nature. https://doi.org/10.1038/nrm3496'
chicago: 'Toyama, Brandon H., and Martin Hetzer. “Protein Homeostasis: Live Long,
Won’t Prosper.” Nature Reviews Molecular Cell Biology. Springer Nature,
2013. https://doi.org/10.1038/nrm3496.'
ieee: 'B. H. Toyama and M. Hetzer, “Protein homeostasis: Live long, won’t prosper,”
Nature Reviews Molecular Cell Biology, vol. 14. Springer Nature, pp. 55–61,
2013.'
ista: 'Toyama BH, Hetzer M. 2013. Protein homeostasis: Live long, won’t prosper.
Nature Reviews Molecular Cell Biology. 14, 55–61.'
mla: 'Toyama, Brandon H., and Martin Hetzer. “Protein Homeostasis: Live Long, Won’t
Prosper.” Nature Reviews Molecular Cell Biology, vol. 14, Springer Nature,
2013, pp. 55–61, doi:10.1038/nrm3496.'
short: B.H. Toyama, M. Hetzer, Nature Reviews Molecular Cell Biology 14 (2013) 55–61.
date_created: 2022-04-07T07:50:43Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2024-10-14T11:24:09Z
day: '01'
doi: 10.1038/nrm3496
extern: '1'
external_id:
pmid:
- '23258296'
intvolume: ' 14'
keyword:
- Cell Biology
- Molecular Biology
language:
- iso: eng
month: '01'
oa_version: None
page: 55-61
pmid: 1
publication: Nature Reviews Molecular Cell Biology
publication_identifier:
issn:
- 1471-0072
- 1471-0080
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Protein homeostasis: Live long, won''t prosper'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14
year: '2013'
...
---
_id: '11085'
abstract:
- lang: eng
text: During mitotic exit, missegregated chromosomes can recruit their own nuclear
envelope (NE) to form micronuclei (MN). MN have reduced functioning compared to
primary nuclei in the same cell, although the two compartments appear to be structurally
comparable. Here we show that over 60% of MN undergo an irreversible loss of compartmentalization
during interphase due to NE collapse. This disruption of the MN, which is induced
by defects in nuclear lamina assembly, drastically reduces nuclear functions and
can trigger massive DNA damage. MN disruption is associated with chromatin compaction
and invasion of endoplasmic reticulum (ER) tubules into the chromatin. We identified
disrupted MN in both major subtypes of human non-small-cell lung cancer, suggesting
that disrupted MN could be a useful objective biomarker for genomic instability
in solid tumors. Our study shows that NE collapse is a key event underlying MN
dysfunction and establishes a link between aberrant NE organization and aneuploidy.
article_processing_charge: No
article_type: original
author:
- first_name: Emily M.
full_name: Hatch, Emily M.
last_name: Hatch
- first_name: Andrew H.
full_name: Fischer, Andrew H.
last_name: Fischer
- first_name: Thomas J.
full_name: Deerinck, Thomas J.
last_name: Deerinck
- first_name: Martin W
full_name: HETZER, Martin W
id: 86c0d31b-b4eb-11ec-ac5a-eae7b2e135ed
last_name: HETZER
orcid: 0000-0002-2111-992X
citation:
ama: Hatch EM, Fischer AH, Deerinck TJ, Hetzer M. Catastrophic nuclear envelope
collapse in cancer cell micronuclei. Cell. 2013;154(1):47-60. doi:10.1016/j.cell.2013.06.007
apa: Hatch, E. M., Fischer, A. H., Deerinck, T. J., & Hetzer, M. (2013). Catastrophic
nuclear envelope collapse in cancer cell micronuclei. Cell. Elsevier. https://doi.org/10.1016/j.cell.2013.06.007
chicago: Hatch, Emily M., Andrew H. Fischer, Thomas J. Deerinck, and Martin Hetzer.
“Catastrophic Nuclear Envelope Collapse in Cancer Cell Micronuclei.” Cell.
Elsevier, 2013. https://doi.org/10.1016/j.cell.2013.06.007.
ieee: E. M. Hatch, A. H. Fischer, T. J. Deerinck, and M. Hetzer, “Catastrophic nuclear
envelope collapse in cancer cell micronuclei,” Cell, vol. 154, no. 1. Elsevier,
pp. 47–60, 2013.
ista: Hatch EM, Fischer AH, Deerinck TJ, Hetzer M. 2013. Catastrophic nuclear envelope
collapse in cancer cell micronuclei. Cell. 154(1), 47–60.
mla: Hatch, Emily M., et al. “Catastrophic Nuclear Envelope Collapse in Cancer Cell
Micronuclei.” Cell, vol. 154, no. 1, Elsevier, 2013, pp. 47–60, doi:10.1016/j.cell.2013.06.007.
short: E.M. Hatch, A.H. Fischer, T.J. Deerinck, M. Hetzer, Cell 154 (2013) 47–60.
date_created: 2022-04-07T07:50:51Z
date_published: 2013-07-03T00:00:00Z
date_updated: 2024-10-14T11:24:29Z
day: '03'
doi: 10.1016/j.cell.2013.06.007
extern: '1'
external_id:
pmid:
- '23827674'
intvolume: ' 154'
issue: '1'
keyword:
- General Biochemistry
- Genetics and Molecular Biology
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1016/j.cell.2013.06.007
month: '07'
oa: 1
oa_version: Published Version
page: 47-60
pmid: 1
publication: Cell
publication_identifier:
issn:
- 0092-8674
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Catastrophic nuclear envelope collapse in cancer cell micronuclei
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 154
year: '2013'
...
---
_id: '11086'
abstract:
- lang: eng
text: Faithful execution of developmental gene expression programs occurs at multiple
levels and involves many different components such as transcription factors, histone-modification
enzymes, and mRNA processing proteins. Recent evidence suggests that nucleoporins,
well known components that control nucleo-cytoplasmic trafficking, have wide-ranging
functions in developmental gene regulation that potentially extend beyond their
role in nuclear transport. Whether the unexpected role of nuclear pore proteins
in transcription regulation, which initially has been described in fungi and flies,
also applies to human cells is unknown. Here we show at a genome-wide level that
the nuclear pore protein NUP98 associates with developmentally regulated genes
active during human embryonic stem cell differentiation. Overexpression of a dominant
negative fragment of NUP98 levels decreases expression levels of NUP98-bound genes.
In addition, we identify two modes of developmental gene regulation by NUP98 that
are differentiated by the spatial localization of NUP98 target genes. Genes in
the initial stage of developmental induction can associate with NUP98 that is
embedded in the nuclear pores at the nuclear periphery. Alternatively, genes that
are highly induced can interact with NUP98 in the nuclear interior, away from
the nuclear pores. This work demonstrates for the first time that NUP98 dynamically
associates with the human genome during differentiation, revealing a role of a
nuclear pore protein in regulating developmental gene expression programs.
article_number: e1003308
article_processing_charge: No
article_type: original
author:
- first_name: Yun
full_name: Liang, Yun
last_name: Liang
- first_name: Tobias M.
full_name: Franks, Tobias M.
last_name: Franks
- first_name: Maria C.
full_name: Marchetto, Maria C.
last_name: Marchetto
- first_name: Fred H.
full_name: Gage, Fred H.
last_name: Gage
- first_name: Martin W
full_name: HETZER, Martin W
id: 86c0d31b-b4eb-11ec-ac5a-eae7b2e135ed
last_name: HETZER
orcid: 0000-0002-2111-992X
citation:
ama: Liang Y, Franks TM, Marchetto MC, Gage FH, Hetzer M. Dynamic association of
NUP98 with the human genome. PLoS Genetics. 2013;9(2). doi:10.1371/journal.pgen.1003308
apa: Liang, Y., Franks, T. M., Marchetto, M. C., Gage, F. H., & Hetzer, M. (2013).
Dynamic association of NUP98 with the human genome. PLoS Genetics. Public
Library of Science. https://doi.org/10.1371/journal.pgen.1003308
chicago: Liang, Yun, Tobias M. Franks, Maria C. Marchetto, Fred H. Gage, and Martin
Hetzer. “Dynamic Association of NUP98 with the Human Genome.” PLoS Genetics.
Public Library of Science, 2013. https://doi.org/10.1371/journal.pgen.1003308.
ieee: Y. Liang, T. M. Franks, M. C. Marchetto, F. H. Gage, and M. Hetzer, “Dynamic
association of NUP98 with the human genome,” PLoS Genetics, vol. 9, no.
2. Public Library of Science, 2013.
ista: Liang Y, Franks TM, Marchetto MC, Gage FH, Hetzer M. 2013. Dynamic association
of NUP98 with the human genome. PLoS Genetics. 9(2), e1003308.
mla: Liang, Yun, et al. “Dynamic Association of NUP98 with the Human Genome.” PLoS
Genetics, vol. 9, no. 2, e1003308, Public Library of Science, 2013, doi:10.1371/journal.pgen.1003308.
short: Y. Liang, T.M. Franks, M.C. Marchetto, F.H. Gage, M. Hetzer, PLoS Genetics
9 (2013).
date_created: 2022-04-07T07:50:59Z
date_published: 2013-02-28T00:00:00Z
date_updated: 2024-10-14T11:24:40Z
day: '28'
doi: 10.1371/journal.pgen.1003308
extern: '1'
external_id:
pmid:
- '23468646'
intvolume: ' 9'
issue: '2'
keyword:
- Cancer Research
- Genetics (clinical)
- Genetics
- Molecular Biology
- Ecology
- Evolution
- Behavior and Systematics
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1371/journal.pgen.1003308
month: '02'
oa: 1
oa_version: Published Version
pmid: 1
publication: PLoS Genetics
publication_identifier:
issn:
- 1553-7404
publication_status: published
publisher: Public Library of Science
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamic association of NUP98 with the human genome
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9
year: '2013'
...
---
_id: '11088'
abstract:
- lang: eng
text: 'The crowded intracellular environment poses a formidable challenge to experimental
and theoretical analyses of intracellular transport mechanisms. Our measurements
of single-particle trajectories in cytoplasm and their random-walk interpretations
elucidate two of these mechanisms: molecular diffusion in crowded environments
and cytoskeletal transport along microtubules. We employed acousto-optic deflector
microscopy to map out the three-dimensional trajectories of microspheres migrating
in the cytosolic fraction of a cellular extract. Classical Brownian motion (BM),
continuous time random walk, and fractional BM were alternatively used to represent
these trajectories. The comparison of the experimental and numerical data demonstrates
that cytoskeletal transport along microtubules and diffusion in the cytosolic
fraction exhibit anomalous (nonFickian) behavior and posses statistically distinct
signatures. Among the three random-walk models used, continuous time random walk
provides the best representation of diffusion, whereas microtubular transport
is accurately modeled with fractional BM.'
article_processing_charge: No
article_type: original
author:
- first_name: Benjamin M.
full_name: Regner, Benjamin M.
last_name: Regner
- first_name: Dejan
full_name: Vučinić, Dejan
last_name: Vučinić
- first_name: Cristina
full_name: Domnisoru, Cristina
last_name: Domnisoru
- first_name: Thomas M.
full_name: Bartol, Thomas M.
last_name: Bartol
- first_name: Martin W
full_name: HETZER, Martin W
id: 86c0d31b-b4eb-11ec-ac5a-eae7b2e135ed
last_name: HETZER
orcid: 0000-0002-2111-992X
- first_name: Daniel M.
full_name: Tartakovsky, Daniel M.
last_name: Tartakovsky
- first_name: Terrence J.
full_name: Sejnowski, Terrence J.
last_name: Sejnowski
citation:
ama: Regner BM, Vučinić D, Domnisoru C, et al. Anomalous diffusion of single particles
in cytoplasm. Biophysical Journal. 2013;104(8):1652-1660. doi:10.1016/j.bpj.2013.01.049
apa: Regner, B. M., Vučinić, D., Domnisoru, C., Bartol, T. M., Hetzer, M., Tartakovsky,
D. M., & Sejnowski, T. J. (2013). Anomalous diffusion of single particles
in cytoplasm. Biophysical Journal. Elsevier. https://doi.org/10.1016/j.bpj.2013.01.049
chicago: Regner, Benjamin M., Dejan Vučinić, Cristina Domnisoru, Thomas M. Bartol,
Martin Hetzer, Daniel M. Tartakovsky, and Terrence J. Sejnowski. “Anomalous Diffusion
of Single Particles in Cytoplasm.” Biophysical Journal. Elsevier, 2013.
https://doi.org/10.1016/j.bpj.2013.01.049.
ieee: B. M. Regner et al., “Anomalous diffusion of single particles in cytoplasm,”
Biophysical Journal, vol. 104, no. 8. Elsevier, pp. 1652–1660, 2013.
ista: Regner BM, Vučinić D, Domnisoru C, Bartol TM, Hetzer M, Tartakovsky DM, Sejnowski
TJ. 2013. Anomalous diffusion of single particles in cytoplasm. Biophysical Journal.
104(8), 1652–1660.
mla: Regner, Benjamin M., et al. “Anomalous Diffusion of Single Particles in Cytoplasm.”
Biophysical Journal, vol. 104, no. 8, Elsevier, 2013, pp. 1652–60, doi:10.1016/j.bpj.2013.01.049.
short: B.M. Regner, D. Vučinić, C. Domnisoru, T.M. Bartol, M. Hetzer, D.M. Tartakovsky,
T.J. Sejnowski, Biophysical Journal 104 (2013) 1652–1660.
date_created: 2022-04-07T07:51:26Z
date_published: 2013-04-16T00:00:00Z
date_updated: 2022-07-18T08:51:01Z
day: '16'
doi: 10.1016/j.bpj.2013.01.049
extern: '1'
external_id:
pmid:
- '23601312'
intvolume: ' 104'
issue: '8'
keyword:
- Biophysics
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1016/j.bpj.2013.01.049
month: '04'
oa: 1
oa_version: Published Version
page: 1652-1660
pmid: 1
publication: Biophysical Journal
publication_identifier:
issn:
- 0006-3495
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Anomalous diffusion of single particles in cytoplasm
type: journal_article
user_id: 72615eeb-f1f3-11ec-aa25-d4573ddc34fd
volume: 104
year: '2013'
...
---
_id: '115'
abstract:
- lang: eng
text: We present the design and performance characterization of a new experimental
technique for measuring individual particle charges in large ensembles of macroscopic
grains. The measurement principle is qualitatively similar to that used in determining
the elementary charge by Millikan in that it follows individual particle trajectories.
However, by taking advantage of new technology we are able to work with macroscopic
grains and achieve several orders of magnitude better resolution in charge to
mass ratios. By observing freely falling grains accelerated in a horizontal electric
field with a co-falling, high-speed video camera, we dramatically increase particle
tracking time and measurement precision. Keeping the granular medium under vacuum,
we eliminate air drag, leaving the electrostatic force as the primary source of
particle accelerations in the co-moving frame. Because the technique is based
on direct imaging, we can distinguish between different particle types during
the experiment, opening up the possibility of studying charge transfer processes
between different particle species. For the ∼300 μm diameter grains reported here,
we achieve an average acceleration resolution of ∼0.008 m/s2, a force resolution
of ∼500 pN, and a median charge resolution ∼6× 104 elementary charges per grain
(corresponding to surface charge densities ∼1 elementary charges per μm2). The
primary source of error is indeterminacy in the grain mass, but with higher resolution
cameras and better optics this can be further improved. The high degree of resolution
and the ability to visually identify particles of different species or sizes with
direct imaging make this a powerful new tool to characterize charging processes
in granular media.
acknowledgement: This work was supported financially by the National Science Foundation
(NSF) through its Materials Research Science and Engineering Center (MRSEC) program
(DMR-0820054) and by the US Army Research Office through Grant No. W911NF-12-1-0182.
S.R.W. acknowledges support from a University of Chicago Millikan Fellowship.
article_number: '025104'
author:
- first_name: Scott R
full_name: Waitukaitis, Scott R
id: 3A1FFC16-F248-11E8-B48F-1D18A9856A87
last_name: Waitukaitis
orcid: 0000-0002-2299-3176
- first_name: Heinrich
full_name: Jaeger, Heinrich
last_name: Jaeger
citation:
ama: Waitukaitis SR, Jaeger H. In situ granular charge measurement by free-fall
videography. Review of Scientific Instruments. 2013;84(2). doi:10.1063/1.4789496
apa: Waitukaitis, S. R., & Jaeger, H. (2013). In situ granular charge measurement
by free-fall videography. Review of Scientific Instruments. AIP. https://doi.org/10.1063/1.4789496
chicago: Waitukaitis, Scott R, and Heinrich Jaeger. “In Situ Granular Charge Measurement
by Free-Fall Videography.” Review of Scientific Instruments. AIP, 2013.
https://doi.org/10.1063/1.4789496.
ieee: S. R. Waitukaitis and H. Jaeger, “In situ granular charge measurement by free-fall
videography,” Review of Scientific Instruments, vol. 84, no. 2. AIP, 2013.
ista: Waitukaitis SR, Jaeger H. 2013. In situ granular charge measurement by free-fall
videography. Review of Scientific Instruments. 84(2), 025104.
mla: Waitukaitis, Scott R., and Heinrich Jaeger. “In Situ Granular Charge Measurement
by Free-Fall Videography.” Review of Scientific Instruments, vol. 84, no.
2, 025104, AIP, 2013, doi:10.1063/1.4789496.
short: S.R. Waitukaitis, H. Jaeger, Review of Scientific Instruments 84 (2013).
date_created: 2018-12-11T11:44:42Z
date_published: 2013-02-07T00:00:00Z
date_updated: 2021-01-12T06:48:39Z
day: '07'
doi: 10.1063/1.4789496
extern: '1'
intvolume: ' 84'
issue: '2'
language:
- iso: eng
month: '02'
oa_version: None
publication: Review of Scientific Instruments
publication_status: published
publisher: AIP
publist_id: '7939'
quality_controlled: '1'
status: public
title: In situ granular charge measurement by free-fall videography
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 84
year: '2013'
...
---
_id: '11520'
abstract:
- lang: eng
text: We present the spatially resolved Hα dynamics of 16 star-forming galaxies
at z ∼ 0.81 using the new KMOS multi-object integral field spectrograph on the
ESO Very Large Telescope. These galaxies, selected using 1.18 μm narrowband imaging
from the 10 deg2 CFHT-HiZELS survey of the SA 22 hr field, are found in a ∼4 Mpc
overdensity of Hα emitters and likely reside in a group/intermediate environment,
but not a cluster. We confirm and identify a rich group of star-forming galaxies
at z = 0.813 ± 0.003, with 13 galaxies within 1000 km s−1 of each other, and seven
within a diameter of 3 Mpc. All of our galaxies are “typical” star-forming galaxies
at their redshift, 0.8 ± 0.4 SFR$^*_{z = 0.8}$, spanning a range of specific star
formation rates (sSFRs) of 0.2–1.1 Gyr−1 and have a median metallicity very close
to solar of 12 + log(O/H) = 8.62 ± 0.06. We measure the spatially resolved Hα
dynamics of the galaxies in our sample and show that 13 out of 16 galaxies can
be described by rotating disks and use the data to derive inclination corrected
rotation speeds of 50–275 km s−1. The fraction of disks within our sample is 75%
± 8%, consistent with previous results based on Hubble Space Telescope morphologies
of Hα-selected galaxies at z ∼ 1 and confirming that disks dominate the SFR density
at z ∼ 1. Our Hα galaxies are well fitted by the z ∼ 1–2 Tully–Fisher (TF) relation,
confirming the evolution seen in the zero point. Apart from having, on average,
higher stellar masses and lower sSFRs, our group galaxies at z = 0.81 present
the same mass–metallicity and TF relation as z ∼ 1 field galaxies and are all
disk galaxies.
acknowledgement: 'We thank the referee for many helpful comments and suggestions which
greatly improved the clarity and quality of this work. D.S. acknowledges financial
support from the Netherlands Organisation for Scientific research (NWO) through
a Veni fellowship and also funding from the European Community Seventh Framework
Programme (FP7/2007-2013) under grant agreement number RG226604 (OPTICON) which
allowed access to CFHT time (proposals: 11BO29 & 12AO19). A.M.S. gratefully acknowledges
an STFC Advanced Fellowship through grant number ST/H005234/1. I.R.S., J.P.S., and
R.G.B. acknowledge support from the UK Science and Technology Facilities Council
(STFC) under ST/I001573/1. I.R.S. acknowledges STFC (ST/J001422/1), the ERC Advanced
Investigator program DUSTYGAL and a Royal Society/Wolfson Merit Award. P.N.B. acknowledges
support from STFC. R.M.S. acknowledges support from the grant ST/1001573/1. The
data presented here are based on observations with the KMOS spectrograph on the
ESO/VLT under program 60.A-9460 and can be accessed through the ESO data archive.
The authors also wish to acknowledge the help from Michael Hilker in preparing the
KMOS observations.'
article_number: '139'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: D.
full_name: Sobral, D.
last_name: Sobral
- first_name: A. M.
full_name: Swinbank, A. M.
last_name: Swinbank
- first_name: J. P.
full_name: Stott, J. P.
last_name: Stott
- first_name: Jorryt J
full_name: Matthee, Jorryt J
id: 7439a258-f3c0-11ec-9501-9df22fe06720
last_name: Matthee
orcid: 0000-0003-2871-127X
- first_name: R. G.
full_name: Bower, R. G.
last_name: Bower
- first_name: Ian
full_name: Smail, Ian
last_name: Smail
- first_name: P.
full_name: Best, P.
last_name: Best
- first_name: J. E.
full_name: Geach, J. E.
last_name: Geach
- first_name: R. M.
full_name: Sharples, R. M.
last_name: Sharples
citation:
ama: Sobral D, Swinbank AM, Stott JP, et al. The dynamics of z=0.8 H-alpha-selected
star-forming galaxies from KMOS/CF-HiZELS. The Astrophysical Journal. 2013;779(2).
doi:10.1088/0004-637x/779/2/139
apa: Sobral, D., Swinbank, A. M., Stott, J. P., Matthee, J. J., Bower, R. G., Smail,
I., … Sharples, R. M. (2013). The dynamics of z=0.8 H-alpha-selected star-forming
galaxies from KMOS/CF-HiZELS. The Astrophysical Journal. IOP Publishing.
https://doi.org/10.1088/0004-637x/779/2/139
chicago: Sobral, D., A. M. Swinbank, J. P. Stott, Jorryt J Matthee, R. G. Bower,
Ian Smail, P. Best, J. E. Geach, and R. M. Sharples. “The Dynamics of Z=0.8 H-Alpha-Selected
Star-Forming Galaxies from KMOS/CF-HiZELS.” The Astrophysical Journal.
IOP Publishing, 2013. https://doi.org/10.1088/0004-637x/779/2/139.
ieee: D. Sobral et al., “The dynamics of z=0.8 H-alpha-selected star-forming
galaxies from KMOS/CF-HiZELS,” The Astrophysical Journal, vol. 779, no.
2. IOP Publishing, 2013.
ista: Sobral D, Swinbank AM, Stott JP, Matthee JJ, Bower RG, Smail I, Best P, Geach
JE, Sharples RM. 2013. The dynamics of z=0.8 H-alpha-selected star-forming galaxies
from KMOS/CF-HiZELS. The Astrophysical Journal. 779(2), 139.
mla: Sobral, D., et al. “The Dynamics of Z=0.8 H-Alpha-Selected Star-Forming Galaxies
from KMOS/CF-HiZELS.” The Astrophysical Journal, vol. 779, no. 2, 139,
IOP Publishing, 2013, doi:10.1088/0004-637x/779/2/139.
short: D. Sobral, A.M. Swinbank, J.P. Stott, J.J. Matthee, R.G. Bower, I. Smail,
P. Best, J.E. Geach, R.M. Sharples, The Astrophysical Journal 779 (2013).
date_created: 2022-07-07T09:14:48Z
date_published: 2013-12-03T00:00:00Z
date_updated: 2022-08-18T10:43:07Z
day: '03'
doi: 10.1088/0004-637x/779/2/139
extern: '1'
external_id:
arxiv:
- '1310.3822'
intvolume: ' 779'
issue: '2'
keyword:
- Space and Planetary Science
- Astronomy and Astrophysics
- 'galaxies: evolution – galaxies'
- high-redshift – galaxies
- starburst
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1310.3822
month: '12'
oa: 1
oa_version: Preprint
publication: The Astrophysical Journal
publication_identifier:
eissn:
- 1538-4357
issn:
- 0004-637X
publication_status: published
publisher: IOP Publishing
quality_controlled: '1'
scopus_import: '1'
status: public
title: The dynamics of z=0.8 H-alpha-selected star-forming galaxies from KMOS/CF-HiZELS
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 779
year: '2013'
...
---
_id: '116'
abstract:
- lang: eng
text: 'We describe a model experiment for dynamic jamming: a two-dimensional collection
of initially unjammed disks that are forced into the jammed state by uniaxial
compression via a rake. This leads to a stable densification front that travels
ahead of the rake, leaving regions behind it jammed. Using disk conservation in
conjunction with an upper limit to the packing fraction at jamming onset, we predict
the front speed as a function of packing fraction and rake speed. However, we
find that the jamming front has a finite width, a feature that cannot be explained
by disk conservation alone. This width appears to diverge on approach to jamming,
which suggests that it may be related to growing lengthscales encountered in other
jamming studies.'
acknowledgement: This work was supported by the National Science Foundation (NSF)
through its Materials Research Science and Engineering program (DMR-0820054). SRW
was supported by the U.S. Department of Energy, Office of Basic Energy Sciences,
Division of Materials Sciences and Engineering under Award DE-FG02-03ER46088. LKR
acknowledges support through the NSF Research Experience for Undergraduates program.
article_number: '44001'
author:
- first_name: Scott R
full_name: Waitukaitis, Scott R
id: 3A1FFC16-F248-11E8-B48F-1D18A9856A87
last_name: Waitukaitis
orcid: 0000-0002-2299-3176
- first_name: Leah
full_name: Roth, Leah
last_name: Roth
- first_name: Vincenzo
full_name: Vitelli, Vincenzo
last_name: Vitelli
- first_name: Heinrich
full_name: Jaeger, Heinrich
last_name: Jaeger
citation:
ama: Waitukaitis SR, Roth L, Vitelli V, Jaeger H. Dynamic jamming fronts. EPL.
2013;102(4). doi:10.1209/0295-5075/102/44001
apa: Waitukaitis, S. R., Roth, L., Vitelli, V., & Jaeger, H. (2013). Dynamic
jamming fronts. EPL. Elsevier. https://doi.org/10.1209/0295-5075/102/44001
chicago: Waitukaitis, Scott R, Leah Roth, Vincenzo Vitelli, and Heinrich Jaeger.
“Dynamic Jamming Fronts.” EPL. Elsevier, 2013. https://doi.org/10.1209/0295-5075/102/44001.
ieee: S. R. Waitukaitis, L. Roth, V. Vitelli, and H. Jaeger, “Dynamic jamming fronts,”
EPL, vol. 102, no. 4. Elsevier, 2013.
ista: Waitukaitis SR, Roth L, Vitelli V, Jaeger H. 2013. Dynamic jamming fronts.
EPL. 102(4), 44001.
mla: Waitukaitis, Scott R., et al. “Dynamic Jamming Fronts.” EPL, vol. 102,
no. 4, 44001, Elsevier, 2013, doi:10.1209/0295-5075/102/44001.
short: S.R. Waitukaitis, L. Roth, V. Vitelli, H. Jaeger, EPL 102 (2013).
date_created: 2018-12-11T11:44:43Z
date_published: 2013-05-24T00:00:00Z
date_updated: 2021-01-12T06:48:44Z
day: '24'
doi: 10.1209/0295-5075/102/44001
extern: '1'
intvolume: ' 102'
issue: '4'
language:
- iso: eng
month: '05'
oa_version: None
publication: EPL
publication_status: published
publisher: Elsevier
publist_id: '7938'
quality_controlled: '1'
status: public
title: Dynamic jamming fronts
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 102
year: '2013'
...
---
_id: '11671'
abstract:
- lang: eng
text: "Given only the URL of a Web page, can we identify its language? In this article
we examine this question. URL-based language classification is useful when the
content of the Web page is not available or downloading the content is a waste
of bandwidth and time.\r\nWe built URL-based language classifiers for English,
German, French, Spanish, and Italian by applying a variety of algorithms and features.
As algorithms we used machine learning algorithms which are widely applied for
text classification and state-of-art algorithms for language identification of
text. As features we used words, various sized n-grams, and custom-made features
(our novel feature set). We compared our approaches with two baseline methods,
namely classification by country code top-level domains and classification by
IP addresses of the hosting Web servers.\r\n\r\nWe trained and tested our classifiers
in a 10-fold cross-validation setup on a dataset obtained from the Open Directory
Project and from querying a commercial search engine. We obtained the lowest F1-measure
for English (94) and the highest F1-measure for German (98) with the best performing
classifiers.\r\n\r\nWe also evaluated the performance of our methods: (i) on a
set of Web pages written in Adobe Flash and (ii) as part of a language-focused
crawler. In the first case, the content of the Web page is hard to extract and
in the second page downloading pages of the “wrong” language constitutes a waste
of bandwidth. In both settings the best classifiers have a high accuracy with
an F1-measure between 95 (for English) and 98 (for Italian) for the Adobe Flash
pages and a precision between 90 (for Italian) and 97 (for French) for the language-focused
crawler."
article_number: '3'
article_processing_charge: No
article_type: original
author:
- first_name: Eda
full_name: Baykan, Eda
last_name: Baykan
- first_name: Ingmar
full_name: Weber, Ingmar
last_name: Weber
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: Baykan E, Weber I, Henzinger M. A comprehensive study of techniques for URL-based
web page language classification. ACM Transactions on the Web. 2013;7(1).
doi:10.1145/2435215.2435218
apa: Baykan, E., Weber, I., & Henzinger, M. (2013). A comprehensive study of
techniques for URL-based web page language classification. ACM Transactions
on the Web. Association for Computing Machinery. https://doi.org/10.1145/2435215.2435218
chicago: Baykan, Eda, Ingmar Weber, and Monika Henzinger. “A Comprehensive Study
of Techniques for URL-Based Web Page Language Classification.” ACM Transactions
on the Web. Association for Computing Machinery, 2013. https://doi.org/10.1145/2435215.2435218.
ieee: E. Baykan, I. Weber, and M. Henzinger, “A comprehensive study of techniques
for URL-based web page language classification,” ACM Transactions on the Web,
vol. 7, no. 1. Association for Computing Machinery, 2013.
ista: Baykan E, Weber I, Henzinger M. 2013. A comprehensive study of techniques
for URL-based web page language classification. ACM Transactions on the Web. 7(1),
3.
mla: Baykan, Eda, et al. “A Comprehensive Study of Techniques for URL-Based Web
Page Language Classification.” ACM Transactions on the Web, vol. 7, no.
1, 3, Association for Computing Machinery, 2013, doi:10.1145/2435215.2435218.
short: E. Baykan, I. Weber, M. Henzinger, ACM Transactions on the Web 7 (2013).
date_created: 2022-07-27T12:50:18Z
date_published: 2013-03-01T00:00:00Z
date_updated: 2024-11-06T12:07:18Z
day: '01'
doi: 10.1145/2435215.2435218
extern: '1'
intvolume: ' 7'
issue: '1'
keyword:
- Computer Networks and Communications
language:
- iso: eng
month: '03'
oa_version: None
publication: ACM Transactions on the Web
publication_identifier:
eissn:
- 1559-114X
issn:
- 1559-1131
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: A comprehensive study of techniques for URL-based web page language classification
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7
year: '2013'
...
---
_id: '117'
abstract:
- lang: eng
text: The packing arrangement of individual particles inside a granular material
and the resulting response to applied stresses depend critically on particle-particle
interactions. One aspect that recently received attention are nanoscale surface
features of particles, which play an important role in determining the strength
of cohesive van der Waals and capillary interactions and also affect tribo-charging
of grains. We describe experiments on freely falling granular streams that can
detect the contributions from all three of these forces. We show that it is possible
to measure the charge of individual grains and build up distributions that are
detailed enough to provide stringent tests of tribo-charging models currently
available. A second aspect concerns particle shape. In this case steric interactions
become important and new types of aggregate behavior can be expected when non-convex
particle shapes are considered that can interlock or entangle. However, a general
connection between the mechanical response of a granular material and the constituents\'
shape remains unknown. This has made it infeasible to tackle the "inverse
packing problem", namely to start from a given, desired behavior for the
aggregate as a whole and then find the particle shape the produces it. We discuss
a new approach, using concepts rooted in artificial evolution that provides a
way to solve this inverse problem. This approach facilitates exploring the role
of arbitrary particle geometry in jammed systems and invites the discovery and
design of granular matter with optimized properties.
acknowledgement: This work was supported by the NSF MRSEC program under DMR-0820054.
Additional support came from the US Army Research Office through W911NF-12-1-0182.
author:
- first_name: Heinrich
full_name: Jaeger, Heinrich
last_name: Jaeger
- first_name: Marc
full_name: Miskin, Marc
last_name: Miskin
- first_name: Scott R
full_name: Waitukaitis, Scott R
id: 3A1FFC16-F248-11E8-B48F-1D18A9856A87
last_name: Waitukaitis
orcid: 0000-0002-2299-3176
citation:
ama: 'Jaeger H, Miskin M, Waitukaitis SR. From nanoscale cohesion to macroscale
entanglement: opportunities for designing granular aggregate behaviour by tailoring
grain shape and interactions. In: AIP Conference Proceedings. Vol 1542.
AIP; 2013:3-6. doi:10.1063/1.4811858'
apa: 'Jaeger, H., Miskin, M., & Waitukaitis, S. R. (2013). From nanoscale cohesion
to macroscale entanglement: opportunities for designing granular aggregate behaviour
by tailoring grain shape and interactions. In AIP Conference Proceedings
(Vol. 1542, pp. 3–6). Sydney, Australia: AIP. https://doi.org/10.1063/1.4811858'
chicago: 'Jaeger, Heinrich, Marc Miskin, and Scott R Waitukaitis. “From Nanoscale
Cohesion to Macroscale Entanglement: Opportunities for Designing Granular Aggregate
Behaviour by Tailoring Grain Shape and Interactions.” In AIP Conference Proceedings,
1542:3–6. AIP, 2013. https://doi.org/10.1063/1.4811858.'
ieee: 'H. Jaeger, M. Miskin, and S. R. Waitukaitis, “From nanoscale cohesion to
macroscale entanglement: opportunities for designing granular aggregate behaviour
by tailoring grain shape and interactions,” in AIP Conference Proceedings,
Sydney, Australia, 2013, vol. 1542, pp. 3–6.'
ista: 'Jaeger H, Miskin M, Waitukaitis SR. 2013. From nanoscale cohesion to macroscale
entanglement: opportunities for designing granular aggregate behaviour by tailoring
grain shape and interactions. AIP Conference Proceedings. Powders and Grains
vol. 1542, 3–6.'
mla: 'Jaeger, Heinrich, et al. “From Nanoscale Cohesion to Macroscale Entanglement:
Opportunities for Designing Granular Aggregate Behaviour by Tailoring Grain Shape
and Interactions.” AIP Conference Proceedings, vol. 1542, AIP, 2013, pp.
3–6, doi:10.1063/1.4811858.'
short: H. Jaeger, M. Miskin, S.R. Waitukaitis, in:, AIP Conference Proceedings,
AIP, 2013, pp. 3–6.
conference:
end_date: 2013-07-12
location: Sydney, Australia
name: Powders and Grains
start_date: 2013-07-08
date_created: 2018-12-11T11:44:43Z
date_published: 2013-06-01T00:00:00Z
date_updated: 2021-01-12T06:48:49Z
day: '01'
doi: 10.1063/1.4811858
extern: '1'
intvolume: ' 1542'
language:
- iso: eng
month: '06'
oa_version: None
page: 3 - 6
publication: ' AIP Conference Proceedings'
publication_status: published
publisher: AIP
publist_id: '7937'
quality_controlled: '1'
status: public
title: 'From nanoscale cohesion to macroscale entanglement: opportunities for designing
granular aggregate behaviour by tailoring grain shape and interactions'
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 1542
year: '2013'
...
---
_id: '11758'
article_processing_charge: No
article_type: letter_note
author:
- first_name: Luca
full_name: Aceto, Luca
last_name: Aceto
- 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: Jiří
full_name: Sgall, Jiří
last_name: Sgall
citation:
ama: Aceto L, Henzinger M, Sgall J. 38th International Colloquium on Automata, Languages
and Programming. Information and Computation. 2013;222(1):1. doi:10.1016/j.ic.2012.11.002
apa: Aceto, L., Henzinger, M., & Sgall, J. (2013). 38th International Colloquium
on Automata, Languages and Programming. Information and Computation. Elsevier.
https://doi.org/10.1016/j.ic.2012.11.002
chicago: Aceto, Luca, Monika Henzinger, and Jiří Sgall. “38th International Colloquium
on Automata, Languages and Programming.” Information and Computation. Elsevier,
2013. https://doi.org/10.1016/j.ic.2012.11.002.
ieee: L. Aceto, M. Henzinger, and J. Sgall, “38th International Colloquium on Automata,
Languages and Programming,” Information and Computation, vol. 222, no.
1. Elsevier, p. 1, 2013.
ista: Aceto L, Henzinger M, Sgall J. 2013. 38th International Colloquium on Automata,
Languages and Programming. Information and Computation. 222(1), 1.
mla: Aceto, Luca, et al. “38th International Colloquium on Automata, Languages and
Programming.” Information and Computation, vol. 222, no. 1, Elsevier, 2013,
p. 1, doi:10.1016/j.ic.2012.11.002.
short: L. Aceto, M. Henzinger, J. Sgall, Information and Computation 222 (2013)
1.
date_created: 2022-08-08T11:25:34Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2024-11-06T12:01:32Z
day: '01'
doi: 10.1016/j.ic.2012.11.002
extern: '1'
intvolume: ' 222'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: '1'
publication: Information and Computation
publication_identifier:
issn:
- 0890-5401
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: 38th International Colloquium on Automata, Languages and Programming
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 222
year: '2013'
...
---
_id: '11759'
abstract:
- lang: eng
text: Matching markets play a prominent role in economic theory. A prime example
of such a market is the sponsored search market. Here, as in other markets of
that kind, market equilibria correspond to feasible, envy free, and bidder optimal
outcomes. For settings without budgets such an outcome always exists and can be
computed in polynomial-time by the so-called Hungarian Method. Moreover, every
mechanism that computes such an outcome is incentive compatible. We show that
the Hungarian Method can be modified so that it finds a feasible, envy free, and
bidder optimal outcome for settings with budgets. We also show that in settings
with budgets no mechanism that computes such an outcome can be incentive compatible
for all inputs. For inputs in general position, however, the presented mechanism—as
any other mechanism that computes such an outcome for settings with budgets—is
incentive compatible.
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: Ingmar
full_name: Weber, Ingmar
last_name: Weber
citation:
ama: Dütting P, Henzinger M, Weber I. Sponsored search, market equilibria, and the
Hungarian Method. Information Processing Letters. 2013;113(3):67-73. doi:10.1016/j.ipl.2012.11.006
apa: Dütting, P., Henzinger, M., & Weber, I. (2013). Sponsored search, market
equilibria, and the Hungarian Method. Information Processing Letters. Elsevier.
https://doi.org/10.1016/j.ipl.2012.11.006
chicago: Dütting, Paul, Monika Henzinger, and Ingmar Weber. “Sponsored Search, Market
Equilibria, and the Hungarian Method.” Information Processing Letters.
Elsevier, 2013. https://doi.org/10.1016/j.ipl.2012.11.006.
ieee: P. Dütting, M. Henzinger, and I. Weber, “Sponsored search, market equilibria,
and the Hungarian Method,” Information Processing Letters, vol. 113, no.
3. Elsevier, pp. 67–73, 2013.
ista: Dütting P, Henzinger M, Weber I. 2013. Sponsored search, market equilibria,
and the Hungarian Method. Information Processing Letters. 113(3), 67–73.
mla: Dütting, Paul, et al. “Sponsored Search, Market Equilibria, and the Hungarian
Method.” Information Processing Letters, vol. 113, no. 3, Elsevier, 2013,
pp. 67–73, doi:10.1016/j.ipl.2012.11.006.
short: P. Dütting, M. Henzinger, I. Weber, Information Processing Letters 113 (2013)
67–73.
date_created: 2022-08-08T11:29:08Z
date_published: 2013-02-15T00:00:00Z
date_updated: 2024-11-06T12:09:36Z
day: '15'
doi: 10.1016/j.ipl.2012.11.006
extern: '1'
external_id:
arxiv:
- '0912.1934'
intvolume: ' 113'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/0912.1934
month: '02'
oa: 1
oa_version: Preprint
page: 67-73
publication: Information Processing Letters
publication_identifier:
issn:
- 0020-0190
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Sponsored search, market equilibria, and the Hungarian Method
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 113
year: '2013'
...
---
_id: '11791'
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 VCG 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 the welfare
loss increases in expressiveness. All our bounds apply to equilibrium concepts
that can be computed in polynomial time as well as to learning outcomes.
alternative_title:
- LNCS
article_processing_charge: No
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. In: 9th International Conference on Web and Internet
Economics. Vol 8289. Springer Nature; 2013:146–159. doi:10.1007/978-3-642-45046-4_13'
apa: 'Dütting, P., Henzinger, M., & Starnberger, M. (2013). Valuation compressions
in VCG-based combinatorial auctions. In 9th International Conference on Web
and Internet Economics (Vol. 8289, pp. 146–159). Cambridge, MA, USA: Springer
Nature. https://doi.org/10.1007/978-3-642-45046-4_13'
chicago: Dütting, Paul, Monika Henzinger, and Martin Starnberger. “Valuation Compressions
in VCG-Based Combinatorial Auctions.” In 9th International Conference on Web
and Internet Economics, 8289:146–159. Springer Nature, 2013. https://doi.org/10.1007/978-3-642-45046-4_13.
ieee: P. Dütting, M. Henzinger, and M. Starnberger, “Valuation compressions in VCG-based
combinatorial auctions,” in 9th International Conference on Web and Internet
Economics, Cambridge, MA, USA, 2013, vol. 8289, pp. 146–159.
ista: 'Dütting P, Henzinger M, Starnberger M. 2013. Valuation compressions in VCG-based
combinatorial auctions. 9th International Conference on Web and Internet Economics.
WINE: International Conference on Web and Internet Economics, LNCS, vol. 8289,
146–159.'
mla: Dütting, Paul, et al. “Valuation Compressions in VCG-Based Combinatorial Auctions.”
9th International Conference on Web and Internet Economics, vol. 8289,
Springer Nature, 2013, pp. 146–159, doi:10.1007/978-3-642-45046-4_13.
short: P. Dütting, M. Henzinger, M. Starnberger, in:, 9th International Conference
on Web and Internet Economics, Springer Nature, 2013, pp. 146–159.
conference:
end_date: 2013-12-14
location: Cambridge, MA, USA
name: 'WINE: International Conference on Web and Internet Economics'
start_date: 2013-12-01
date_created: 2022-08-11T11:05:14Z
date_published: 2013-12-01T00:00:00Z
date_updated: 2024-11-06T12:12:00Z
day: '01'
doi: 10.1007/978-3-642-45046-4_13
extern: '1'
external_id:
arxiv:
- '1310.3153'
intvolume: ' 8289'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1310.3153
month: '12'
oa: 1
oa_version: Preprint
page: 146–159
publication: 9th International Conference on Web and Internet Economics
publication_identifier:
isbn:
- '9783642450457'
issn:
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Valuation compressions in VCG-based combinatorial auctions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8289
year: '2013'
...
---
_id: '11792'
abstract:
- lang: eng
text: "We study the problem of maximizing a monotone submodular function with viability
constraints. This problem originates from computational biology, where we are
given a phylogenetic tree over a set of species and a directed graph, the so-called
food web, encoding viability constraints between these species. These food webs
usually have constant depth. The goal is to select a subset of k species that
satisfies the viability constraints and has maximal phylogenetic diversity. As
this problem is known to be NP-hard, we investigate approximation algorithm. We
present the first constant factor approximation algorithm if the depth is constant.
Its approximation ratio is (1−1\U0001D452√). This algorithm not only applies to
phylogenetic trees with viability constraints but for arbitrary monotone submodular
set functions with viability constraints. Second, we show that there is no (1 − 1/e + ε)-approximation
algorithm for our problem setting (even for additive functions) and that there
is no approximation algorithm for a slight extension of this setting."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Wolfgang
full_name: Dvořák, Wolfgang
last_name: Dvořák
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: David P.
full_name: Williamson, David P.
last_name: Williamson
citation:
ama: 'Dvořák W, Henzinger M, Williamson DP. Maximizing a submodular function with
viability constraints. In: 21st Annual European Symposium on Algorithms.
Vol 8125. Springer Nature; 2013:409-420. doi:10.1007/978-3-642-40450-4_35'
apa: 'Dvořák, W., Henzinger, M., & Williamson, D. P. (2013). Maximizing a submodular
function with viability constraints. In 21st Annual European Symposium on Algorithms
(Vol. 8125, pp. 409–420). Sophia Antipolis, France: Springer Nature. https://doi.org/10.1007/978-3-642-40450-4_35'
chicago: Dvořák, Wolfgang, Monika Henzinger, and David P. Williamson. “Maximizing
a Submodular Function with Viability Constraints.” In 21st Annual European
Symposium on Algorithms, 8125:409–20. Springer Nature, 2013. https://doi.org/10.1007/978-3-642-40450-4_35.
ieee: W. Dvořák, M. Henzinger, and D. P. Williamson, “Maximizing a submodular function
with viability constraints,” in 21st Annual European Symposium on Algorithms,
Sophia Antipolis, France, 2013, vol. 8125, pp. 409–420.
ista: 'Dvořák W, Henzinger M, Williamson DP. 2013. Maximizing a submodular function
with viability constraints. 21st Annual European Symposium on Algorithms. ESA:
European Symposium on Algorithms, LNCS, vol. 8125, 409–420.'
mla: Dvořák, Wolfgang, et al. “Maximizing a Submodular Function with Viability Constraints.”
21st Annual European Symposium on Algorithms, vol. 8125, Springer Nature,
2013, pp. 409–20, doi:10.1007/978-3-642-40450-4_35.
short: W. Dvořák, M. Henzinger, D.P. Williamson, in:, 21st Annual European Symposium
on Algorithms, Springer Nature, 2013, pp. 409–420.
conference:
end_date: 2013-09-04
location: Sophia Antipolis, France
name: 'ESA: European Symposium on Algorithms'
start_date: 2013-09-02
date_created: 2022-08-11T11:18:19Z
date_published: 2013-09-01T00:00:00Z
date_updated: 2024-11-06T12:12:13Z
day: '01'
doi: 10.1007/978-3-642-40450-4_35
extern: '1'
external_id:
arxiv:
- '1611.05753'
intvolume: ' 8125'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1611.05753
month: '09'
oa: 1
oa_version: Preprint
page: 409 - 420
publication: 21st Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783642404498'
issn:
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '11792'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Maximizing a submodular function with viability constraints
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8125
year: '2013'
...
---
_id: '11793'
abstract:
- lang: eng
text: "We study the problem of maintaining a breadth-first spanning tree (BFS tree)
in partially dynamic distributed networks modeling a sequence of either failures
or additions of communication links (but not both). We show (1 + ε)-approximation
algorithms whose amortized time (over some number of link changes) is sublinear
in D, the maximum diameter of the network. This breaks the Θ(D) time bound of
recomputing “from scratch”.\r\n\r\nOur technique also leads to a (1 + ε)-approximate
incremental algorithm for single-source shortest paths (SSSP) in the sequential
(usual RAM) model. Prior to our work, the state of the art was the classic exact
algorithm of [9] that is optimal under some assumptions [27]. Our result is the
first to show that, in the incremental setting, this bound can be beaten in certain
cases if a small approximation is allowed."
alternative_title:
- LNCS
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: 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. Sublinear-time maintenance of breadth-first
spanning tree in partially dynamic networks. In: 40th International Colloquium
on Automata, Languages, and Programming. Vol 7966. Springer Nature; 2013:607–619.
doi:10.1007/978-3-642-39212-2_53'
apa: 'Henzinger, M., Krinninger, S., & Nanongkai, D. (2013). Sublinear-time
maintenance of breadth-first spanning tree in partially dynamic networks. In 40th
International Colloquium on Automata, Languages, and Programming (Vol. 7966,
pp. 607–619). Riga, Latvia: Springer Nature. https://doi.org/10.1007/978-3-642-39212-2_53'
chicago: Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time
Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks.” In
40th International Colloquium on Automata, Languages, and Programming,
7966:607–619. Springer Nature, 2013. https://doi.org/10.1007/978-3-642-39212-2_53.
ieee: M. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time maintenance
of breadth-first spanning tree in partially dynamic networks,” in 40th International
Colloquium on Automata, Languages, and Programming, Riga, Latvia, 2013, vol.
7966, pp. 607–619.
ista: 'Henzinger M, Krinninger S, Nanongkai D. 2013. Sublinear-time maintenance
of breadth-first spanning tree in partially dynamic networks. 40th International
Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium
on Automata, Languages, and Programming, LNCS, vol. 7966, 607–619.'
mla: Henzinger, Monika, et al. “Sublinear-Time Maintenance of Breadth-First Spanning
Tree in Partially Dynamic Networks.” 40th International Colloquium on Automata,
Languages, and Programming, vol. 7966, Springer Nature, 2013, pp. 607–619,
doi:10.1007/978-3-642-39212-2_53.
short: M. Henzinger, S. Krinninger, D. Nanongkai, in:, 40th International Colloquium
on Automata, Languages, and Programming, Springer Nature, 2013, pp. 607–619.
conference:
end_date: 2013-07-12
location: Riga, Latvia
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2013-07-08
date_created: 2022-08-11T11:25:13Z
date_published: 2013-07-01T00:00:00Z
date_updated: 2024-11-06T12:12:27Z
day: '01'
doi: 10.1007/978-3-642-39212-2_53
extern: '1'
external_id:
arxiv:
- '1512.08147'
intvolume: ' 7966'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1512.08147
month: '07'
oa: 1
oa_version: Preprint
page: 607–619
publication: 40th International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783642392115'
issn:
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '11793'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Sublinear-time maintenance of breadth-first spanning tree in partially dynamic
networks
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7966
year: '2013'
...
---
_id: '11856'
abstract:
- lang: eng
text: 'We study dynamic (1 + ϵ)-approximation algorithms for the all-pairs shortest
paths problem in unweighted undirected n-node m-edge graphs under edge deletions.
The fastest algorithm for this problem is a randomized algorithm with a total
update time of Ȏ(mn) and constant query time by Roditty and Zwick (FOCS 2004).
The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach
(JACM 1981); it has a total update time of O(mn 2 ) and constant query time. We
improve these results as follows: (1) We present an algorithm with a total update
time of Ȏ(n 5/2 ) and constant query time that has an additive error of two in
addition to the 1 + ϵ multiplicative error. This beats the previous Ȏ(mn) time
when m = Ω(n 3/2 ). Note that the additive error is unavoidable since, even in
the static case, an O(n 3-δ )-time (a so-called truly sub cubic) combinatorial
algorithm with 1 + ϵ multiplicative error cannot have an additive error less than
2 - ϵ, unless we make a major breakthrough for Boolean matrix multiplication (Dor,
Halperin and Zwick FOCS 1996) and many other long-standing problems (Vassilevska
Williams and Williams FOCS 2010). The algorithm can also be turned into a (2 +
ϵ)-approximation algorithm (without an additive error) with the same time guarantees,
improving the recent (3 + ϵ)-approximation algorithm with Ȏ(n 5/2+O(1√(log n))
) running time of Bernstein and Roditty (SODA 2011) in terms of both approximation
and time guarantees. (2) We present a deterministic algorithm with a total update
time of Ȏ(mn) and a query time of O(log log n). The algorithm has a multiplicative
error of 1 + ϵ and gives the first improved deterministic algorithm since 1981.
It also answers an open question raised by Bernstein in his STOC 2013 paper. In
order to achieve our results, we introduce two new techniques: (1) A lazy Even-Shiloach
tree algorithm which maintains a bounded-distance shortest-paths tree on a certain
type of emulator called locally persevering emulator. (2) A derandomization technique
based on moving Even-Shiloach trees as a way to derandomize the standard random
set argument. These techniques might be of independent interest.'
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: 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. Dynamic approximate all-pairs shortest
paths: Breaking the O(mn) barrier and derandomization. In: 54th Annual Symposium
on Foundations of Computer Science. Institute of Electrical and Electronics
Engineers; 2013:538-547. doi:10.1109/focs.2013.64'
apa: 'Henzinger, M., Krinninger, S., & Nanongkai, D. (2013). Dynamic approximate
all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. In 54th
Annual Symposium on Foundations of Computer Science (pp. 538–547). Berkeley,
CA, United States: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/focs.2013.64'
chicago: 'Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Dynamic
Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.”
In 54th Annual Symposium on Foundations of Computer Science, 538–47. Institute
of Electrical and Electronics Engineers, 2013. https://doi.org/10.1109/focs.2013.64.'
ieee: 'M. Henzinger, S. Krinninger, and D. Nanongkai, “Dynamic approximate all-pairs
shortest paths: Breaking the O(mn) barrier and derandomization,” in 54th Annual
Symposium on Foundations of Computer Science, Berkeley, CA, United States,
2013, pp. 538–547.'
ista: 'Henzinger M, Krinninger S, Nanongkai D. 2013. Dynamic approximate all-pairs
shortest paths: Breaking the O(mn) barrier and derandomization. 54th Annual Symposium
on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer
Science, 538–547.'
mla: 'Henzinger, Monika, et al. “Dynamic Approximate All-Pairs Shortest Paths: Breaking
the O(Mn) Barrier and Derandomization.” 54th Annual Symposium on Foundations
of Computer Science, Institute of Electrical and Electronics Engineers, 2013,
pp. 538–47, doi:10.1109/focs.2013.64.'
short: M. Henzinger, S. Krinninger, D. Nanongkai, in:, 54th Annual Symposium on
Foundations of Computer Science, Institute of Electrical and Electronics Engineers,
2013, pp. 538–547.
conference:
end_date: 2013-10-29
location: Berkeley, CA, United States
name: 'FOCS: Symposium on Foundations of Computer Science'
start_date: 2013-10-26
date_created: 2022-08-16T08:22:37Z
date_published: 2013-10-01T00:00:00Z
date_updated: 2024-11-06T12:18:28Z
day: '01'
doi: 10.1109/focs.2013.64
extern: '1'
external_id:
arxiv:
- '1308.0776'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1308.0776
month: '10'
oa: 1
oa_version: Preprint
page: 538-547
publication: 54th Annual Symposium on Foundations of Computer Science
publication_identifier:
eisbn:
- 978-0-7695-5135-7
issn:
- 0272-5428
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and
derandomization'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...