---
_id: '3330'
abstract:
- lang: eng
text: We consider the problem of approximating all real roots of a square-free polynomial
f. Given isolating intervals, our algorithm refines each of them to a width at
most 2-L, that is, each of the roots is approximated to L bits after the binary
point. Our method provides a certified answer for arbitrary real polynomials,
only requiring finite approximations of the polynomial coefficient and choosing
a suitable working precision adaptively. In this way, we get a correct algorithm
that is simple to implement and practically efficient. Our algorithm uses the
quadratic interval refinement method; we adapt that method to be able to cope
with inaccuracies when evaluating f, without sacrificing its quadratic convergence
behavior. We prove a bound on the bit complexity of our algorithm in terms of
degree, coefficient size and discriminant. Our bound improves previous work on
integer polynomials by a factor of deg f and essentially matches best known theoretical
bounds on root approximation which are obtained by very sophisticated algorithms.
article_processing_charge: No
arxiv: 1
author:
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Michael
full_name: Sagraloff, Michael
last_name: Sagraloff
citation:
ama: 'Kerber M, Sagraloff M. Root refinement for real polynomials. In: Springer;
2011:209-216. doi:10.1145/1993886.1993920'
apa: 'Kerber, M., & Sagraloff, M. (2011). Root refinement for real polynomials
(pp. 209–216). Presented at the ISSAC: International Symposium on Symbolic and
Algebraic Computation, California, USA: Springer. https://doi.org/10.1145/1993886.1993920'
chicago: Kerber, Michael, and Michael Sagraloff. “Root Refinement for Real Polynomials,”
209–16. Springer, 2011. https://doi.org/10.1145/1993886.1993920.
ieee: 'M. Kerber and M. Sagraloff, “Root refinement for real polynomials,” presented
at the ISSAC: International Symposium on Symbolic and Algebraic Computation, California,
USA, 2011, pp. 209–216.'
ista: 'Kerber M, Sagraloff M. 2011. Root refinement for real polynomials. ISSAC:
International Symposium on Symbolic and Algebraic Computation, 209–216.'
mla: Kerber, Michael, and Michael Sagraloff. Root Refinement for Real Polynomials.
Springer, 2011, pp. 209–16, doi:10.1145/1993886.1993920.
short: M. Kerber, M. Sagraloff, in:, Springer, 2011, pp. 209–216.
conference:
end_date: 2011-06-11
location: California, USA
name: 'ISSAC: International Symposium on Symbolic and Algebraic Computation'
start_date: 2011-06-08
date_created: 2018-12-11T12:02:43Z
date_published: 2011-06-08T00:00:00Z
date_updated: 2021-01-12T07:42:42Z
day: '08'
department:
- _id: HeEd
doi: 10.1145/1993886.1993920
external_id:
arxiv:
- '1104.1362'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1104.1362
month: '06'
oa: 1
oa_version: Preprint
page: 209 - 216
publication_status: published
publisher: Springer
publist_id: '3304'
quality_controlled: '1'
scopus_import: 1
status: public
title: Root refinement for real polynomials
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3332'
abstract:
- lang: eng
text: Given an algebraic hypersurface O in ℝd, how many simplices are necessary
for a simplicial complex isotopic to O? We address this problem and the variant
where all vertices of the complex must lie on O. We give asymptotically tight
worst-case bounds for algebraic plane curves. Our results gradually improve known
bounds in higher dimensions; however, the question for tight bounds remains unsolved
for d ≥ 3.
article_processing_charge: No
article_type: original
author:
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Michael
full_name: Sagraloff, Michael
last_name: Sagraloff
citation:
ama: Kerber M, Sagraloff M. A note on the complexity of real algebraic hypersurfaces.
Graphs and Combinatorics. 2011;27(3):419-430. doi:10.1007/s00373-011-1020-7
apa: Kerber, M., & Sagraloff, M. (2011). A note on the complexity of real algebraic
hypersurfaces. Graphs and Combinatorics. Springer. https://doi.org/10.1007/s00373-011-1020-7
chicago: Kerber, Michael, and Michael Sagraloff. “A Note on the Complexity of Real
Algebraic Hypersurfaces.” Graphs and Combinatorics. Springer, 2011. https://doi.org/10.1007/s00373-011-1020-7.
ieee: M. Kerber and M. Sagraloff, “A note on the complexity of real algebraic hypersurfaces,”
Graphs and Combinatorics, vol. 27, no. 3. Springer, pp. 419–430, 2011.
ista: Kerber M, Sagraloff M. 2011. A note on the complexity of real algebraic hypersurfaces.
Graphs and Combinatorics. 27(3), 419–430.
mla: Kerber, Michael, and Michael Sagraloff. “A Note on the Complexity of Real Algebraic
Hypersurfaces.” Graphs and Combinatorics, vol. 27, no. 3, Springer, 2011,
pp. 419–30, doi:10.1007/s00373-011-1020-7.
short: M. Kerber, M. Sagraloff, Graphs and Combinatorics 27 (2011) 419–430.
date_created: 2018-12-11T12:02:43Z
date_published: 2011-03-17T00:00:00Z
date_updated: 2021-01-12T07:42:43Z
day: '17'
ddc:
- '500'
department:
- _id: HeEd
doi: 10.1007/s00373-011-1020-7
file:
- access_level: open_access
checksum: a63a1e3e885dcc68f1e3dea68dfbe213
content_type: application/pdf
creator: dernst
date_created: 2020-05-19T16:11:36Z
date_updated: 2020-07-14T12:46:08Z
file_id: '7869'
file_name: 2011_GraphsCombi_Kerber.pdf
file_size: 143976
relation: main_file
file_date_updated: 2020-07-14T12:46:08Z
has_accepted_license: '1'
intvolume: ' 27'
issue: '3'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Submitted Version
page: 419 - 430
publication: Graphs and Combinatorics
publication_status: published
publisher: Springer
publist_id: '3301'
quality_controlled: '1'
scopus_import: 1
status: public
title: A note on the complexity of real algebraic hypersurfaces
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 27
year: '2011'
...
---
_id: '3334'
article_type: letter_note
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: János
full_name: Pach, János
last_name: Pach
- first_name: Günter
full_name: Ziegler, Günter
last_name: Ziegler
citation:
ama: Edelsbrunner H, Pach J, Ziegler G. Letter from the new editors-in-chief. Discrete
& Computational Geometry. 2011;45(1):1-2. doi:10.1007/s00454-010-9313-9
apa: Edelsbrunner, H., Pach, J., & Ziegler, G. (2011). Letter from the new editors-in-chief.
Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-010-9313-9
chicago: Edelsbrunner, Herbert, János Pach, and Günter Ziegler. “Letter from the
New Editors-in-Chief.” Discrete & Computational Geometry. Springer,
2011. https://doi.org/10.1007/s00454-010-9313-9.
ieee: H. Edelsbrunner, J. Pach, and G. Ziegler, “Letter from the new editors-in-chief,”
Discrete & Computational Geometry, vol. 45, no. 1. Springer, pp. 1–2,
2011.
ista: Edelsbrunner H, Pach J, Ziegler G. 2011. Letter from the new editors-in-chief.
Discrete & Computational Geometry. 45(1), 1–2.
mla: Edelsbrunner, Herbert, et al. “Letter from the New Editors-in-Chief.” Discrete
& Computational Geometry, vol. 45, no. 1, Springer, 2011, pp. 1–2, doi:10.1007/s00454-010-9313-9.
short: H. Edelsbrunner, J. Pach, G. Ziegler, Discrete & Computational Geometry
45 (2011) 1–2.
date_created: 2018-12-11T12:02:44Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:42:44Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/s00454-010-9313-9
intvolume: ' 45'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 1 - 2
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '3297'
quality_controlled: '1'
scopus_import: 1
status: public
title: Letter from the new editors-in-chief
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 45
year: '2011'
...
---
_id: '3335'
abstract:
- lang: eng
text: We study the topology of the Megaparsec Cosmic Web in terms of the scale-dependent
Betti numbers, which formalize the topological information content of the cosmic
mass distribution. While the Betti numbers do not fully quantify topology, they
extend the information beyond conventional cosmological studies of topology in
terms of genus and Euler characteristic. The richer information content of Betti
numbers goes along the availability of fast algorithms to compute them. For continuous
density fields, we determine the scale-dependence of Betti numbers by invoking
the cosmologically familiar filtration of sublevel or superlevel sets defined
by density thresholds. For the discrete galaxy distribution, however, the analysis
is based on the alpha shapes of the particles. These simplicial complexes constitute
an ordered sequence of nested subsets of the Delaunay tessellation, a filtration
defined by the scale parameter, α. As they are homotopy equivalent to the sublevel
sets of the distance field, they are an excellent tool for assessing the topological
structure of a discrete point distribution. In order to develop an intuitive understanding
for the behavior of Betti numbers as a function of α, and their relation to the
morphological patterns in the Cosmic Web, we first study them within the context
of simple heuristic Voronoi clustering models. These can be tuned to consist of
specific morphological elements of the Cosmic Web, i.e. clusters, filaments, or
sheets. To elucidate the relative prominence of the various Betti numbers in different
stages of morphological evolution, we introduce the concept of alpha tracks. Subsequently,
we address the topology of structures emerging in the standard LCDM scenario and
in cosmological scenarios with alternative dark energy content. The evolution
of the Betti numbers is shown to reflect the hierarchical evolution of the Cosmic
Web. We also demonstrate that the scale-dependence of the Betti numbers yields
a promising measure of cosmological parameters, with a potential to help in determining
the nature of dark energy and to probe primordial non-Gaussianities. We also discuss
the expected Betti numbers as a function of the density threshold for superlevel
sets of a Gaussian random field. Finally, we introduce the concept of persistent
homology. It measures scale levels of the mass distribution and allows us to separate
small from large scale features. Within the context of the hierarchical cosmic
structure formation, persistence provides a natural formalism for a multiscale
topology study of the Cosmic Web.
alternative_title:
- LNCS
arxiv: 1
author:
- first_name: Rien
full_name: Van De Weygaert, Rien
last_name: Van De Weygaert
- first_name: Gert
full_name: Vegter, Gert
last_name: Vegter
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Bernard
full_name: Jones, Bernard
last_name: Jones
- first_name: Pratyush
full_name: Pranav, Pratyush
last_name: Pranav
- first_name: Changbom
full_name: Park, Changbom
last_name: Park
- first_name: Wojciech
full_name: Hellwing, Wojciech
last_name: Hellwing
- first_name: Bob
full_name: Eldering, Bob
last_name: Eldering
- first_name: Nico
full_name: Kruithof, Nico
last_name: Kruithof
- first_name: Patrick
full_name: Bos, Patrick
last_name: Bos
- first_name: Johan
full_name: Hidding, Johan
last_name: Hidding
- first_name: Job
full_name: Feldbrugge, Job
last_name: Feldbrugge
- first_name: Eline
full_name: Ten Have, Eline
last_name: Ten Have
- first_name: Matti
full_name: Van Engelen, Matti
last_name: Van Engelen
- first_name: Manuel
full_name: Caroli, Manuel
last_name: Caroli
- first_name: Monique
full_name: Teillaud, Monique
last_name: Teillaud
citation:
ama: 'Van De Weygaert R, Vegter G, Edelsbrunner H, et al. Alpha, Betti and the Megaparsec
Universe: On the topology of the Cosmic Web. In: Gavrilova M, Tan K, Mostafavi
M, eds. Transactions on Computational Science XIV. Vol 6970. Special Issue
on Voronoi Diagrams and Delaunay Triangulation. Springer; 2011:60-101. doi:10.1007/978-3-642-25249-5_3'
apa: 'Van De Weygaert, R., Vegter, G., Edelsbrunner, H., Jones, B., Pranav, P.,
Park, C., … Teillaud, M. (2011). Alpha, Betti and the Megaparsec Universe: On
the topology of the Cosmic Web. In M. Gavrilova, K. Tan, & M. Mostafavi (Eds.),
Transactions on Computational Science XIV (Vol. 6970, pp. 60–101). Springer.
https://doi.org/10.1007/978-3-642-25249-5_3'
chicago: 'Van De Weygaert, Rien, Gert Vegter, Herbert Edelsbrunner, Bernard Jones,
Pratyush Pranav, Changbom Park, Wojciech Hellwing, et al. “Alpha, Betti and the
Megaparsec Universe: On the Topology of the Cosmic Web.” In Transactions on
Computational Science XIV, edited by Marina Gavrilova, Kenneth Tan, and Mir
Mostafavi, 6970:60–101. Special Issue on Voronoi Diagrams and Delaunay Triangulation.
Springer, 2011. https://doi.org/10.1007/978-3-642-25249-5_3.'
ieee: 'R. Van De Weygaert et al., “Alpha, Betti and the Megaparsec Universe:
On the topology of the Cosmic Web,” in Transactions on Computational Science
XIV, vol. 6970, M. Gavrilova, K. Tan, and M. Mostafavi, Eds. Springer, 2011,
pp. 60–101.'
ista: 'Van De Weygaert R, Vegter G, Edelsbrunner H, Jones B, Pranav P, Park C, Hellwing
W, Eldering B, Kruithof N, Bos P, Hidding J, Feldbrugge J, Ten Have E, Van Engelen
M, Caroli M, Teillaud M. 2011.Alpha, Betti and the Megaparsec Universe: On the
topology of the Cosmic Web. In: Transactions on Computational Science XIV. LNCS,
vol. 6970, 60–101.'
mla: 'Van De Weygaert, Rien, et al. “Alpha, Betti and the Megaparsec Universe: On
the Topology of the Cosmic Web.” Transactions on Computational Science XIV,
edited by Marina Gavrilova et al., vol. 6970, Springer, 2011, pp. 60–101, doi:10.1007/978-3-642-25249-5_3.'
short: R. Van De Weygaert, G. Vegter, H. Edelsbrunner, B. Jones, P. Pranav, C. Park,
W. Hellwing, B. Eldering, N. Kruithof, P. Bos, J. Hidding, J. Feldbrugge, E. Ten
Have, M. Van Engelen, M. Caroli, M. Teillaud, in:, M. Gavrilova, K. Tan, M. Mostafavi
(Eds.), Transactions on Computational Science XIV, Springer, 2011, pp. 60–101.
date_created: 2018-12-11T12:02:44Z
date_published: 2011-11-09T00:00:00Z
date_updated: 2021-01-12T07:42:44Z
day: '09'
department:
- _id: HeEd
doi: 10.1007/978-3-642-25249-5_3
editor:
- first_name: Marina
full_name: Gavrilova, Marina
last_name: Gavrilova
- first_name: Kenneth
full_name: Tan, Kenneth
last_name: Tan
- first_name: Mir
full_name: Mostafavi, Mir
last_name: Mostafavi
external_id:
arxiv:
- '1306.3640'
intvolume: ' 6970'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1306.3640
month: '11'
oa: 1
oa_version: Preprint
page: 60 - 101
publication: Transactions on Computational Science XIV
publication_status: published
publisher: Springer
publist_id: '3295'
quality_controlled: '1'
scopus_import: 1
series_title: Special Issue on Voronoi Diagrams and Delaunay Triangulation
status: public
title: 'Alpha, Betti and the Megaparsec Universe: On the topology of the Cosmic Web'
type: book_chapter
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6970
year: '2011'
...
---
_id: '3336'
abstract:
- lang: eng
text: 'We introduce TopoCut: a new way to integrate knowledge about topological
properties (TPs) into random field image segmentation model. Instead of including
TPs as additional constraints during minimization of the energy function, we devise
an efficient algorithm for modifying the unary potentials such that the resulting
segmentation is guaranteed with the desired properties. Our method is more flexible
in the sense that it handles more topology constraints than previous methods,
which were only able to enforce pairwise or global connectivity. In particular,
our method is very fast, making it for the first time possible to enforce global
topological properties in practical image segmentation tasks.'
acknowledgement: The first author is supported by the Austrian Science Fund (FWF)
grant No. P20134-N13. The authors would like to thank Sebastian Nowozin for helpful
discussions.
article_processing_charge: No
author:
- first_name: Chao
full_name: Chen, Chao
id: 3E92416E-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Daniel
full_name: Freedman, Daniel
last_name: Freedman
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: 'Chen C, Freedman D, Lampert C. Enforcing topological constraints in random
field image segmentation. In: CVPR: Computer Vision and Pattern Recognition.
IEEE; 2011:2089-2096. doi:10.1109/CVPR.2011.5995503'
apa: 'Chen, C., Freedman, D., & Lampert, C. (2011). Enforcing topological constraints
in random field image segmentation. In CVPR: Computer Vision and Pattern Recognition
(pp. 2089–2096). Colorado Springs, CO, United States: IEEE. https://doi.org/10.1109/CVPR.2011.5995503'
chicago: 'Chen, Chao, Daniel Freedman, and Christoph Lampert. “Enforcing Topological
Constraints in Random Field Image Segmentation.” In CVPR: Computer Vision and
Pattern Recognition, 2089–96. IEEE, 2011. https://doi.org/10.1109/CVPR.2011.5995503.'
ieee: 'C. Chen, D. Freedman, and C. Lampert, “Enforcing topological constraints
in random field image segmentation,” in CVPR: Computer Vision and Pattern Recognition,
Colorado Springs, CO, United States, 2011, pp. 2089–2096.'
ista: 'Chen C, Freedman D, Lampert C. 2011. Enforcing topological constraints in
random field image segmentation. CVPR: Computer Vision and Pattern Recognition.
CVPR: Conference on Computer Vision and Pattern Recognition, 2089–2096.'
mla: 'Chen, Chao, et al. “Enforcing Topological Constraints in Random Field Image
Segmentation.” CVPR: Computer Vision and Pattern Recognition, IEEE, 2011,
pp. 2089–96, doi:10.1109/CVPR.2011.5995503.'
short: 'C. Chen, D. Freedman, C. Lampert, in:, CVPR: Computer Vision and Pattern
Recognition, IEEE, 2011, pp. 2089–2096.'
conference:
end_date: 2011-06-25
location: Colorado Springs, CO, United States
name: 'CVPR: Conference on Computer Vision and Pattern Recognition'
start_date: 2011-06-20
date_created: 2018-12-11T12:02:45Z
date_published: 2011-07-22T00:00:00Z
date_updated: 2023-02-23T12:23:56Z
day: '22'
department:
- _id: HeEd
- _id: ChLa
doi: 10.1109/CVPR.2011.5995503
language:
- iso: eng
month: '07'
oa_version: None
page: 2089 - 2096
publication: 'CVPR: Computer Vision and Pattern Recognition'
publication_identifier:
eisbn:
- 978-1-4577-0395-9
isbn:
- 978-1-4577-0394-2
publication_status: published
publisher: IEEE
publist_id: '3294'
quality_controlled: '1'
related_material:
record:
- id: '5386'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Enforcing topological constraints in random field image segmentation
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3337'
abstract:
- lang: eng
text: Playing table tennis is a difficult task for robots, especially due to their
limitations of acceleration. A key bottleneck is the amount of time needed to
reach the desired hitting position and velocity of the racket for returning the
incoming ball. Here, it often does not suffice to simply extrapolate the ball's
trajectory after the opponent returns it but more information is needed. Humans
are able to predict the ball's trajectory based on the opponent's moves and, thus,
have a considerable advantage. Hence, we propose to incorporate an anticipation
system into robot table tennis players, which enables the robot to react earlier
while the opponent is performing the striking movement. Based on visual observation
of the opponent's racket movement, the robot can predict the aim of the opponent
and adjust its movement generation accordingly. The policies for deciding how
and when to react are obtained by reinforcement learning. We conduct experiments
with an existing robot player to show that the learned reaction policy can significantly
improve the performance of the overall system.
author:
- first_name: Zhikun
full_name: Wang, Zhikun
last_name: Wang
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
- first_name: Katharina
full_name: Mülling, Katharina
last_name: Mülling
- first_name: Bernhard
full_name: Schölkopf, Bernhard
last_name: Schölkopf
- first_name: Jan
full_name: Peters, Jan
last_name: Peters
citation:
ama: 'Wang Z, Lampert C, Mülling K, Schölkopf B, Peters J. Learning anticipation
policies for robot table tennis. In: IEEE; 2011:332-337. doi:10.1109/IROS.2011.6094892'
apa: 'Wang, Z., Lampert, C., Mülling, K., Schölkopf, B., & Peters, J. (2011).
Learning anticipation policies for robot table tennis (pp. 332–337). Presented
at the IROS: RSJ International Conference on Intelligent Robots and Systems, San
Francisco, USA: IEEE. https://doi.org/10.1109/IROS.2011.6094892'
chicago: Wang, Zhikun, Christoph Lampert, Katharina Mülling, Bernhard Schölkopf,
and Jan Peters. “Learning Anticipation Policies for Robot Table Tennis,” 332–37.
IEEE, 2011. https://doi.org/10.1109/IROS.2011.6094892.
ieee: 'Z. Wang, C. Lampert, K. Mülling, B. Schölkopf, and J. Peters, “Learning anticipation
policies for robot table tennis,” presented at the IROS: RSJ International Conference
on Intelligent Robots and Systems, San Francisco, USA, 2011, pp. 332–337.'
ista: 'Wang Z, Lampert C, Mülling K, Schölkopf B, Peters J. 2011. Learning anticipation
policies for robot table tennis. IROS: RSJ International Conference on Intelligent
Robots and Systems, 332–337.'
mla: Wang, Zhikun, et al. Learning Anticipation Policies for Robot Table Tennis.
IEEE, 2011, pp. 332–37, doi:10.1109/IROS.2011.6094892.
short: Z. Wang, C. Lampert, K. Mülling, B. Schölkopf, J. Peters, in:, IEEE, 2011,
pp. 332–337.
conference:
end_date: 2011-09-30
location: San Francisco, USA
name: 'IROS: RSJ International Conference on Intelligent Robots and Systems'
start_date: 2011-09-25
date_created: 2018-12-11T12:02:45Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:42:45Z
day: '01'
department:
- _id: ChLa
doi: 10.1109/IROS.2011.6094892
language:
- iso: eng
month: '01'
oa_version: None
page: 332 - 337
publication_status: published
publisher: IEEE
publist_id: '3293'
quality_controlled: '1'
scopus_import: 1
status: public
title: Learning anticipation policies for robot table tennis
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3338'
abstract:
- lang: eng
text: 'We consider 2-player games played on a finite state space for an infinite
number of rounds. The games are concurrent: in each round, the two players (player
1 and player 2) choose their moves inde- pendently and simultaneously; the current
state and the two moves determine the successor state. We study concurrent games
with ω-regular winning conditions specified as parity objectives. We consider
the qualitative analysis problems: the computation of the almost-sure and limit-sure
winning set of states, where player 1 can ensure to win with probability 1 and
with probability arbitrarily close to 1, respec- tively. In general the almost-sure
and limit-sure winning strategies require both infinite-memory as well as infinite-precision
(to describe probabilities). We study the bounded-rationality problem for qualitative
analysis of concurrent parity games, where the strategy set for player 1 is restricted
to bounded-resource strategies. In terms of precision, strategies can be deterministic,
uniform, finite-precision or infinite- precision; and in terms of memory, strategies
can be memoryless, finite-memory or infinite-memory. We present a precise and
complete characterization of the qualitative winning sets for all combinations
of classes of strategies. In particular, we show that uniform memoryless strategies
are as powerful as finite-precision infinite-memory strategies, and infinite-precision
memoryless strategies are as power- ful as infinite-precision finite-memory strategies.
We show that the winning sets can be computed in O(n2d+3) time, where n is the
size of the game structure and 2d is the number of priorities (or colors), and
our algorithms are symbolic. The membership problem of whether a state belongs
to a winning set can be decided in NP ∩ coNP. While this complexity is the same
as for the simpler class of turn-based parity games, where in each state only
one of the two players has a choice of moves, our algorithms, that are obtained
by characterization of the winning sets as μ-calculus formulas, are considerably
more involved than those for turn-based games.'
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: Chatterjee K. Bounded rationality in concurrent parity games. arXiv.
2011:1-51.
apa: Chatterjee, K. (2011). Bounded rationality in concurrent parity games. arXiv.
ArXiv.
chicago: Chatterjee, Krishnendu. “Bounded Rationality in Concurrent Parity Games.”
ArXiv. ArXiv, 2011.
ieee: K. Chatterjee, “Bounded rationality in concurrent parity games,” arXiv.
ArXiv, pp. 1–51, 2011.
ista: Chatterjee K. 2011. Bounded rationality in concurrent parity games. arXiv,
1–51, .
mla: Chatterjee, Krishnendu. “Bounded Rationality in Concurrent Parity Games.” ArXiv,
ArXiv, 2011, pp. 1–51.
short: K. Chatterjee, ArXiv (2011) 1–51.
date_created: 2018-12-11T12:02:45Z
date_published: 2011-07-11T00:00:00Z
date_updated: 2023-02-23T12:23:40Z
day: '11'
department:
- _id: KrCh
external_id:
arxiv:
- '1107.2146'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1107.2146
month: '07'
oa: 1
oa_version: Preprint
page: 1 - 51
publication: arXiv
publication_status: published
publisher: ArXiv
publist_id: '3287'
related_material:
record:
- id: '5380'
relation: earlier_version
status: public
status: public
title: Bounded rationality in concurrent parity games
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3339'
abstract:
- lang: eng
text: 'Turn-based stochastic games and its important subclass Markov decision processes
(MDPs) provide models for systems with both probabilistic and nondeterministic
behaviors. We consider turn-based stochastic games with two classical quantitative
objectives: discounted-sum and long-run average objectives. The game models and
the quantitative objectives are widely used in probabilistic verification, planning,
optimal inventory control, network protocol and performance analysis. Games and
MDPs that model realistic systems often have very large state spaces, and probabilistic
abstraction techniques are necessary to handle the state-space explosion. The
commonly used full-abstraction techniques do not yield space-savings for systems
that have many states with similar value, but does not necessarily have similar
transition structure. A semi-abstraction technique, namely Magnifying-lens abstractions
(MLA), that clusters states based on value only, disregarding differences in their
transition relation was proposed for qualitative objectives (reachability and
safety objectives). In this paper we extend the MLA technique to solve stochastic
games with discounted-sum and long-run average objectives. We present the MLA
technique based abstraction-refinement algorithm for stochastic games and MDPs
with discounted-sum objectives. For long-run average objectives, our solution
works for all MDPs and a sub-class of stochastic games where every state has the
same value. '
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: Luca
full_name: De Alfaro, Luca
last_name: De Alfaro
- first_name: Roy
full_name: Pritam, Roy
last_name: Pritam
citation:
ama: Chatterjee K, De Alfaro L, Pritam R. Magnifying lens abstraction for stochastic
games with discounted and long-run average objectives. arXiv. 2011.
apa: Chatterjee, K., De Alfaro, L., & Pritam, R. (2011). Magnifying lens abstraction
for stochastic games with discounted and long-run average objectives. arXiv.
ArXiv.
chicago: Chatterjee, Krishnendu, Luca De Alfaro, and Roy Pritam. “Magnifying Lens
Abstraction for Stochastic Games with Discounted and Long-Run Average Objectives.”
ArXiv. ArXiv, 2011.
ieee: K. Chatterjee, L. De Alfaro, and R. Pritam, “Magnifying lens abstraction for
stochastic games with discounted and long-run average objectives,” arXiv.
ArXiv, 2011.
ista: Chatterjee K, De Alfaro L, Pritam R. 2011. Magnifying lens abstraction for
stochastic games with discounted and long-run average objectives. arXiv, .
mla: Chatterjee, Krishnendu, et al. “Magnifying Lens Abstraction for Stochastic
Games with Discounted and Long-Run Average Objectives.” ArXiv, ArXiv, 2011.
short: K. Chatterjee, L. De Alfaro, R. Pritam, ArXiv (2011).
date_created: 2018-12-11T12:02:46Z
date_published: 2011-07-11T00:00:00Z
date_updated: 2021-01-12T07:42:46Z
day: '11'
department:
- _id: KrCh
external_id:
arxiv:
- '1107.2132'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1107.2132
month: '07'
oa: 1
oa_version: Preprint
page: '17'
publication: arXiv
publication_status: published
publisher: ArXiv
publist_id: '3286'
status: public
title: Magnifying lens abstraction for stochastic games with discounted and long-run
average objectives
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3342'
abstract:
- lang: eng
text: 'We consider Markov decision processes (MDPs) with ω-regular specifications
given as parity objectives. We consider the problem of computing the set of almost-sure
winning states from where the objective can be ensured with probability 1. The
algorithms for the computation of the almost-sure winning set for parity objectives
iteratively use the solutions for the almost-sure winning set for Büchi objectives
(a special case of parity objectives). Our contributions are as follows: First,
we present the first subquadratic symbolic algorithm to compute the almost-sure
winning set for MDPs with Büchi objectives; our algorithm takes O(nm) symbolic
steps as compared to the previous known algorithm that takes O(n 2) symbolic steps,
where n is the number of states and m is the number of edges of the MDP. In practice
MDPs often have constant out-degree, and then our symbolic algorithm takes O(nn) symbolic
steps, as compared to the previous known O(n 2) symbolic steps algorithm. Second,
we present a new algorithm, namely win-lose algorithm, with the following two
properties: (a) the algorithm iteratively computes subsets of the almost-sure
winning set and its complement, as compared to all previous algorithms that discover
the almost-sure winning set upon termination; and (b) requires O(nK) symbolic
steps, where K is the maximal number of edges of strongly connected components
(scc’s) of the MDP. The win-lose algorithm requires symbolic computation of scc’s.
Third, we improve the algorithm for symbolic scc computation; the previous known
algorithm takes linear symbolic steps, and our new algorithm improves the constants
associated with the linear number of steps. In the worst case the previous known
algorithm takes 5·n symbolic steps, whereas our new algorithm takes 4 ·n symbolic
steps.'
alternative_title:
- LNCS
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: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Manas
full_name: Joglekar, Manas
last_name: Joglekar
- first_name: Shah
full_name: Nisarg, Shah
last_name: Nisarg
citation:
ama: 'Chatterjee K, Henzinger MH, Joglekar M, Nisarg S. Symbolic algorithms for
qualitative analysis of Markov decision processes with Büchi objectives. In: Gopalakrishnan
G, Qadeer S, eds. Vol 6806. Springer; 2011:260-276. doi:10.1007/978-3-642-22110-1_21'
apa: 'Chatterjee, K., Henzinger, M. H., Joglekar, M., & Nisarg, S. (2011). Symbolic
algorithms for qualitative analysis of Markov decision processes with Büchi objectives.
In G. Gopalakrishnan & S. Qadeer (Eds.) (Vol. 6806, pp. 260–276). Presented
at the CAV: Computer Aided Verification, Snowbird, USA: Springer. https://doi.org/10.1007/978-3-642-22110-1_21'
chicago: Chatterjee, Krishnendu, Monika H Henzinger, Manas Joglekar, and Shah Nisarg.
“Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with
Büchi Objectives.” edited by Ganesh Gopalakrishnan and Shaz Qadeer, 6806:260–76.
Springer, 2011. https://doi.org/10.1007/978-3-642-22110-1_21.
ieee: 'K. Chatterjee, M. H. Henzinger, M. Joglekar, and S. Nisarg, “Symbolic algorithms
for qualitative analysis of Markov decision processes with Büchi objectives,”
presented at the CAV: Computer Aided Verification, Snowbird, USA, 2011, vol. 6806,
pp. 260–276.'
ista: 'Chatterjee K, Henzinger MH, Joglekar M, Nisarg S. 2011. Symbolic algorithms
for qualitative analysis of Markov decision processes with Büchi objectives. CAV:
Computer Aided Verification, LNCS, vol. 6806, 260–276.'
mla: Chatterjee, Krishnendu, et al. Symbolic Algorithms for Qualitative Analysis
of Markov Decision Processes with Büchi Objectives. Edited by Ganesh Gopalakrishnan
and Shaz Qadeer, vol. 6806, Springer, 2011, pp. 260–76, doi:10.1007/978-3-642-22110-1_21.
short: K. Chatterjee, M.H. Henzinger, M. Joglekar, S. Nisarg, in:, G. Gopalakrishnan,
S. Qadeer (Eds.), Springer, 2011, pp. 260–276.
conference:
end_date: 2011-07-20
location: Snowbird, USA
name: 'CAV: Computer Aided Verification'
start_date: 2011-07-14
date_created: 2018-12-11T12:02:47Z
date_published: 2011-08-11T00:00:00Z
date_updated: 2023-02-23T11:00:13Z
day: '11'
department:
- _id: KrCh
doi: 10.1007/978-3-642-22110-1_21
editor:
- first_name: Ganesh
full_name: Gopalakrishnan, Ganesh
last_name: Gopalakrishnan
- first_name: Shaz
full_name: Qadeer, Shaz
last_name: Qadeer
external_id:
arxiv:
- '1104.3348'
intvolume: ' 6806'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1104.3348
month: '08'
oa: 1
oa_version: Preprint
page: 260 - 276
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication_status: published
publisher: Springer
publist_id: '3282'
quality_controlled: '1'
related_material:
record:
- id: '2831'
relation: later_version
status: public
status: public
title: Symbolic algorithms for qualitative analysis of Markov decision processes with
Büchi objectives
type: conference
user_id: 72615eeb-f1f3-11ec-aa25-d4573ddc34fd
volume: 6806
year: '2011'
...
---
_id: '3343'
abstract:
- lang: eng
text: 'We present faster and dynamic algorithms for the following problems arising
in probabilistic verification: Computation of the maximal end-component (mec)
decomposition of Markov decision processes (MDPs), and of the almost sure winning
set for reachability and parity objectives in MDPs. We achieve the following running
time for static algorithms in MDPs with graphs of n vertices and m edges: (1)
O(m · min{ √m, n2/3 }) for the mec decomposition, improving the longstanding O(m·n)
bound; (2) O(m·n2/3) for reachability objectives, improving the previous O(m ·
√m) bound for m > n4/3; and (3) O(m · min{ √m, n2/3 } · log(d)) for parity
objectives with d priorities, improving the previous O(m · √m · d) bound. We also
give incremental and decremental algorithms in linear time for mec decomposition
and reachability objectives and O(m · log d) time for parity ob jectives.'
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: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'Chatterjee K, Henzinger MH. Faster and dynamic algorithms for maximal end-component
decomposition and related graph problems in probabilistic verification. In: SIAM;
2011:1318-1336. doi:10.1137/1.9781611973082.101'
apa: 'Chatterjee, K., & Henzinger, M. H. (2011). Faster and dynamic algorithms
for maximal end-component decomposition and related graph problems in probabilistic
verification (pp. 1318–1336). Presented at the SODA: Symposium on Discrete Algorithms,
San Francisco, SA, United States: SIAM. https://doi.org/10.1137/1.9781611973082.101'
chicago: Chatterjee, Krishnendu, and Monika H Henzinger. “Faster and Dynamic Algorithms
for Maximal End-Component Decomposition and Related Graph Problems in Probabilistic
Verification,” 1318–36. SIAM, 2011. https://doi.org/10.1137/1.9781611973082.101.
ieee: 'K. Chatterjee and M. H. Henzinger, “Faster and dynamic algorithms for maximal
end-component decomposition and related graph problems in probabilistic verification,”
presented at the SODA: Symposium on Discrete Algorithms, San Francisco, SA, United
States, 2011, pp. 1318–1336.'
ista: 'Chatterjee K, Henzinger MH. 2011. Faster and dynamic algorithms for maximal
end-component decomposition and related graph problems in probabilistic verification.
SODA: Symposium on Discrete Algorithms, 1318–1336.'
mla: Chatterjee, Krishnendu, and Monika H. Henzinger. Faster and Dynamic Algorithms
for Maximal End-Component Decomposition and Related Graph Problems in Probabilistic
Verification. SIAM, 2011, pp. 1318–36, doi:10.1137/1.9781611973082.101.
short: K. Chatterjee, M.H. Henzinger, in:, SIAM, 2011, pp. 1318–1336.
conference:
end_date: 2011-01-25
location: San Francisco, SA, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2011-01-23
date_created: 2018-12-11T12:02:47Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2023-02-14T10:36:10Z
day: '01'
department:
- _id: KrCh
doi: 10.1137/1.9781611973082.101
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprints.cs.univie.ac.at/21/
month: '01'
oa: 1
oa_version: Submitted Version
page: 1318 - 1336
publication_status: published
publisher: SIAM
publist_id: '3278'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Faster and dynamic algorithms for maximal end-component decomposition and related
graph problems in probabilistic verification
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3344'
abstract:
- lang: eng
text: 'Games played on graphs provide the mathematical framework to analyze several
important problems in computer science as well as mathematics, such as the synthesis
problem of Church, model checking of open reactive systems and many others. On
the basis of mode of interaction of the players these games can be classified
as follows: (a) turn-based (players make moves in turns); and (b) concurrent (players
make moves simultaneously). On the basis of the information available to the players
these games can be classified as follows: (a) perfect-information (players have
perfect view of the game); and (b) partial-information (players have partial view
of the game). In this talk we will consider all these classes of games with reachability
objectives, where the goal of one player is to reach a set of target vertices
of the graph, and the goal of the opponent player is to prevent the player from
reaching the target. We will survey the results for various classes of games,
and the results range from linear time decision algorithms to EXPTIME-complete
problems to undecidable problems.'
alternative_title:
- LNCS
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: 'Chatterjee K. Graph games with reachability objectives. In: Delzanno G, Potapov
I, eds. Vol 6945. Springer; 2011:1-1. doi:10.1007/978-3-642-24288-5_1'
apa: 'Chatterjee, K. (2011). Graph games with reachability objectives. In G. Delzanno
& I. Potapov (Eds.) (Vol. 6945, pp. 1–1). Presented at the RP: Reachability
Problems, Genoa, Italy: Springer. https://doi.org/10.1007/978-3-642-24288-5_1'
chicago: Chatterjee, Krishnendu. “Graph Games with Reachability Objectives.” edited
by Giorgo Delzanno and Igor Potapov, 6945:1–1. Springer, 2011. https://doi.org/10.1007/978-3-642-24288-5_1.
ieee: 'K. Chatterjee, “Graph games with reachability objectives,” presented at the
RP: Reachability Problems, Genoa, Italy, 2011, vol. 6945, pp. 1–1.'
ista: 'Chatterjee K. 2011. Graph games with reachability objectives. RP: Reachability
Problems, LNCS, vol. 6945, 1–1.'
mla: Chatterjee, Krishnendu. Graph Games with Reachability Objectives. Edited
by Giorgo Delzanno and Igor Potapov, vol. 6945, Springer, 2011, pp. 1–1, doi:10.1007/978-3-642-24288-5_1.
short: K. Chatterjee, in:, G. Delzanno, I. Potapov (Eds.), Springer, 2011, pp. 1–1.
conference:
end_date: 2011-09-30
location: Genoa, Italy
name: 'RP: Reachability Problems'
start_date: 2011-09-28
date_created: 2018-12-11T12:02:47Z
date_published: 2011-10-15T00:00:00Z
date_updated: 2021-01-12T07:42:48Z
day: '15'
department:
- _id: KrCh
doi: 10.1007/978-3-642-24288-5_1
editor:
- first_name: Giorgo
full_name: Delzanno, Giorgo
last_name: Delzanno
- first_name: Igor
full_name: Potapov, Igor
last_name: Potapov
intvolume: ' 6945'
language:
- iso: eng
month: '10'
oa_version: None
page: 1 - 1
publication_status: published
publisher: Springer
publist_id: '3277'
quality_controlled: '1'
status: public
title: Graph games with reachability objectives
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6945
year: '2011'
...
---
_id: '10907'
abstract:
- lang: eng
text: This paper presents a method to create a model of an articulated object using
the planar motion in an initialization video. The model consists of rigid parts
connected by points of articulation. The rigid parts are described by the positions
of salient feature-points tracked throughout the video. Following a filtering
step that identifies points that belong to different objects, rigid parts are
found by a grouping process in a graph pyramid. Valid articulation points are
selected by verifying multiple hypotheses for each pair of parts.
acknowledgement: This work has been partially supported by the Austrian Science Fund
under grants S9103-N13 and P18716-N13.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Nicole M.
full_name: Artner, Nicole M.
last_name: Artner
- first_name: Adrian
full_name: Ion, Adrian
id: 29F89302-F248-11E8-B48F-1D18A9856A87
last_name: Ion
- first_name: Walter G.
full_name: Kropatsch, Walter G.
last_name: Kropatsch
citation:
ama: 'Artner NM, Ion A, Kropatsch WG. Spatio-temporal extraction of articulated
models in a graph pyramid. In: Jiang X, Ferrer M, Torsello A, eds. Graph-Based
Representations in Pattern Recognition. Vol 6658. LNIP. Berlin, Heidelberg:
Springer; 2011:215-224. doi:10.1007/978-3-642-20844-7_22'
apa: 'Artner, N. M., Ion, A., & Kropatsch, W. G. (2011). Spatio-temporal extraction
of articulated models in a graph pyramid. In X. Jiang, M. Ferrer, & A. Torsello
(Eds.), Graph-Based Representations in Pattern Recognition (Vol. 6658,
pp. 215–224). Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-20844-7_22'
chicago: 'Artner, Nicole M., Adrian Ion, and Walter G. Kropatsch. “Spatio-Temporal
Extraction of Articulated Models in a Graph Pyramid.” In Graph-Based Representations
in Pattern Recognition, edited by Xiaoyi Jiang, Miquel Ferrer, and Andrea
Torsello, 6658:215–24. LNIP. Berlin, Heidelberg: Springer, 2011. https://doi.org/10.1007/978-3-642-20844-7_22.'
ieee: N. M. Artner, A. Ion, and W. G. Kropatsch, “Spatio-temporal extraction of
articulated models in a graph pyramid,” in Graph-Based Representations in Pattern
Recognition, Münster, Germany, 2011, vol. 6658, pp. 215–224.
ista: 'Artner NM, Ion A, Kropatsch WG. 2011. Spatio-temporal extraction of articulated
models in a graph pyramid. Graph-Based Representations in Pattern Recognition.
GbRPR: Graph-based Representations in Pattern RecognitionLNIP, LNCS, vol. 6658,
215–224.'
mla: Artner, Nicole M., et al. “Spatio-Temporal Extraction of Articulated Models
in a Graph Pyramid.” Graph-Based Representations in Pattern Recognition,
edited by Xiaoyi Jiang et al., vol. 6658, Springer, 2011, pp. 215–24, doi:10.1007/978-3-642-20844-7_22.
short: N.M. Artner, A. Ion, W.G. Kropatsch, in:, X. Jiang, M. Ferrer, A. Torsello
(Eds.), Graph-Based Representations in Pattern Recognition, Springer, Berlin,
Heidelberg, 2011, pp. 215–224.
conference:
end_date: 2011-05-20
location: Münster, Germany
name: 'GbRPR: Graph-based Representations in Pattern Recognition'
start_date: 2011-05-18
date_created: 2022-03-21T08:08:35Z
date_published: 2011-06-01T00:00:00Z
date_updated: 2023-09-05T14:10:15Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/978-3-642-20844-7_22
editor:
- first_name: Xiaoyi
full_name: Jiang, Xiaoyi
last_name: Jiang
- first_name: Miquel
full_name: Ferrer, Miquel
last_name: Ferrer
- first_name: Andrea
full_name: Torsello, Andrea
last_name: Torsello
intvolume: ' 6658'
language:
- iso: eng
month: '06'
oa_version: None
page: 215-224
place: Berlin, Heidelberg
publication: Graph-Based Representations in Pattern Recognition
publication_identifier:
eisbn:
- '9783642208447'
eissn:
- 1611-3349
isbn:
- '9783642208430'
issn:
- 0302-9743
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
series_title: LNIP
status: public
title: Spatio-temporal extraction of articulated models in a graph pyramid
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 6658
year: '2011'
...
---
_id: '11094'
abstract:
- lang: eng
text: Nuclear pore complexes (NPCs) assemble at the end of mitosis during nuclear
envelope (NE) reformation and into an intact NE as cells progress through interphase.
Although recent studies have shown that NPC formation occurs by two different
molecular mechanisms at two distinct cell cycle stages, little is known about
the molecular players that mediate the fusion of the outer and inner nuclear membranes
to form pores. In this paper, we provide evidence that the transmembrane nucleoporin
(Nup), POM121, but not the Nup107–160 complex, is present at new pore assembly
sites at a time that coincides with inner nuclear membrane (INM) and outer nuclear
membrane (ONM) fusion. Overexpression of POM121 resulted in juxtaposition of the
INM and ONM. Additionally, Sun1, an INM protein that is known to interact with
the cytoskeleton, was specifically required for interphase assembly and localized
with POM121 at forming pores. We propose a model in which POM121 and Sun1 interact
transiently to promote early steps of interphase NPC assembly.
article_processing_charge: No
article_type: original
author:
- first_name: Jessica A.
full_name: Talamas, Jessica A.
last_name: Talamas
- 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: Talamas JA, Hetzer M. POM121 and Sun1 play a role in early steps of interphase
NPC assembly. Journal of Cell Biology. 2011;194(1):27-37. doi:10.1083/jcb.201012154
apa: Talamas, J. A., & Hetzer, M. (2011). POM121 and Sun1 play a role in early
steps of interphase NPC assembly. Journal of Cell Biology. Rockefeller
University Press. https://doi.org/10.1083/jcb.201012154
chicago: Talamas, Jessica A., and Martin Hetzer. “POM121 and Sun1 Play a Role in
Early Steps of Interphase NPC Assembly.” Journal of Cell Biology. Rockefeller
University Press, 2011. https://doi.org/10.1083/jcb.201012154.
ieee: J. A. Talamas and M. Hetzer, “POM121 and Sun1 play a role in early steps of
interphase NPC assembly,” Journal of Cell Biology, vol. 194, no. 1. Rockefeller
University Press, pp. 27–37, 2011.
ista: Talamas JA, Hetzer M. 2011. POM121 and Sun1 play a role in early steps of
interphase NPC assembly. Journal of Cell Biology. 194(1), 27–37.
mla: Talamas, Jessica A., and Martin Hetzer. “POM121 and Sun1 Play a Role in Early
Steps of Interphase NPC Assembly.” Journal of Cell Biology, vol. 194, no.
1, Rockefeller University Press, 2011, pp. 27–37, doi:10.1083/jcb.201012154.
short: J.A. Talamas, M. Hetzer, Journal of Cell Biology 194 (2011) 27–37.
date_created: 2022-04-07T07:52:18Z
date_published: 2011-07-04T00:00:00Z
date_updated: 2022-07-18T08:53:46Z
day: '04'
doi: 10.1083/jcb.201012154
extern: '1'
external_id:
pmid:
- '21727197'
intvolume: ' 194'
issue: '1'
keyword:
- Cell Biology
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1083/jcb.201012154
month: '07'
oa: 1
oa_version: Published Version
page: 27-37
pmid: 1
publication: Journal of Cell Biology
publication_identifier:
eissn:
- 1540-8140
issn:
- 0021-9525
publication_status: published
publisher: Rockefeller University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: POM121 and Sun1 play a role in early steps of interphase NPC assembly
type: journal_article
user_id: 72615eeb-f1f3-11ec-aa25-d4573ddc34fd
volume: 194
year: '2011'
...
---
_id: '11095'
article_processing_charge: No
article_type: letter_note
author:
- 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: Giacomo
full_name: Cavalli, Giacomo
last_name: Cavalli
citation:
ama: Hetzer M, Cavalli G. Editorial overview. Current Opinion in Cell Biology.
2011;23(3):255-257. doi:10.1016/j.ceb.2011.04.013
apa: Hetzer, M., & Cavalli, G. (2011). Editorial overview. Current Opinion
in Cell Biology. Elsevier. https://doi.org/10.1016/j.ceb.2011.04.013
chicago: Hetzer, Martin, and Giacomo Cavalli. “Editorial Overview.” Current Opinion
in Cell Biology. Elsevier, 2011. https://doi.org/10.1016/j.ceb.2011.04.013.
ieee: M. Hetzer and G. Cavalli, “Editorial overview,” Current Opinion in Cell
Biology, vol. 23, no. 3. Elsevier, pp. 255–257, 2011.
ista: Hetzer M, Cavalli G. 2011. Editorial overview. Current Opinion in Cell Biology.
23(3), 255–257.
mla: Hetzer, Martin, and Giacomo Cavalli. “Editorial Overview.” Current Opinion
in Cell Biology, vol. 23, no. 3, Elsevier, 2011, pp. 255–57, doi:10.1016/j.ceb.2011.04.013.
short: M. Hetzer, G. Cavalli, Current Opinion in Cell Biology 23 (2011) 255–257.
date_created: 2022-04-07T07:52:27Z
date_published: 2011-06-01T00:00:00Z
date_updated: 2022-07-18T08:39:40Z
day: '01'
doi: 10.1016/j.ceb.2011.04.013
extern: '1'
external_id:
pmid:
- '21592757'
intvolume: ' 23'
issue: '3'
keyword:
- Cell Biology
language:
- iso: eng
month: '06'
oa_version: None
page: 255-257
pmid: 1
publication: Current Opinion in Cell Biology
publication_identifier:
issn:
- 0955-0674
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Editorial overview
type: journal_article
user_id: 72615eeb-f1f3-11ec-aa25-d4573ddc34fd
volume: 23
year: '2011'
...
---
_id: '11096'
abstract:
- lang: eng
text: As the gatekeepers of the eukaryotic cell nucleus, nuclear pore complexes
(NPCs) mediate all molecular trafficking between the nucleoplasm and the cytoplasm.
In recent years, transport-independent functions of NPC components, nucleoporins,
have been identified including roles in chromatin organization and gene regulation.
Here, we summarize our current view of the NPC as a dynamic hub for the integration
of chromatin regulation and nuclear trafficking and discuss the functional interplay
between nucleoporins and the nuclear genome.
article_processing_charge: No
article_type: original
author:
- first_name: Yun
full_name: Liang, Yun
last_name: Liang
- 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, Hetzer M. Functional interactions between nucleoporins and chromatin.
Current Opinion in Cell Biology. 2011;23(1):65-70. doi:10.1016/j.ceb.2010.09.008
apa: Liang, Y., & Hetzer, M. (2011). Functional interactions between nucleoporins
and chromatin. Current Opinion in Cell Biology. Elsevier. https://doi.org/10.1016/j.ceb.2010.09.008
chicago: Liang, Yun, and Martin Hetzer. “Functional Interactions between Nucleoporins
and Chromatin.” Current Opinion in Cell Biology. Elsevier, 2011. https://doi.org/10.1016/j.ceb.2010.09.008.
ieee: Y. Liang and M. Hetzer, “Functional interactions between nucleoporins and
chromatin,” Current Opinion in Cell Biology, vol. 23, no. 1. Elsevier,
pp. 65–70, 2011.
ista: Liang Y, Hetzer M. 2011. Functional interactions between nucleoporins and
chromatin. Current Opinion in Cell Biology. 23(1), 65–70.
mla: Liang, Yun, and Martin Hetzer. “Functional Interactions between Nucleoporins
and Chromatin.” Current Opinion in Cell Biology, vol. 23, no. 1, Elsevier,
2011, pp. 65–70, doi:10.1016/j.ceb.2010.09.008.
short: Y. Liang, M. Hetzer, Current Opinion in Cell Biology 23 (2011) 65–70.
date_created: 2022-04-07T07:52:37Z
date_published: 2011-02-01T00:00:00Z
date_updated: 2022-07-18T08:53:48Z
day: '01'
doi: 10.1016/j.ceb.2010.09.008
extern: '1'
external_id:
pmid:
- '21030234'
intvolume: ' 23'
issue: '1'
keyword:
- Cell Biology
language:
- iso: eng
month: '02'
oa_version: None
page: 65-70
pmid: 1
publication: Current Opinion in Cell Biology
publication_identifier:
issn:
- 0955-0674
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Functional interactions between nucleoporins and chromatin
type: journal_article
user_id: 72615eeb-f1f3-11ec-aa25-d4573ddc34fd
volume: 23
year: '2011'
...
---
_id: '11100'
abstract:
- lang: eng
text: Eukaryotic cell function depends on the physical separation of nucleoplasmic
and cytoplasmic components by the nuclear envelope (NE). Molecular communication
between the two compartments involves active, signal-mediated trafficking, a function
that is exclusively performed by nuclear pore complexes (NPCs). The individual
NPC components and the mechanisms that are involved in nuclear trafficking are
well documented and have become textbook knowledge. However, in addition to their
roles as nuclear gatekeepers, NPC components-nucleoporins-have been shown to have
critical roles in chromatin organization and gene regulation. These findings have
sparked new enthusiasm to study the roles of this multiprotein complex in nuclear
organization and explore novel functions that in some cases appear to go beyond
a role in transport. Here, we discuss our present view of NPC biogenesis, which
is tightly linked to proper cell cycle progression and cell differentiation. In
addition, we summarize new data suggesting that NPCs represent dynamic hubs for
the integration of gene regulation and nuclear transport processes.
article_processing_charge: No
article_type: original
author:
- first_name: M.
full_name: Capelson, M.
last_name: Capelson
- first_name: C.
full_name: Doucet, C.
last_name: Doucet
- 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: 'Capelson M, Doucet C, Hetzer M. Nuclear pore complexes: Guardians of the nuclear
genome. Cold Spring Harbor Symposia on Quantitative Biology. 2011;75:585-597.
doi:10.1101/sqb.2010.75.059'
apa: 'Capelson, M., Doucet, C., & Hetzer, M. (2011). Nuclear pore complexes:
Guardians of the nuclear genome. Cold Spring Harbor Symposia on Quantitative
Biology. Cold Spring Harbor Laboratory Press. https://doi.org/10.1101/sqb.2010.75.059'
chicago: 'Capelson, M., C. Doucet, and Martin Hetzer. “Nuclear Pore Complexes: Guardians
of the Nuclear Genome.” Cold Spring Harbor Symposia on Quantitative Biology.
Cold Spring Harbor Laboratory Press, 2011. https://doi.org/10.1101/sqb.2010.75.059.'
ieee: 'M. Capelson, C. Doucet, and M. Hetzer, “Nuclear pore complexes: Guardians
of the nuclear genome,” Cold Spring Harbor Symposia on Quantitative Biology,
vol. 75. Cold Spring Harbor Laboratory Press, pp. 585–597, 2011.'
ista: 'Capelson M, Doucet C, Hetzer M. 2011. Nuclear pore complexes: Guardians of
the nuclear genome. Cold Spring Harbor Symposia on Quantitative Biology. 75, 585–597.'
mla: 'Capelson, M., et al. “Nuclear Pore Complexes: Guardians of the Nuclear Genome.”
Cold Spring Harbor Symposia on Quantitative Biology, vol. 75, Cold Spring
Harbor Laboratory Press, 2011, pp. 585–97, doi:10.1101/sqb.2010.75.059.'
short: M. Capelson, C. Doucet, M. Hetzer, Cold Spring Harbor Symposia on Quantitative
Biology 75 (2011) 585–597.
date_created: 2022-04-07T07:53:18Z
date_published: 2011-04-18T00:00:00Z
date_updated: 2022-07-18T08:54:23Z
day: '18'
doi: 10.1101/sqb.2010.75.059
extern: '1'
external_id:
pmid:
- '21502404'
intvolume: ' 75'
keyword:
- Genetics
- Molecular Biology
- Biochemistry
language:
- iso: eng
month: '04'
oa_version: None
page: 585-597
pmid: 1
publication: Cold Spring Harbor Symposia on Quantitative Biology
publication_identifier:
isbn:
- '9781936113071'
issn:
- 0091-7451
- 1943-4456
publication_status: published
publisher: Cold Spring Harbor Laboratory Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Nuclear pore complexes: Guardians of the nuclear genome'
type: journal_article
user_id: 72615eeb-f1f3-11ec-aa25-d4573ddc34fd
volume: 75
year: '2011'
...
---
_id: '112'
abstract:
- lang: eng
text: Particle beams are important tools for probing atomic and molecular interactions.
Here we demonstrate that particle beams also offer a unique opportunity to investigate
interactions in macroscopic systems, such as granular media. Motivated by recent
experiments on streams of grains that exhibit liquid-like breakup into droplets,
we use molecular dynamics simulations to investigate the evolution of a dense
stream of macroscopic spheres accelerating out of an opening at the bottom of
a reservoir. We show how nanoscale details associated with energy dissipation
during collisions modify the stream\'s macroscopic behavior. We find that inelastic
collisions collimate the stream, while the presence of short-range attractive
interactions drives structure formation. Parameterizing the collision dynamics
by the coefficient of restitution (i.e., the ratio of relative velocities before
and after impact) and the strength of the cohesive interaction, we map out a spectrum
of behaviors that ranges from gaslike jets in which all grains drift apart to
liquid-like streams that break into large droplets containing hundreds of grains.
We also find a new, intermediate regime in which small aggregates form by capture
from the gas phase, similar to what can be observed in molecular beams. Our results
show that nearly all aspects of stream behavior are closely related to the velocity
gradient associated with vertical free fall. Led by this observation, we propose
a simple energy balance model to explain the droplet formation process. The qualitative
as well as many quantitative features of the simulations and the model compare
well with available experimental data and provide a first quantitative measure
of the role of attractions in freely cooling granular streams.
acknowledgement: This work was supported by the NSF through CBET-0933242. We acknowledge
use of shared facilities provided by the Keck Facility for Ultrafast Imaging at
the University of Chicago and by the Chicago MRSEC through NSF DMR-0820054. Software
support by Itasca Consulting Group, Inc., under the Itasca Educational Partnership
is gratefully acknowledged. H.G. thanks the German-American Fulbright Commission
for fellowship support during his stay at the University of Chicago.
article_number: '051302'
arxiv: 1
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: Helge
full_name: Grütjen, Helge
last_name: Grütjen
- first_name: John
full_name: Royer, John
last_name: Royer
- first_name: Heinrich
full_name: Jaeger, Heinrich
last_name: Jaeger
citation:
ama: Waitukaitis SR, Grütjen H, Royer J, Jaeger H. Droplet and cluster formation
in freely falling granular streams. Physical Review E. 2011;83(5). doi:10.1103/PhysRevE.83.051302
apa: Waitukaitis, S. R., Grütjen, H., Royer, J., & Jaeger, H. (2011). Droplet
and cluster formation in freely falling granular streams. Physical Review E.
American Physical Society. https://doi.org/10.1103/PhysRevE.83.051302
chicago: Waitukaitis, Scott R, Helge Grütjen, John Royer, and Heinrich Jaeger. “Droplet
and Cluster Formation in Freely Falling Granular Streams.” Physical Review
E. American Physical Society, 2011. https://doi.org/10.1103/PhysRevE.83.051302.
ieee: S. R. Waitukaitis, H. Grütjen, J. Royer, and H. Jaeger, “Droplet and cluster
formation in freely falling granular streams,” Physical Review E, vol.
83, no. 5. American Physical Society, 2011.
ista: Waitukaitis SR, Grütjen H, Royer J, Jaeger H. 2011. Droplet and cluster formation
in freely falling granular streams. Physical Review E. 83(5), 051302.
mla: Waitukaitis, Scott R., et al. “Droplet and Cluster Formation in Freely Falling
Granular Streams.” Physical Review E, vol. 83, no. 5, 051302, American
Physical Society, 2011, doi:10.1103/PhysRevE.83.051302.
short: S.R. Waitukaitis, H. Grütjen, J. Royer, H. Jaeger, Physical Review E 83 (2011).
date_created: 2018-12-11T11:44:41Z
date_published: 2011-05-12T00:00:00Z
date_updated: 2021-01-12T06:48:25Z
day: '12'
doi: 10.1103/PhysRevE.83.051302
extern: '1'
external_id:
arxiv:
- '1006.1371'
intvolume: ' 83'
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1006.1371
month: '05'
oa: 1
oa_version: Preprint
publication: Physical Review E
publication_status: published
publisher: American Physical Society
publist_id: '7942'
quality_controlled: '1'
status: public
title: Droplet and cluster formation in freely falling granular streams
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 83
year: '2011'
...
---
_id: '11673'
abstract:
- lang: eng
text: Given only the URL of a Web page, can we identify its topic? We study this
problem in detail by exploring a large number of different feature sets and algorithms
on several datasets. We also show that the inherent overlap between topics and
the sparsity of the information in URLs makes this a very challenging problem.
Web page classification without a page’s content is desirable when the content
is not available at all, when a classification is needed before obtaining the
content, or when classification speed is of utmost importance. For our experiments
we used five different corpora comprising a total of about 3 million (URL, classification)
pairs. We evaluated several techniques for feature generation and classification
algorithms. The individual binary classifiers were then combined via boosting
into metabinary classifiers. We achieve typical F-measure values between 80 and
85, and a typical precision of around 86. The precision can be pushed further
over 90 while maintaining a typical level of recall between 30 and 40.
article_number: '15'
article_processing_charge: No
article_type: original
author:
- first_name: Eda
full_name: Baykan, Eda
last_name: Baykan
- 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: Ludmila
full_name: Marian, Ludmila
last_name: Marian
- first_name: Ingmar
full_name: Weber, Ingmar
last_name: Weber
citation:
ama: Baykan E, Henzinger MH, Marian L, Weber I. A comprehensive study of features
and algorithms for URL-based topic classification. ACM Transactions on the
Web. 2011;5(3). doi:10.1145/1993053.1993057
apa: Baykan, E., Henzinger, M. H., Marian, L., & Weber, I. (2011). A comprehensive
study of features and algorithms for URL-based topic classification. ACM Transactions
on the Web. Association for Computing Machinery. https://doi.org/10.1145/1993053.1993057
chicago: Baykan, Eda, Monika H Henzinger, Ludmila Marian, and Ingmar Weber. “A Comprehensive
Study of Features and Algorithms for URL-Based Topic Classification.” ACM Transactions
on the Web. Association for Computing Machinery, 2011. https://doi.org/10.1145/1993053.1993057.
ieee: E. Baykan, M. H. Henzinger, L. Marian, and I. Weber, “A comprehensive study
of features and algorithms for URL-based topic classification,” ACM Transactions
on the Web, vol. 5, no. 3. Association for Computing Machinery, 2011.
ista: Baykan E, Henzinger MH, Marian L, Weber I. 2011. A comprehensive study of
features and algorithms for URL-based topic classification. ACM Transactions on
the Web. 5(3), 15.
mla: Baykan, Eda, et al. “A Comprehensive Study of Features and Algorithms for URL-Based
Topic Classification.” ACM Transactions on the Web, vol. 5, no. 3, 15,
Association for Computing Machinery, 2011, doi:10.1145/1993053.1993057.
short: E. Baykan, M.H. Henzinger, L. Marian, I. Weber, ACM Transactions on the Web
5 (2011).
date_created: 2022-07-27T13:48:11Z
date_published: 2011-07-01T00:00:00Z
date_updated: 2022-09-12T08:46:56Z
day: '01'
doi: 10.1145/1993053.1993057
extern: '1'
intvolume: ' 5'
issue: '3'
keyword:
- Topic classification
- URL
- ODP
language:
- iso: eng
month: '07'
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 features and algorithms for URL-based topic classification
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 5
year: '2011'
...
---
_id: '11760'
abstract:
- lang: eng
text: "We study a novel load balancing problem that arises in web search engines.
The problem is a combination of an offline assignment problem, where files need
to be (copied and) assigned to machines, and an online load balancing problem,
where requests ask for specific files and need to be assigned to a corresponding
machine, whose load is increased\r\nby this. We present simple deterministic algorithms
for this problem and exhibit an interesting trade-off between the available space
to make file copies and the obtainable makespan. We also give non-trivial lower
bounds for a large class of deterministic algorithms and present a randomized
algorithm that beats these bounds with high probability."
article_processing_charge: No
article_type: original
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 MH, Weber I. Offline file assignments for online load
balancing. Information Processing Letters. 2011;111(4):178-183. doi:10.1016/j.ipl.2010.11.022
apa: Dütting, P., Henzinger, M. H., & Weber, I. (2011). Offline file assignments
for online load balancing. Information Processing Letters. Elsevier. https://doi.org/10.1016/j.ipl.2010.11.022
chicago: Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Offline File Assignments
for Online Load Balancing.” Information Processing Letters. Elsevier, 2011.
https://doi.org/10.1016/j.ipl.2010.11.022.
ieee: P. Dütting, M. H. Henzinger, and I. Weber, “Offline file assignments for online
load balancing,” Information Processing Letters, vol. 111, no. 4. Elsevier,
pp. 178–183, 2011.
ista: Dütting P, Henzinger MH, Weber I. 2011. Offline file assignments for online
load balancing. Information Processing Letters. 111(4), 178–183.
mla: Dütting, Paul, et al. “Offline File Assignments for Online Load Balancing.”
Information Processing Letters, vol. 111, no. 4, Elsevier, 2011, pp. 178–83,
doi:10.1016/j.ipl.2010.11.022.
short: P. Dütting, M.H. Henzinger, I. Weber, Information Processing Letters 111
(2011) 178–183.
date_created: 2022-08-08T11:33:03Z
date_published: 2011-01-15T00:00:00Z
date_updated: 2022-09-12T09:38:05Z
day: '15'
doi: 10.1016/j.ipl.2010.11.022
extern: '1'
intvolume: ' 111'
issue: '4'
language:
- iso: eng
month: '01'
oa_version: None
page: 178-183
publication: Information Processing Letters
publication_identifier:
issn:
- 0020-0190
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Offline file assignments for online load balancing
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 111
year: '2011'
...
---
_id: '11796'
abstract:
- lang: eng
text: "The design of truthful auctions that approximate the optimal expected revenue
is a central problem in algorithmic mechanism design. 30 years after Myerson’s
characterization of Bayesian optimal auctions in single-parameter domains [8],
characterizing but also providing efficient mechanisms for multi-parameter domains
still remains a very important unsolved problem. Our work improves upon recent
results in this area, introducing new techniques for tackling the problem, while
also combining and extending recently introduced tools.\r\n\r\nIn particular we
give the first approximation algorithms for Bayesian auctions with multiple heterogeneous
items when bidders have additive valuations, budget constraints and general matroid
feasibility constraints."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Angelina
full_name: Vidali, Angelina
last_name: Vidali
citation:
ama: 'Henzinger MH, Vidali A. Multi-parameter mechanism design under budget and
matroid constraints. In: 19th Annual European Symposium on Algorithms.
Vol 6942. Springer Nature; 2011:192–202. doi:10.1007/978-3-642-23719-5_17'
apa: 'Henzinger, M. H., & Vidali, A. (2011). Multi-parameter mechanism design
under budget and matroid constraints. In 19th Annual European Symposium on
Algorithms (Vol. 6942, pp. 192–202). Saarbrücken, Germany: Springer Nature.
https://doi.org/10.1007/978-3-642-23719-5_17'
chicago: Henzinger, Monika H, and Angelina Vidali. “Multi-Parameter Mechanism Design
under Budget and Matroid Constraints.” In 19th Annual European Symposium on
Algorithms, 6942:192–202. Springer Nature, 2011. https://doi.org/10.1007/978-3-642-23719-5_17.
ieee: M. H. Henzinger and A. Vidali, “Multi-parameter mechanism design under budget
and matroid constraints,” in 19th Annual European Symposium on Algorithms,
Saarbrücken, Germany, 2011, vol. 6942, pp. 192–202.
ista: 'Henzinger MH, Vidali A. 2011. Multi-parameter mechanism design under budget
and matroid constraints. 19th Annual European Symposium on Algorithms. ESA: European
Symposium on Algorithms, LNCS, vol. 6942, 192–202.'
mla: Henzinger, Monika H., and Angelina Vidali. “Multi-Parameter Mechanism Design
under Budget and Matroid Constraints.” 19th Annual European Symposium on Algorithms,
vol. 6942, Springer Nature, 2011, pp. 192–202, doi:10.1007/978-3-642-23719-5_17.
short: M.H. Henzinger, A. Vidali, in:, 19th Annual European Symposium on Algorithms,
Springer Nature, 2011, pp. 192–202.
conference:
end_date: 2011-09-09
location: Saarbrücken, Germany
name: 'ESA: European Symposium on Algorithms'
start_date: 2011-09-05
date_created: 2022-08-11T11:51:39Z
date_published: 2011-09-01T00:00:00Z
date_updated: 2023-02-13T11:32:41Z
day: '01'
doi: 10.1007/978-3-642-23719-5_17
extern: '1'
intvolume: ' 6942'
language:
- iso: eng
month: '09'
oa_version: None
page: 192–202
publication: 19th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783642237188'
issn:
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Multi-parameter mechanism design under budget and matroid constraints
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6942
year: '2011'
...