---
_id: '14735'
abstract:
- lang: eng
text: "Scaling blockchain protocols to perform on par with the expected needs of
Web3.0 has been proven to be a challenging task with almost a decade of research.
In the forefront of the current solution is the idea of separating the execution
of the updates encoded in a block from the ordering of blocks. In order to achieve
this, a new class of protocols called rollups has emerged. Rollups have as input
a total ordering of valid and invalid transactions and as output a new valid state-transition.\r\nIf
we study rollups from a distributed computing perspective, we uncover that rollups
take as input the output of a Byzantine Atomic Broadcast (BAB) protocol and convert
it to a State Machine Replication (SMR) protocol. BAB and SMR, however, are considered
equivalent as far as distributed computing is concerned and a solution to one
can easily be retrofitted to solve the other simply by adding/removing an execution
step before the validation of the input.\r\nThis “easy” step of retrofitting an
atomic broadcast solution to implement an SMR has, however, been overlooked in
practice. In this paper, we formalize the problem and show that after BAB is solved,
traditional impossibility results for consensus no longer apply towards an SMR.
Leveraging this we propose a distributed execution protocol that allows reduced
execution and storage cost per executor (O(log2n/n)) without relaxing the network
assumptions of the underlying BAB protocol and providing censorship-resistance.
Finally, we propose efficient non-interactive light client constructions that
leverage our efficient execution protocols and do not require any synchrony assumptions
or expensive ZK-proofs."
acknowledgement: 'Eleftherios Kokoris-Kogias is partially supported by Austrian Science
Fund (FWF) grant No: F8512-N.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Christos
full_name: Stefo, Christos
id: a20e8902-32b0-11ee-9fa8-b23fa638b793
last_name: Stefo
- first_name: Zhuolun
full_name: Xiang, Zhuolun
last_name: Xiang
- first_name: Eleftherios
full_name: Kokoris Kogias, Eleftherios
id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
last_name: Kokoris Kogias
citation:
ama: 'Stefo C, Xiang Z, Kokoris Kogias E. Executing and proving over dirty ledgers.
In: 27th International Conference on Financial Cryptography and Data Security.
Vol 13950. Springer Nature; 2023:3-20. doi:10.1007/978-3-031-47754-6_1'
apa: 'Stefo, C., Xiang, Z., & Kokoris Kogias, E. (2023). Executing and proving
over dirty ledgers. In 27th International Conference on Financial Cryptography
and Data Security (Vol. 13950, pp. 3–20). Bol, Brac, Croatia: Springer Nature.
https://doi.org/10.1007/978-3-031-47754-6_1'
chicago: Stefo, Christos, Zhuolun Xiang, and Eleftherios Kokoris Kogias. “Executing
and Proving over Dirty Ledgers.” In 27th International Conference on Financial
Cryptography and Data Security, 13950:3–20. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-47754-6_1.
ieee: C. Stefo, Z. Xiang, and E. Kokoris Kogias, “Executing and proving over dirty
ledgers,” in 27th International Conference on Financial Cryptography and Data
Security, Bol, Brac, Croatia, 2023, vol. 13950, pp. 3–20.
ista: 'Stefo C, Xiang Z, Kokoris Kogias E. 2023. Executing and proving over dirty
ledgers. 27th International Conference on Financial Cryptography and Data Security.
FC: Financial Cryptography and Data Security, LNCS, vol. 13950, 3–20.'
mla: Stefo, Christos, et al. “Executing and Proving over Dirty Ledgers.” 27th
International Conference on Financial Cryptography and Data Security, vol.
13950, Springer Nature, 2023, pp. 3–20, doi:10.1007/978-3-031-47754-6_1.
short: C. Stefo, Z. Xiang, E. Kokoris Kogias, in:, 27th International Conference
on Financial Cryptography and Data Security, Springer Nature, 2023, pp. 3–20.
conference:
end_date: 2023-05-05
location: Bol, Brac, Croatia
name: 'FC: Financial Cryptography and Data Security'
start_date: 2023-05-01
date_created: 2024-01-08T09:17:38Z
date_published: 2023-12-01T00:00:00Z
date_updated: 2024-01-08T09:28:14Z
day: '01'
department:
- _id: ElKo
- _id: GradSch
doi: 10.1007/978-3-031-47754-6_1
intvolume: ' 13950'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2022/1554
month: '12'
oa: 1
oa_version: Preprint
page: 3-20
project:
- _id: 34a4ce89-11ca-11ed-8bc3-8cc37fb6e11f
grant_number: F8512
name: Secure Network and Hardware for Efficient Blockchains
publication: 27th International Conference on Financial Cryptography and Data Security
publication_identifier:
eisbn:
- '9783031477546'
eissn:
- 0302-9743
isbn:
- '9783031477539'
issn:
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Executing and proving over dirty ledgers
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13950
year: '2023'
...
---
_id: '6726'
abstract:
- lang: eng
text: Randomness is an essential part of any secure cryptosystem, but many constructions
rely on distributions that are not uniform. This is particularly true for lattice
based cryptosystems, which more often than not make use of discrete Gaussian distributions
over the integers. For practical purposes it is crucial to evaluate the impact
that approximation errors have on the security of a scheme to provide the best
possible trade-off between security and performance. Recent years have seen surprising
results allowing to use relatively low precision while maintaining high levels
of security. A key insight in these results is that sampling a distribution with
low relative error can provide very strong security guarantees. Since floating
point numbers provide guarantees on the relative approximation error, they seem
a suitable tool in this setting, but it is not obvious which sampling algorithms
can actually profit from them. While previous works have shown that inversion
sampling can be adapted to provide a low relative error (Pöppelmann et al., CHES
2014; Prest, ASIACRYPT 2017), other works have called into question if this is
possible for other sampling techniques (Zheng et al., Eprint report 2018/309).
In this work, we consider all sampling algorithms that are popular in the cryptographic
setting and analyze the relationship of floating point precision and the resulting
relative error. We show that all of the algorithms either natively achieve a low
relative error or can be adapted to do so.
article_processing_charge: No
author:
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Walter M. Sampling the integers with low relative error. In: Buchmann J, Nitaj
A, Rachidi T, eds. Progress in Cryptology – AFRICACRYPT 2019. Vol 11627.
LNCS. Cham: Springer Nature; 2019:157-180. doi:10.1007/978-3-030-23696-0_9'
apa: 'Walter, M. (2019). Sampling the integers with low relative error. In J. Buchmann,
A. Nitaj, & T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019
(Vol. 11627, pp. 157–180). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-23696-0_9'
chicago: 'Walter, Michael. “Sampling the Integers with Low Relative Error.” In Progress
in Cryptology – AFRICACRYPT 2019, edited by J Buchmann, A Nitaj, and T Rachidi,
11627:157–80. LNCS. Cham: Springer Nature, 2019. https://doi.org/10.1007/978-3-030-23696-0_9.'
ieee: 'M. Walter, “Sampling the integers with low relative error,” in Progress
in Cryptology – AFRICACRYPT 2019, vol. 11627, J. Buchmann, A. Nitaj, and T.
Rachidi, Eds. Cham: Springer Nature, 2019, pp. 157–180.'
ista: 'Walter M. 2019.Sampling the integers with low relative error. In: Progress
in Cryptology – AFRICACRYPT 2019. vol. 11627, 157–180.'
mla: Walter, Michael. “Sampling the Integers with Low Relative Error.” Progress
in Cryptology – AFRICACRYPT 2019, edited by J Buchmann et al., vol. 11627,
Springer Nature, 2019, pp. 157–80, doi:10.1007/978-3-030-23696-0_9.
short: M. Walter, in:, J. Buchmann, A. Nitaj, T. Rachidi (Eds.), Progress in Cryptology
– AFRICACRYPT 2019, Springer Nature, Cham, 2019, pp. 157–180.
conference:
end_date: 2019-07-11
location: Rabat, Morocco
name: 'AFRICACRYPT: International Conference on Cryptology in Africa'
start_date: 2019-07-09
date_created: 2019-07-29T12:25:31Z
date_published: 2019-06-29T00:00:00Z
date_updated: 2023-02-23T12:50:15Z
day: '29'
department:
- _id: KrPi
doi: 10.1007/978-3-030-23696-0_9
ec_funded: 1
editor:
- first_name: J
full_name: Buchmann, J
last_name: Buchmann
- first_name: A
full_name: Nitaj, A
last_name: Nitaj
- first_name: T
full_name: Rachidi, T
last_name: Rachidi
intvolume: ' 11627'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/068
month: '06'
oa: 1
oa_version: Preprint
page: 157-180
place: Cham
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Progress in Cryptology – AFRICACRYPT 2019
publication_identifier:
eisbn:
- 978-3-0302-3696-0
isbn:
- 978-3-0302-3695-3
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: Sampling the integers with low relative error
type: book_chapter
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 11627
year: '2019'
...
---
_id: '7453'
abstract:
- lang: eng
text: We illustrate the ingredients of the state-of-the-art of model-based approach
for the formal design and verification of cyber-physical systems. To capture the
interaction between a discrete controller and its continuously evolving environment,
we use the formal models of timed and hybrid automata. We explain the steps of
modeling and verification in the tools Uppaal and SpaceEx using a case study based
on a dual-chamber implantable pacemaker monitoring a human heart. We show how
to design a model as a composition of components, how to construct models at varying
levels of detail, how to establish that one model is an abstraction of another,
how to specify correctness requirements using temporal logic, and how to verify
that a model satisfies a logical requirement.
acknowledgement: This research was supported in part by the Austrian Science Fund
(FWF) under grants S11402-N23(RiSE/SHiNE) and Z211-N23 (Wittgenstein Award). This
research has received funding from the Sino-Danish Basic Research Centre, IDEA4CPS,
funded by the Danish National Research Foundation and the National Science Foundation,
China, the Innovation Fund Denmark centre DiCyPS, as well as the ERC Advanced Grant
LASSO.
alternative_title:
- Lecture Notes in Computer Science
article_processing_charge: No
author:
- first_name: Rajeev
full_name: Alur, Rajeev
last_name: Alur
- first_name: Mirco
full_name: Giacobbe, Mirco
id: 3444EA5E-F248-11E8-B48F-1D18A9856A87
last_name: Giacobbe
orcid: 0000-0001-8180-0904
- 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: Kim G.
full_name: Larsen, Kim G.
last_name: Larsen
- first_name: Marius
full_name: Mikučionis, Marius
last_name: Mikučionis
citation:
ama: 'Alur R, Giacobbe M, Henzinger TA, Larsen KG, Mikučionis M. Continuous-time
models for system design and analysis. In: Steffen B, Woeginger G, eds. Computing
and Software Science. Vol 10000. LNCS. Springer Nature; 2019:452-477. doi:10.1007/978-3-319-91908-9_22'
apa: Alur, R., Giacobbe, M., Henzinger, T. A., Larsen, K. G., & Mikučionis,
M. (2019). Continuous-time models for system design and analysis. In B. Steffen
& G. Woeginger (Eds.), Computing and Software Science (Vol. 10000,
pp. 452–477). Springer Nature. https://doi.org/10.1007/978-3-319-91908-9_22
chicago: Alur, Rajeev, Mirco Giacobbe, Thomas A Henzinger, Kim G. Larsen, and Marius
Mikučionis. “Continuous-Time Models for System Design and Analysis.” In Computing
and Software Science, edited by Bernhard Steffen and Gerhard Woeginger, 10000:452–77.
LNCS. Springer Nature, 2019. https://doi.org/10.1007/978-3-319-91908-9_22.
ieee: R. Alur, M. Giacobbe, T. A. Henzinger, K. G. Larsen, and M. Mikučionis, “Continuous-time
models for system design and analysis,” in Computing and Software Science,
vol. 10000, B. Steffen and G. Woeginger, Eds. Springer Nature, 2019, pp. 452–477.
ista: 'Alur R, Giacobbe M, Henzinger TA, Larsen KG, Mikučionis M. 2019.Continuous-time
models for system design and analysis. In: Computing and Software Science. Lecture
Notes in Computer Science, vol. 10000, 452–477.'
mla: Alur, Rajeev, et al. “Continuous-Time Models for System Design and Analysis.”
Computing and Software Science, edited by Bernhard Steffen and Gerhard
Woeginger, vol. 10000, Springer Nature, 2019, pp. 452–77, doi:10.1007/978-3-319-91908-9_22.
short: R. Alur, M. Giacobbe, T.A. Henzinger, K.G. Larsen, M. Mikučionis, in:, B.
Steffen, G. Woeginger (Eds.), Computing and Software Science, Springer Nature,
2019, pp. 452–477.
date_created: 2020-02-05T10:51:44Z
date_published: 2019-10-05T00:00:00Z
date_updated: 2022-09-06T08:25:52Z
day: '05'
department:
- _id: ToHe
doi: 10.1007/978-3-319-91908-9_22
editor:
- first_name: Bernhard
full_name: Steffen, Bernhard
last_name: Steffen
- first_name: Gerhard
full_name: Woeginger, Gerhard
last_name: Woeginger
intvolume: ' 10000'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1007/978-3-319-91908-9_22
month: '10'
oa: 1
oa_version: Published Version
page: 452-477
project:
- _id: 25F2ACDE-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: The Wittgenstein Prize
publication: Computing and Software Science
publication_identifier:
eisbn:
- '9783319919089'
eissn:
- 0302-9743
isbn:
- '9783319919072'
issn:
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: Continuous-time models for system design and analysis
type: book_chapter
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10000
year: '2019'
...
---
_id: '6163'
abstract:
- lang: eng
text: We propose a new non-orthogonal basis to express the 3D Euclidean space in
terms of a regular grid. Every grid point, each represented by integer 3-coordinates,
corresponds to rhombic dodecahedron centroid. Rhombic dodecahedron is a space
filling polyhedron which represents the close packing of spheres in 3D space and
the Voronoi structures of the face centered cubic (FCC) lattice. In order to illustrate
the interest of the new coordinate system, we propose the characterization of
3D digital plane with its topological features, such as the interrelation between
the thickness of the digital plane and the separability constraint we aim to obtain.
A characterization of a 3D digital sphere with relevant topological features is
proposed as well with the help of a 48 symmetry that comes with the new coordinate
system.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Ranita
full_name: Biswas, Ranita
id: 3C2B033E-F248-11E8-B48F-1D18A9856A87
last_name: Biswas
orcid: 0000-0002-5372-7890
- first_name: Gaëlle
full_name: Largeteau-Skapin, Gaëlle
last_name: Largeteau-Skapin
- first_name: Rita
full_name: Zrour, Rita
last_name: Zrour
- first_name: Eric
full_name: Andres, Eric
last_name: Andres
citation:
ama: 'Biswas R, Largeteau-Skapin G, Zrour R, Andres E. Rhombic dodecahedron grid—coordinate
system and 3D digital object definitions. In: 21st IAPR International Conference
on Discrete Geometry for Computer Imagery. Vol 11414. Berlin, Heidelberg:
Springer Berlin Heidelberg; 2019:27-37. doi:10.1007/978-3-030-14085-4_3'
apa: 'Biswas, R., Largeteau-Skapin, G., Zrour, R., & Andres, E. (2019). Rhombic
dodecahedron grid—coordinate system and 3D digital object definitions. In 21st
IAPR International Conference on Discrete Geometry for Computer Imagery (Vol.
11414, pp. 27–37). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-030-14085-4_3'
chicago: 'Biswas, Ranita, Gaëlle Largeteau-Skapin, Rita Zrour, and Eric Andres.
“Rhombic Dodecahedron Grid—Coordinate System and 3D Digital Object Definitions.”
In 21st IAPR International Conference on Discrete Geometry for Computer Imagery,
11414:27–37. Berlin, Heidelberg: Springer Berlin Heidelberg, 2019. https://doi.org/10.1007/978-3-030-14085-4_3.'
ieee: R. Biswas, G. Largeteau-Skapin, R. Zrour, and E. Andres, “Rhombic dodecahedron
grid—coordinate system and 3D digital object definitions,” in 21st IAPR International
Conference on Discrete Geometry for Computer Imagery, Marne-la-Vallée, France,
2019, vol. 11414, pp. 27–37.
ista: 'Biswas R, Largeteau-Skapin G, Zrour R, Andres E. 2019. Rhombic dodecahedron
grid—coordinate system and 3D digital object definitions. 21st IAPR International
Conference on Discrete Geometry for Computer Imagery. DGCI: International Conference
on Discrete Geometry for Computer Imagery, LNCS, vol. 11414, 27–37.'
mla: Biswas, Ranita, et al. “Rhombic Dodecahedron Grid—Coordinate System and 3D
Digital Object Definitions.” 21st IAPR International Conference on Discrete
Geometry for Computer Imagery, vol. 11414, Springer Berlin Heidelberg, 2019,
pp. 27–37, doi:10.1007/978-3-030-14085-4_3.
short: R. Biswas, G. Largeteau-Skapin, R. Zrour, E. Andres, in:, 21st IAPR International
Conference on Discrete Geometry for Computer Imagery, Springer Berlin Heidelberg,
Berlin, Heidelberg, 2019, pp. 27–37.
conference:
end_date: 2019-03-28
location: Marne-la-Vallée, France
name: 'DGCI: International Conference on Discrete Geometry for Computer Imagery'
start_date: 2019-03-26
date_created: 2019-03-21T12:12:19Z
date_published: 2019-02-23T00:00:00Z
date_updated: 2022-01-27T14:25:17Z
day: '23'
doi: 10.1007/978-3-030-14085-4_3
extern: '1'
intvolume: ' 11414'
language:
- iso: eng
month: '02'
oa_version: None
page: 27-37
place: Berlin, Heidelberg
publication: 21st IAPR International Conference on Discrete Geometry for Computer
Imagery
publication_identifier:
isbn:
- 978-3-6624-6446-5
- 978-3-6624-6447-2
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer Berlin Heidelberg
quality_controlled: '1'
status: public
title: Rhombic dodecahedron grid—coordinate system and 3D digital object definitions
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 11414
year: '2019'
...
---
_id: '8298'
abstract:
- lang: eng
text: Sharding, or partitioning the system’s state so that different subsets of
participants handle it, is a proven approach to building distributed systems whose
total capacity scales horizontally with the number of participants. Many distributed
ledgers have adopted this approach to increase their performance, however, they
focus on the permissionless setting that assumes the existence of a strong adversary.
In this paper, we deploy channels for permissioned blockchains. Our first contribution
is to adapt sharding on asset-management applications for the permissioned setting,
while preserving liveness and safety even on transactions spanning across-channels.
Our second contribution is to leverage channels as a confidentiality boundary,
enabling different organizations and consortia to preserve their privacy within
their channels and still be part of a bigger collaborative ecosystem. To make
our system concrete we map it on top of Hyperledger Fabric.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Elli
full_name: Androulaki, Elli
last_name: Androulaki
- first_name: Christian
full_name: Cachin, Christian
last_name: Cachin
- first_name: Angelo
full_name: De Caro, Angelo
last_name: De Caro
- first_name: Eleftherios
full_name: Kokoris Kogias, Eleftherios
id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
last_name: Kokoris Kogias
citation:
ama: 'Androulaki E, Cachin C, De Caro A, Kokoris Kogias E. Channels: Horizontal
scaling and confidentiality on permissioned blockchains. In: Computer Security.
Vol 11098. Springer Nature; 2018:111-131. doi:10.1007/978-3-319-99073-6_6'
apa: 'Androulaki, E., Cachin, C., De Caro, A., & Kokoris Kogias, E. (2018).
Channels: Horizontal scaling and confidentiality on permissioned blockchains.
In Computer Security (Vol. 11098, pp. 111–131). Barcelona, Spain: Springer
Nature. https://doi.org/10.1007/978-3-319-99073-6_6'
chicago: 'Androulaki, Elli, Christian Cachin, Angelo De Caro, and Eleftherios Kokoris
Kogias. “Channels: Horizontal Scaling and Confidentiality on Permissioned Blockchains.”
In Computer Security, 11098:111–31. Springer Nature, 2018. https://doi.org/10.1007/978-3-319-99073-6_6.'
ieee: 'E. Androulaki, C. Cachin, A. De Caro, and E. Kokoris Kogias, “Channels: Horizontal
scaling and confidentiality on permissioned blockchains,” in Computer Security,
Barcelona, Spain, 2018, vol. 11098, pp. 111–131.'
ista: 'Androulaki E, Cachin C, De Caro A, Kokoris Kogias E. 2018. Channels: Horizontal
scaling and confidentiality on permissioned blockchains. Computer Security. ESORICS:
European Symposium on Research in Computer Security, LNCS, vol. 11098, 111–131.'
mla: 'Androulaki, Elli, et al. “Channels: Horizontal Scaling and Confidentiality
on Permissioned Blockchains.” Computer Security, vol. 11098, Springer Nature,
2018, pp. 111–31, doi:10.1007/978-3-319-99073-6_6.'
short: E. Androulaki, C. Cachin, A. De Caro, E. Kokoris Kogias, in:, Computer Security,
Springer Nature, 2018, pp. 111–131.
conference:
end_date: 2018-09-07
location: Barcelona, Spain
name: 'ESORICS: European Symposium on Research in Computer Security'
start_date: 2018-09-03
date_created: 2020-08-26T11:47:34Z
date_published: 2018-08-08T00:00:00Z
date_updated: 2021-01-12T08:17:57Z
day: '08'
doi: 10.1007/978-3-319-99073-6_6
extern: '1'
intvolume: ' 11098'
language:
- iso: eng
month: '08'
oa_version: None
page: 111-131
publication: Computer Security
publication_identifier:
eisbn:
- '9783319990736'
isbn:
- '9783319990729'
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: 'Channels: Horizontal scaling and confidentiality on permissioned blockchains'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 11098
year: '2018'
...
---
_id: '5803'
abstract:
- lang: eng
text: Different distance metrics produce Voronoi diagrams with different properties.
It is a well-known that on the (real) 2D plane or even on any 3D plane, a Voronoi
diagram (VD) based on the Euclidean distance metric produces convex Voronoi regions.
In this paper, we first show that this metric produces a persistent VD on the
2D digital plane, as it comprises digitally convex Voronoi regions and hence correctly
approximates the corresponding VD on the 2D real plane. Next, we show that on
a 3D digital plane D, the Euclidean metric spanning over its voxel set does not
guarantee a digital VD which is persistent with the real-space VD. As a solution,
we introduce a novel concept of functional-plane-convexity, which is ensured by
the Euclidean metric spanning over the pedal set of D. Necessary proofs and some
visual result have been provided to adjudge the merit and usefulness of the proposed
concept.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Ranita
full_name: Biswas, Ranita
id: 3C2B033E-F248-11E8-B48F-1D18A9856A87
last_name: Biswas
orcid: 0000-0002-5372-7890
- first_name: Partha
full_name: Bhowmick, Partha
last_name: Bhowmick
citation:
ama: 'Biswas R, Bhowmick P. Construction of persistent Voronoi diagram on 3D digital
plane. In: Combinatorial Image Analysis. Vol 10256. Cham: Springer Nature;
2017:93-104. doi:10.1007/978-3-319-59108-7_8'
apa: 'Biswas, R., & Bhowmick, P. (2017). Construction of persistent Voronoi
diagram on 3D digital plane. In Combinatorial image analysis (Vol. 10256,
pp. 93–104). Cham: Springer Nature. https://doi.org/10.1007/978-3-319-59108-7_8'
chicago: 'Biswas, Ranita, and Partha Bhowmick. “Construction of Persistent Voronoi
Diagram on 3D Digital Plane.” In Combinatorial Image Analysis, 10256:93–104.
Cham: Springer Nature, 2017. https://doi.org/10.1007/978-3-319-59108-7_8.'
ieee: 'R. Biswas and P. Bhowmick, “Construction of persistent Voronoi diagram on
3D digital plane,” in Combinatorial image analysis, vol. 10256, Cham: Springer
Nature, 2017, pp. 93–104.'
ista: 'Biswas R, Bhowmick P. 2017.Construction of persistent Voronoi diagram on
3D digital plane. In: Combinatorial image analysis. LNCS, vol. 10256, 93–104.'
mla: Biswas, Ranita, and Partha Bhowmick. “Construction of Persistent Voronoi Diagram
on 3D Digital Plane.” Combinatorial Image Analysis, vol. 10256, Springer
Nature, 2017, pp. 93–104, doi:10.1007/978-3-319-59108-7_8.
short: R. Biswas, P. Bhowmick, in:, Combinatorial Image Analysis, Springer Nature,
Cham, 2017, pp. 93–104.
conference:
end_date: 2017-06-21
location: Plovdiv, Bulgaria
name: 'IWCIA: International Workshop on Combinatorial Image Analysis'
start_date: 2017-06-19
date_created: 2019-01-08T20:42:56Z
date_published: 2017-05-17T00:00:00Z
date_updated: 2022-01-28T07:48:24Z
day: '17'
department:
- _id: HeEd
doi: 10.1007/978-3-319-59108-7_8
extern: '1'
intvolume: ' 10256'
language:
- iso: eng
month: '05'
oa_version: None
page: 93-104
place: Cham
publication: Combinatorial image analysis
publication_identifier:
isbn:
- 978-3-319-59107-0
- 978-3-319-59108-7
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: Construction of persistent Voronoi diagram on 3D digital plane
type: book_chapter
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 10256
year: '2017'
...
---
_id: '12571'
abstract:
- lang: eng
text: We consider the problems of maintaining approximate maximum matching and minimum
vertex cover in a dynamic graph. Starting with the seminal work of Onak and Rubinfeld
[STOC 2010], this problem has received significant attention in recent years.
Very recently, extending the framework of Baswana, Gupta and Sen [FOCS 2011],
Solomon [FOCS 2016] gave a randomized 2-approximation dynamic algorithm for this
problem that has amortized update time of O(1) with high probability. We consider
the natural open question of derandomizing this result. We present a new deterministic
fully dynamic algorithm that maintains a O(1)-approximate minimum vertex cover
and maximum fractional matching, with an amortized update time of O(1). Previously,
the best deterministic algorithm for this problem was due to Bhattacharya, Henzinger
and Italiano [SODA 2015]; it had an approximation ratio of (2+ϵ) and an amortized
update time of O(logn/ϵ2). Our result can be generalized to give a fully dynamic
O(f3)-approximation algorithm with O(f2) amortized update time for the hypergraph
vertex cover and fractional matching problems, where every hyperedge has at most
f vertices.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Sayan
full_name: Bhattacharya, Sayan
last_name: Bhattacharya
- first_name: Deeparnab
full_name: Chakrabarty, Deeparnab
last_name: Chakrabarty
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'Bhattacharya S, Chakrabarty D, Henzinger MH. Deterministic fully dynamic approximate
vertex cover and fractional matching in O(1) amortized update time. In: 19th
International Conference on Integer Programming and Combinatorial Optimization.
Vol 10328. Springer Nature; 2017:86-98. doi:10.1007/978-3-319-59250-3_8'
apa: 'Bhattacharya, S., Chakrabarty, D., & Henzinger, M. H. (2017). Deterministic
fully dynamic approximate vertex cover and fractional matching in O(1) amortized
update time. In 19th International Conference on Integer Programming and Combinatorial
Optimization (Vol. 10328, pp. 86–98). Waterloo, ON, Canada: Springer Nature.
https://doi.org/10.1007/978-3-319-59250-3_8'
chicago: Bhattacharya, Sayan, Deeparnab Chakrabarty, and Monika H Henzinger. “Deterministic
Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized
Update Time.” In 19th International Conference on Integer Programming and Combinatorial
Optimization, 10328:86–98. Springer Nature, 2017. https://doi.org/10.1007/978-3-319-59250-3_8.
ieee: S. Bhattacharya, D. Chakrabarty, and M. H. Henzinger, “Deterministic fully
dynamic approximate vertex cover and fractional matching in O(1) amortized update
time,” in 19th International Conference on Integer Programming and Combinatorial
Optimization, Waterloo, ON, Canada, 2017, vol. 10328, pp. 86–98.
ista: 'Bhattacharya S, Chakrabarty D, Henzinger MH. 2017. Deterministic fully dynamic
approximate vertex cover and fractional matching in O(1) amortized update time.
19th International Conference on Integer Programming and Combinatorial Optimization.
IPCO: Integer Programming and Combinatorial Optimization, LNCS, vol. 10328, 86–98.'
mla: Bhattacharya, Sayan, et al. “Deterministic Fully Dynamic Approximate Vertex
Cover and Fractional Matching in O(1) Amortized Update Time.” 19th International
Conference on Integer Programming and Combinatorial Optimization, vol. 10328,
Springer Nature, 2017, pp. 86–98, doi:10.1007/978-3-319-59250-3_8.
short: S. Bhattacharya, D. Chakrabarty, M.H. Henzinger, in:, 19th International
Conference on Integer Programming and Combinatorial Optimization, Springer Nature,
2017, pp. 86–98.
conference:
end_date: 2017-06-28
location: Waterloo, ON, Canada
name: 'IPCO: Integer Programming and Combinatorial Optimization'
start_date: 2017-06-26
date_created: 2023-02-20T07:52:31Z
date_published: 2017-05-24T00:00:00Z
date_updated: 2023-02-20T07:57:24Z
day: '24'
doi: 10.1007/978-3-319-59250-3_8
extern: '1'
external_id:
arxiv:
- '1611.00198'
intvolume: ' 10328'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1611.00198
month: '05'
oa: 1
oa_version: Preprint
page: 86-98
publication: 19th International Conference on Integer Programming and Combinatorial
Optimization
publication_identifier:
eisbn:
- '9783319592503'
isbn:
- '9783319592497'
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Deterministic fully dynamic approximate vertex cover and fractional matching
in O(1) amortized update time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10328
year: '2017'
...
---
_id: '5806'
abstract:
- lang: eng
text: Although the concept of functional plane for naive plane is studied and reported
in the literature in great detail, no similar study is yet found for naive sphere.
This article exposes the first study in this line, opening up further prospects
of analyzing the topological properties of sphere in the discrete space. We show
that each quadraginta octant Q of a naive sphere forms a bijection with its projected
pixel set on a unique coordinate plane, which thereby serves as the functional
plane of Q, and hence gives rise to merely mono-jumps during back projection.
The other two coordinate planes serve as para-functional and dia-functional planes
for Q, as the former is ‘mono-jumping’ but not bijective, whereas the latter holds
neither of the two. Owing to this, the quadraginta octants form symmetry groups
and subgroups with equivalent jump conditions. We also show a potential application
in generating a special class of discrete 3D circles based on back projection
and jump bridging by Steiner voxels. A circle in this class possesses 4-symmetry,
uniqueness, and bounded distance from the underlying real sphere and real plane.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Ranita
full_name: Biswas, Ranita
id: 3C2B033E-F248-11E8-B48F-1D18A9856A87
last_name: Biswas
orcid: 0000-0002-5372-7890
- first_name: Partha
full_name: Bhowmick, Partha
last_name: Bhowmick
citation:
ama: 'Biswas R, Bhowmick P. On functionality of quadraginta octants of naive sphere
with application to circle drawing. In: Discrete Geometry for Computer Imagery.
Vol 9647. Cham: Springer Nature; 2016:256-267. doi:10.1007/978-3-319-32360-2_20'
apa: 'Biswas, R., & Bhowmick, P. (2016). On functionality of quadraginta octants
of naive sphere with application to circle drawing. In Discrete Geometry for
Computer Imagery (Vol. 9647, pp. 256–267). Cham: Springer Nature. https://doi.org/10.1007/978-3-319-32360-2_20'
chicago: 'Biswas, Ranita, and Partha Bhowmick. “On Functionality of Quadraginta
Octants of Naive Sphere with Application to Circle Drawing.” In Discrete Geometry
for Computer Imagery, 9647:256–67. Cham: Springer Nature, 2016. https://doi.org/10.1007/978-3-319-32360-2_20.'
ieee: R. Biswas and P. Bhowmick, “On functionality of quadraginta octants of naive
sphere with application to circle drawing,” in Discrete Geometry for Computer
Imagery, Nantes, France, 2016, vol. 9647, pp. 256–267.
ista: 'Biswas R, Bhowmick P. 2016. On functionality of quadraginta octants of naive
sphere with application to circle drawing. Discrete Geometry for Computer Imagery.
DGCI: International Conference on Discrete Geometry for Computer Imagery, LNCS,
vol. 9647, 256–267.'
mla: Biswas, Ranita, and Partha Bhowmick. “On Functionality of Quadraginta Octants
of Naive Sphere with Application to Circle Drawing.” Discrete Geometry for
Computer Imagery, vol. 9647, Springer Nature, 2016, pp. 256–67, doi:10.1007/978-3-319-32360-2_20.
short: R. Biswas, P. Bhowmick, in:, Discrete Geometry for Computer Imagery, Springer
Nature, Cham, 2016, pp. 256–267.
conference:
end_date: 2016-04-20
location: Nantes, France
name: 'DGCI: International Conference on Discrete Geometry for Computer Imagery'
start_date: 2016-04-18
date_created: 2019-01-08T20:44:37Z
date_published: 2016-04-09T00:00:00Z
date_updated: 2022-01-28T08:10:11Z
day: '09'
department:
- _id: HeEd
doi: 10.1007/978-3-319-32360-2_20
extern: '1'
intvolume: ' 9647'
language:
- iso: eng
month: '04'
oa_version: None
page: 256-267
place: Cham
publication: Discrete Geometry for Computer Imagery
publication_identifier:
eisbn:
- 978-3-319-32360-2
isbn:
- 978-3-319-32359-6
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: On functionality of quadraginta octants of naive sphere with application to
circle drawing
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 9647
year: '2016'
...
---
_id: '5810'
abstract:
- lang: eng
text: A discrete spherical geodesic path between two voxels s and t lying on a discrete
sphere is a/the 1-connected shortest path from s to t, comprising voxels of the
discrete sphere intersected by the real plane passing through s, t, and the center
of the sphere. We show that the set of sphere voxels intersected by the aforesaid
real plane always contains a 1-connected cycle passing through s and t, and each
voxel in this set lies within an isothetic distance of 32 from the concerned plane.
Hence, to compute the path, the algorithm starts from s, and iteratively computes
each voxel p of the path from the predecessor of p. A novel number-theoretic property
and the 48-symmetry of discrete sphere are used for searching the 1-connected
voxels comprising the path. The algorithm is output-sensitive, having its time
and space complexities both linear in the length of the path. It can be extended
for constructing 1-connected discrete 3D circles of arbitrary orientations, specified
by a few appropriate input parameters. Experimental results and related analysis
demonstrate its efficiency and versatility.
author:
- first_name: Ranita
full_name: Biswas, Ranita
id: 3C2B033E-F248-11E8-B48F-1D18A9856A87
last_name: Biswas
orcid: 0000-0002-5372-7890
- first_name: Partha
full_name: Bhowmick, Partha
last_name: Bhowmick
citation:
ama: Biswas R, Bhowmick P. On Finding Spherical Geodesic Paths and Circles in ℤ3.
2014;8668:396-409. doi:10.1007/978-3-319-09955-2_33
apa: 'Biswas, R., & Bhowmick, P. (2014). On Finding Spherical Geodesic Paths
and Circles in ℤ3. Presented at the DGCI: International Conference on Discrete
Geometry for Computer Imagery, Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-319-09955-2_33'
chicago: 'Biswas, Ranita, and Partha Bhowmick. “On Finding Spherical Geodesic Paths
and Circles in ℤ3.” Lecture Notes in Computer Science. Berlin, Heidelberg: Springer,
2014. https://doi.org/10.1007/978-3-319-09955-2_33.'
ieee: R. Biswas and P. Bhowmick, “On Finding Spherical Geodesic Paths and Circles
in ℤ3,” vol. 8668. Springer, Berlin, Heidelberg, pp. 396–409, 2014.
ista: Biswas R, Bhowmick P. 2014. On Finding Spherical Geodesic Paths and Circles
in ℤ3. 8668, 396–409.
mla: Biswas, Ranita, and Partha Bhowmick. On Finding Spherical Geodesic Paths
and Circles in ℤ3. Vol. 8668, Springer, 2014, pp. 396–409, doi:10.1007/978-3-319-09955-2_33.
short: R. Biswas, P. Bhowmick, 8668 (2014) 396–409.
conference:
end_date: 2014-09-12
location: Siena, Italy
name: 'DGCI: International Conference on Discrete Geometry for Computer Imagery'
start_date: 2014-09-10
date_created: 2019-01-08T20:45:32Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2019-01-24T13:22:49Z
doi: 10.1007/978-3-319-09955-2_33
extern: '1'
intvolume: ' 8668'
language:
- iso: eng
oa_version: None
page: 396-409
place: Berlin, Heidelberg
publication_identifier:
isbn:
- '9783642387081'
- '9783642387098'
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer
quality_controlled: '1'
series_title: Lecture Notes in Computer Science
status: public
title: On Finding Spherical Geodesic Paths and Circles in ℤ3
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8668
year: '2014'
...
---
_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 MH, 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. H., & 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 H 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. H. 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 MH, 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.H. 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: 2023-02-13T11:20:42Z
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 MH, 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. H., & 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 H 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. H. 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 MH, 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.H. 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: 2023-02-21T16:28:24Z
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 MH, 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. H., 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 H, 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. H. 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 MH, 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 H., 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.H. 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: 2023-02-21T16:28:26Z
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: '10904'
abstract:
- lang: eng
text: Multi-dimensional mean-payoff and energy games provide the mathematical foundation
for the quantitative study of reactive systems, and play a central role in the
emerging quantitative theory of verification and synthesis. In this work, we study
the strategy synthesis problem for games with such multi-dimensional objectives
along with a parity condition, a canonical way to express ω-regular conditions.
While in general, the winning strategies in such games may require infinite memory,
for synthesis the most relevant problem is the construction of a finite-memory
winning strategy (if one exists). Our main contributions are as follows. First,
we show a tight exponential bound (matching upper and lower bounds) on the memory
required for finite-memory winning strategies in both multi-dimensional mean-payoff
and energy games along with parity objectives. This significantly improves the
triple exponential upper bound for multi energy games (without parity) that could
be derived from results in literature for games on VASS (vector addition systems
with states). Second, we present an optimal symbolic and incremental algorithm
to compute a finite-memory winning strategy (if one exists) in such games. Finally,
we give a complete characterization of when finite memory of strategies can be
traded off for randomness. In particular, we show that for one-dimension mean-payoff
parity games, randomized memoryless strategies are as powerful as their pure finite-memory
counterparts.
acknowledgement: 'Author supported by Austrian Science Fund (FWF) Grant No P 23499-N23,
FWF NFN Grant No S11407 (RiSE), ERC Start Grant (279307: Graph Games), Microsoft
faculty fellowship.'
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: Mickael
full_name: Randour, Mickael
last_name: Randour
- first_name: Jean-François
full_name: Raskin, Jean-François
last_name: Raskin
citation:
ama: 'Chatterjee K, Randour M, Raskin J-F. Strategy synthesis for multi-dimensional
quantitative objectives. In: Koutny M, Ulidowski I, eds. CONCUR 2012 - Concurrency
Theory. Vol 7454. Berlin, Heidelberg: Springer; 2012:115-131. doi:10.1007/978-3-642-32940-1_10'
apa: 'Chatterjee, K., Randour, M., & Raskin, J.-F. (2012). Strategy synthesis
for multi-dimensional quantitative objectives. In M. Koutny & I. Ulidowski
(Eds.), CONCUR 2012 - Concurrency Theory (Vol. 7454, pp. 115–131). Berlin,
Heidelberg: Springer. https://doi.org/10.1007/978-3-642-32940-1_10'
chicago: 'Chatterjee, Krishnendu, Mickael Randour, and Jean-François Raskin. “Strategy
Synthesis for Multi-Dimensional Quantitative Objectives.” In CONCUR 2012 -
Concurrency Theory, edited by Maciej Koutny and Irek Ulidowski, 7454:115–31.
Berlin, Heidelberg: Springer, 2012. https://doi.org/10.1007/978-3-642-32940-1_10.'
ieee: K. Chatterjee, M. Randour, and J.-F. Raskin, “Strategy synthesis for multi-dimensional
quantitative objectives,” in CONCUR 2012 - Concurrency Theory, Newcastle
upon Tyne, United Kingdom, 2012, vol. 7454, pp. 115–131.
ista: 'Chatterjee K, Randour M, Raskin J-F. 2012. Strategy synthesis for multi-dimensional
quantitative objectives. CONCUR 2012 - Concurrency Theory. CONCUR: Conference
on Concurrency Theory, LNCS, vol. 7454, 115–131.'
mla: Chatterjee, Krishnendu, et al. “Strategy Synthesis for Multi-Dimensional Quantitative
Objectives.” CONCUR 2012 - Concurrency Theory, edited by Maciej Koutny
and Irek Ulidowski, vol. 7454, Springer, 2012, pp. 115–31, doi:10.1007/978-3-642-32940-1_10.
short: K. Chatterjee, M. Randour, J.-F. Raskin, in:, M. Koutny, I. Ulidowski (Eds.),
CONCUR 2012 - Concurrency Theory, Springer, Berlin, Heidelberg, 2012, pp. 115–131.
conference:
end_date: 2012-09-07
location: Newcastle upon Tyne, United Kingdom
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2012-09-04
date_created: 2022-03-21T08:00:21Z
date_published: 2012-09-15T00:00:00Z
date_updated: 2023-02-23T10:55:06Z
day: '15'
department:
- _id: KrCh
doi: 10.1007/978-3-642-32940-1_10
ec_funded: 1
editor:
- first_name: Maciej
full_name: Koutny, Maciej
last_name: Koutny
- first_name: Irek
full_name: Ulidowski, Irek
last_name: Ulidowski
external_id:
arxiv:
- '1201.5073'
intvolume: ' 7454'
language:
- iso: eng
month: '09'
oa_version: Preprint
page: 115-131
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: CONCUR 2012 - Concurrency Theory
publication_identifier:
eisbn:
- '9783642329401'
isbn:
- '9783642329395'
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer
quality_controlled: '1'
related_material:
record:
- id: '2716'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Strategy synthesis for multi-dimensional quantitative objectives
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7454
year: '2012'
...
---
_id: '11794'
abstract:
- lang: eng
text: We study individual rational, Pareto optimal, and incentive compatible mechanisms
for auctions with heterogeneous items and budget limits. For multi-dimensional
valuations we show that there can be no deterministic mechanism with these properties
for divisible items. We use this to show that there can also be no randomized
mechanism that achieves this for either divisible or indivisible items. For single-dimensional
valuations we show that there can be no deterministic mechanism with these properties
for indivisible items, but that there is a randomized mechanism that achieves
this for either divisible or indivisible items. The impossibility results hold
for public budgets, while the mechanism allows private budgets, which is in both
cases the harder variant to show. While all positive results are polynomial-time
algorithms, all negative results hold independent of complexity considerations.
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 MH, Starnberger M. Auctions with heterogeneous items
and budget limits. In: 8th International Workshop on Internet and Network Economics.
Vol 7695. Springer Nature; 2012:44–57. doi:10.1007/978-3-642-35311-6_4'
apa: 'Dütting, P., Henzinger, M. H., & Starnberger, M. (2012). Auctions with
heterogeneous items and budget limits. In 8th International Workshop on Internet
and Network Economics (Vol. 7695, pp. 44–57). Liverpool, United Kingdom: Springer
Nature. https://doi.org/10.1007/978-3-642-35311-6_4'
chicago: Dütting, Paul, Monika H Henzinger, and Martin Starnberger. “Auctions with
Heterogeneous Items and Budget Limits.” In 8th International Workshop on Internet
and Network Economics, 7695:44–57. Springer Nature, 2012. https://doi.org/10.1007/978-3-642-35311-6_4.
ieee: P. Dütting, M. H. Henzinger, and M. Starnberger, “Auctions with heterogeneous
items and budget limits,” in 8th International Workshop on Internet and Network
Economics, Liverpool, United Kingdom, 2012, vol. 7695, pp. 44–57.
ista: 'Dütting P, Henzinger MH, Starnberger M. 2012. Auctions with heterogeneous
items and budget limits. 8th International Workshop on Internet and Network Economics.
WINE: International Conference on Web and Internet Economics, LNCS, vol. 7695,
44–57.'
mla: Dütting, Paul, et al. “Auctions with Heterogeneous Items and Budget Limits.”
8th International Workshop on Internet and Network Economics, vol. 7695,
Springer Nature, 2012, pp. 44–57, doi:10.1007/978-3-642-35311-6_4.
short: P. Dütting, M.H. Henzinger, M. Starnberger, in:, 8th International Workshop
on Internet and Network Economics, Springer Nature, 2012, pp. 44–57.
conference:
end_date: 2012-12-14
location: Liverpool, United Kingdom
name: 'WINE: International Conference on Web and Internet Economics'
start_date: 2012-12-11
date_created: 2022-08-11T11:32:25Z
date_published: 2012-12-01T00:00:00Z
date_updated: 2023-02-21T16:28:29Z
day: '01'
doi: 10.1007/978-3-642-35311-6_4
extern: '1'
external_id:
arxiv:
- '1209.6448'
intvolume: ' 7695'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1209.6448
month: '12'
oa: 1
oa_version: Preprint
page: 44–57
publication: 8th International Workshop on Internet and Network Economics
publication_identifier:
isbn:
- '9783642353109'
issn:
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '11794'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Auctions with heterogeneous items and budget limits
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7695
year: '2012'
...
---
_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'
...
---
_id: '5940'
article_processing_charge: No
author:
- first_name: Gabriel
full_name: Juhás, Gabriel
last_name: Juhás
- first_name: Igor
full_name: Kazlov, Igor
id: 4A997E50-F248-11E8-B48F-1D18A9856A87
last_name: Kazlov
- first_name: Ana
full_name: Juhásová, Ana
last_name: Juhásová
citation:
ama: 'Juhás G, Kazlov I, Juhásová A. Instance Deadlock: A Mystery behind Frozen
Programs. In: Applications and Theory of Petri Nets. Berlin, Heidelberg:
Springer Berlin Heidelberg; 2010:1-17. doi:10.1007/978-3-642-13675-7_1'
apa: 'Juhás, G., Kazlov, I., & Juhásová, A. (2010). Instance Deadlock: A Mystery
behind Frozen Programs. In Applications and Theory of Petri Nets (pp. 1–17).
Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-13675-7_1'
chicago: 'Juhás, Gabriel, Igor Kazlov, and Ana Juhásová. “Instance Deadlock: A Mystery
behind Frozen Programs.” In Applications and Theory of Petri Nets, 1–17.
Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. https://doi.org/10.1007/978-3-642-13675-7_1.'
ieee: 'G. Juhás, I. Kazlov, and A. Juhásová, “Instance Deadlock: A Mystery behind
Frozen Programs,” in Applications and Theory of Petri Nets, Berlin, Heidelberg:
Springer Berlin Heidelberg, 2010, pp. 1–17.'
ista: 'Juhás G, Kazlov I, Juhásová A. 2010.Instance Deadlock: A Mystery behind Frozen
Programs. In: Applications and Theory of Petri Nets. , 1–17.'
mla: 'Juhás, Gabriel, et al. “Instance Deadlock: A Mystery behind Frozen Programs.”
Applications and Theory of Petri Nets, Springer Berlin Heidelberg, 2010,
pp. 1–17, doi:10.1007/978-3-642-13675-7_1.'
short: G. Juhás, I. Kazlov, A. Juhásová, in:, Applications and Theory of Petri Nets,
Springer Berlin Heidelberg, Berlin, Heidelberg, 2010, pp. 1–17.
date_created: 2019-02-08T09:33:41Z
date_published: 2010-01-01T00:00:00Z
date_updated: 2022-04-01T13:45:24Z
doi: 10.1007/978-3-642-13675-7_1
extern: '1'
language:
- iso: eng
oa_version: None
page: 1-17
place: Berlin, Heidelberg
publication: Applications and Theory of Petri Nets
publication_identifier:
isbn:
- '9783642136740'
- '9783642136757'
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer Berlin Heidelberg
status: public
title: 'Instance Deadlock: A Mystery behind Frozen Programs'
type: book_chapter
user_id: 4A997E50-F248-11E8-B48F-1D18A9856A87
year: '2010'
...
---
_id: '11797'
abstract:
- lang: eng
text: "Inspired by online ad allocation, we study online stochastic packing integer
programs from theoretical and practical standpoints. We first present a near-optimal
online algorithm for a general class of packing integer programs which model various
online resource allocation problems including online variants of routing, ad allocations,
generalized assignment, and combinatorial auctions. As our main theoretical result,
we prove that a simple dual training-based algorithm achieves a (1 − o(1))-approximation
guarantee in the random order stochastic model. This is a significant improvement
over logarithmic or constant-factor approximations for the adversarial variants
of the same problems (e.g. factor 1−1\U0001D452 for online ad allocation, and
log(m) for online routing). We then focus on the online display ad allocation
problem and study the efficiency and fairness of various training-based and online
allocation algorithms on data sets collected from real-life display ad allocation
system. Our experimental evaluation confirms the effectiveness of training-based
algorithms on real data sets, and also indicates an intrinsic trade-off between
fairness and efficiency."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Jon
full_name: Feldman, Jon
last_name: Feldman
- 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: Nitish
full_name: Korula, Nitish
last_name: Korula
- first_name: Vahab S.
full_name: Mirrokni, Vahab S.
last_name: Mirrokni
- first_name: Cliff
full_name: Stein, Cliff
last_name: Stein
citation:
ama: 'Feldman J, Henzinger MH, Korula N, Mirrokni VS, Stein C. Online stochastic
packing applied to display ad allocation. In: 18th Annual European Symposium
on Algorithms. Vol 6346. Springer Nature; 2010:182–194. doi:10.1007/978-3-642-15775-2_16'
apa: 'Feldman, J., Henzinger, M. H., Korula, N., Mirrokni, V. S., & Stein, C.
(2010). Online stochastic packing applied to display ad allocation. In 18th
Annual European Symposium on Algorithms (Vol. 6346, pp. 182–194). Liverpool,
United Kingdom: Springer Nature. https://doi.org/10.1007/978-3-642-15775-2_16'
chicago: Feldman, Jon, Monika H Henzinger, Nitish Korula, Vahab S. Mirrokni, and
Cliff Stein. “Online Stochastic Packing Applied to Display Ad Allocation.” In
18th Annual European Symposium on Algorithms, 6346:182–194. Springer Nature,
2010. https://doi.org/10.1007/978-3-642-15775-2_16.
ieee: J. Feldman, M. H. Henzinger, N. Korula, V. S. Mirrokni, and C. Stein, “Online
stochastic packing applied to display ad allocation,” in 18th Annual European
Symposium on Algorithms, Liverpool, United Kingdom, 2010, vol. 6346, pp. 182–194.
ista: 'Feldman J, Henzinger MH, Korula N, Mirrokni VS, Stein C. 2010. Online stochastic
packing applied to display ad allocation. 18th Annual European Symposium on Algorithms.
ESA: European Symposium on Algorithms, LNCS, vol. 6346, 182–194.'
mla: Feldman, Jon, et al. “Online Stochastic Packing Applied to Display Ad Allocation.”
18th Annual European Symposium on Algorithms, vol. 6346, Springer Nature,
2010, pp. 182–194, doi:10.1007/978-3-642-15775-2_16.
short: J. Feldman, M.H. Henzinger, N. Korula, V.S. Mirrokni, C. Stein, in:, 18th
Annual European Symposium on Algorithms, Springer Nature, 2010, pp. 182–194.
conference:
end_date: 2010-09-08
location: Liverpool, United Kingdom
name: 'ESA: European Symposium on Algorithms'
start_date: 2010-09-06
date_created: 2022-08-11T12:14:20Z
date_published: 2010-09-01T00:00:00Z
date_updated: 2023-02-13T11:36:46Z
day: '01'
doi: 10.1007/978-3-642-15775-2_16
extern: '1'
external_id:
arxiv:
- '1001.5076'
intvolume: ' 6346'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1001.5076
month: '09'
oa: 1
oa_version: Preprint
page: 182–194
publication: 18th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '3642157742'
issn:
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Online stochastic packing applied to display ad allocation
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6346
year: '2010'
...
---
_id: '11798'
abstract:
- lang: eng
text: Starting with two models fifty years ago, the discrete marriage game [1] and
the continuous assignment game [2], the study of stable matchings has evolved
into a rich theory with applications in many areas. Most notably, it has lead
to a number of truthful mechanisms that have seen a recent rejuvenation in the
context of sponsored search. In this paper we survey the history of these problems
and provide several links to ongoing research in the field.
alternative_title:
- LNCS
article_processing_charge: No
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
citation:
ama: 'Dütting P, Henzinger MH. Mechanisms for the marriage and the assignment game.
In: 7th International Conference on Algorithms and Complexity. Vol 6078.
Springer Nature; 2010:6–12. doi:10.1007/978-3-642-13073-1_2'
apa: 'Dütting, P., & Henzinger, M. H. (2010). Mechanisms for the marriage and
the assignment game. In 7th International Conference on Algorithms and Complexity
(Vol. 6078, pp. 6–12). Rome, Italy: Springer Nature. https://doi.org/10.1007/978-3-642-13073-1_2'
chicago: Dütting, Paul, and Monika H Henzinger. “Mechanisms for the Marriage and
the Assignment Game.” In 7th International Conference on Algorithms and Complexity,
6078:6–12. Springer Nature, 2010. https://doi.org/10.1007/978-3-642-13073-1_2.
ieee: P. Dütting and M. H. Henzinger, “Mechanisms for the marriage and the assignment
game,” in 7th International Conference on Algorithms and Complexity, Rome,
Italy, 2010, vol. 6078, pp. 6–12.
ista: 'Dütting P, Henzinger MH. 2010. Mechanisms for the marriage and the assignment
game. 7th International Conference on Algorithms and Complexity. CIAC: International
Conference on Algorithms and Complexity, LNCS, vol. 6078, 6–12.'
mla: Dütting, Paul, and Monika H. Henzinger. “Mechanisms for the Marriage and the
Assignment Game.” 7th International Conference on Algorithms and Complexity,
vol. 6078, Springer Nature, 2010, pp. 6–12, doi:10.1007/978-3-642-13073-1_2.
short: P. Dütting, M.H. Henzinger, in:, 7th International Conference on Algorithms
and Complexity, Springer Nature, 2010, pp. 6–12.
conference:
end_date: 2010-05-28
location: Rome, Italy
name: 'CIAC: International Conference on Algorithms and Complexity'
start_date: 2010-05-26
date_created: 2022-08-11T12:27:43Z
date_published: 2010-05-01T00:00:00Z
date_updated: 2023-02-13T11:41:29Z
day: '01'
doi: 10.1007/978-3-642-13073-1_2
extern: '1'
intvolume: ' 6078'
language:
- iso: eng
month: '05'
oa_version: None
page: 6–12
publication: 7th International Conference on Algorithms and Complexity
publication_identifier:
isbn:
- '9783642130724'
issn:
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Mechanisms for the marriage and the assignment game
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6078
year: '2010'
...
---
_id: '11799'
abstract:
- lang: eng
text: We study the problem of matching bidders to items where each bidder i has
general, strictly monotonic utility functions u i,j (p j ) expressing her utility
of being matched to item j at price p j . For this setting we prove that a bidder
optimal outcome always exists, even when the utility functions are non-linear
and non-continuous. Furthermore, we give an algorithm to find such a solution.
Although the running time of this algorithm is exponential in the number of items,
it is polynomial in the number of bidders.
alternative_title:
- LNCS
article_processing_charge: No
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. Bidder optimal assignments for general utilities.
In: 5th International Workshop on Internet and Network Economics. Vol 5929.
Springer Nature; 2009:575-582. doi:10.1007/978-3-642-10841-9_58'
apa: 'Dütting, P., Henzinger, M. H., & Weber, I. (2009). Bidder optimal assignments
for general utilities. In 5th International Workshop on Internet and Network
Economics (Vol. 5929, pp. 575–582). Rome, Italy: Springer Nature. https://doi.org/10.1007/978-3-642-10841-9_58'
chicago: Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Bidder Optimal Assignments
for General Utilities.” In 5th International Workshop on Internet and Network
Economics, 5929:575–82. Springer Nature, 2009. https://doi.org/10.1007/978-3-642-10841-9_58.
ieee: P. Dütting, M. H. Henzinger, and I. Weber, “Bidder optimal assignments for
general utilities,” in 5th International Workshop on Internet and Network Economics,
Rome, Italy, 2009, vol. 5929, pp. 575–582.
ista: 'Dütting P, Henzinger MH, Weber I. 2009. Bidder optimal assignments for general
utilities. 5th International Workshop on Internet and Network Economics. WINE:
International Conference on Web and Internet Economics, LNCS, vol. 5929, 575–582.'
mla: Dütting, Paul, et al. “Bidder Optimal Assignments for General Utilities.” 5th
International Workshop on Internet and Network Economics, vol. 5929, Springer
Nature, 2009, pp. 575–82, doi:10.1007/978-3-642-10841-9_58.
short: P. Dütting, M.H. Henzinger, I. Weber, in:, 5th International Workshop on
Internet and Network Economics, Springer Nature, 2009, pp. 575–582.
conference:
end_date: 2009-12-18
location: Rome, Italy
name: 'WINE: International Conference on Web and Internet Economics'
start_date: 2009-12-14
date_created: 2022-08-11T12:33:38Z
date_published: 2009-12-01T00:00:00Z
date_updated: 2023-02-21T16:32:35Z
day: '01'
doi: 10.1007/978-3-642-10841-9_58
extern: '1'
intvolume: ' 5929'
language:
- iso: eng
month: '12'
oa_version: None
page: 575-582
publication: 5th International Workshop on Internet and Network Economics
publication_identifier:
isbn:
- '9783642108402'
issn:
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '11902'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Bidder optimal assignments for general utilities
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 5929
year: '2009'
...