---
_id: '11758'
article_processing_charge: No
article_type: letter_note
author:
- first_name: Luca
  full_name: Aceto, Luca
  last_name: Aceto
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Jiří
  full_name: Sgall, Jiří
  last_name: Sgall
citation:
  ama: Aceto L, Henzinger M, Sgall J. 38th International Colloquium on Automata, Languages
    and Programming. <i>Information and Computation</i>. 2013;222(1):1. doi:<a href="https://doi.org/10.1016/j.ic.2012.11.002">10.1016/j.ic.2012.11.002</a>
  apa: Aceto, L., Henzinger, M., &#38; Sgall, J. (2013). 38th International Colloquium
    on Automata, Languages and Programming. <i>Information and Computation</i>. Elsevier.
    <a href="https://doi.org/10.1016/j.ic.2012.11.002">https://doi.org/10.1016/j.ic.2012.11.002</a>
  chicago: Aceto, Luca, Monika Henzinger, and Jiří Sgall. “38th International Colloquium
    on Automata, Languages and Programming.” <i>Information and Computation</i>. Elsevier,
    2013. <a href="https://doi.org/10.1016/j.ic.2012.11.002">https://doi.org/10.1016/j.ic.2012.11.002</a>.
  ieee: L. Aceto, M. Henzinger, and J. Sgall, “38th International Colloquium on Automata,
    Languages and Programming,” <i>Information and Computation</i>, vol. 222, no.
    1. Elsevier, p. 1, 2013.
  ista: Aceto L, Henzinger M, Sgall J. 2013. 38th International Colloquium on Automata,
    Languages and Programming. Information and Computation. 222(1), 1.
  mla: Aceto, Luca, et al. “38th International Colloquium on Automata, Languages and
    Programming.” <i>Information and Computation</i>, vol. 222, no. 1, Elsevier, 2013,
    p. 1, doi:<a href="https://doi.org/10.1016/j.ic.2012.11.002">10.1016/j.ic.2012.11.002</a>.
  short: L. Aceto, M. Henzinger, J. Sgall, Information and Computation 222 (2013)
    1.
date_created: 2022-08-08T11:25:34Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2024-11-06T12:01:32Z
day: '01'
doi: 10.1016/j.ic.2012.11.002
extern: '1'
intvolume: '       222'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: '1'
publication: Information and Computation
publication_identifier:
  issn:
  - 0890-5401
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: 38th International Colloquium on Automata, Languages and Programming
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 222
year: '2013'
...
---
_id: '11759'
abstract:
- lang: eng
  text: Matching markets play a prominent role in economic theory. A prime example
    of such a market is the sponsored search market. Here, as in other markets of
    that kind, market equilibria correspond to feasible, envy free, and bidder optimal
    outcomes. For settings without budgets such an outcome always exists and can be
    computed in polynomial-time by the so-called Hungarian Method. Moreover, every
    mechanism that computes such an outcome is incentive compatible. We show that
    the Hungarian Method can be modified so that it finds a feasible, envy free, and
    bidder optimal outcome for settings with budgets. We also show that in settings
    with budgets no mechanism that computes such an outcome can be incentive compatible
    for all inputs. For inputs in general position, however, the presented mechanism—as
    any other mechanism that computes such an outcome for settings with budgets—is
    incentive compatible.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Paul
  full_name: Dütting, Paul
  last_name: Dütting
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Ingmar
  full_name: Weber, Ingmar
  last_name: Weber
citation:
  ama: Dütting P, Henzinger M, Weber I. Sponsored search, market equilibria, and the
    Hungarian Method. <i>Information Processing Letters</i>. 2013;113(3):67-73. doi:<a
    href="https://doi.org/10.1016/j.ipl.2012.11.006">10.1016/j.ipl.2012.11.006</a>
  apa: Dütting, P., Henzinger, M., &#38; Weber, I. (2013). Sponsored search, market
    equilibria, and the Hungarian Method. <i>Information Processing Letters</i>. Elsevier.
    <a href="https://doi.org/10.1016/j.ipl.2012.11.006">https://doi.org/10.1016/j.ipl.2012.11.006</a>
  chicago: Dütting, Paul, Monika Henzinger, and Ingmar Weber. “Sponsored Search, Market
    Equilibria, and the Hungarian Method.” <i>Information Processing Letters</i>.
    Elsevier, 2013. <a href="https://doi.org/10.1016/j.ipl.2012.11.006">https://doi.org/10.1016/j.ipl.2012.11.006</a>.
  ieee: P. Dütting, M. Henzinger, and I. Weber, “Sponsored search, market equilibria,
    and the Hungarian Method,” <i>Information Processing Letters</i>, vol. 113, no.
    3. Elsevier, pp. 67–73, 2013.
  ista: Dütting P, Henzinger M, Weber I. 2013. Sponsored search, market equilibria,
    and the Hungarian Method. Information Processing Letters. 113(3), 67–73.
  mla: Dütting, Paul, et al. “Sponsored Search, Market Equilibria, and the Hungarian
    Method.” <i>Information Processing Letters</i>, vol. 113, no. 3, Elsevier, 2013,
    pp. 67–73, doi:<a href="https://doi.org/10.1016/j.ipl.2012.11.006">10.1016/j.ipl.2012.11.006</a>.
  short: P. Dütting, M. Henzinger, I. Weber, Information Processing Letters 113 (2013)
    67–73.
date_created: 2022-08-08T11:29:08Z
date_published: 2013-02-15T00:00:00Z
date_updated: 2024-11-06T12:09:36Z
day: '15'
doi: 10.1016/j.ipl.2012.11.006
extern: '1'
external_id:
  arxiv:
  - '0912.1934'
intvolume: '       113'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/0912.1934
month: '02'
oa: 1
oa_version: Preprint
page: 67-73
publication: Information Processing Letters
publication_identifier:
  issn:
  - 0020-0190
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Sponsored search, market equilibria, and the Hungarian Method
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 113
year: '2013'
...
---
_id: '11791'
abstract:
- lang: eng
  text: The focus of classic mechanism design has been on truthful direct-revelation
    mechanisms. In the context of combinatorial auctions the truthful direct-revelation
    mechanism that maximizes social welfare is the VCG mechanism. For many valuation
    spaces computing the allocation and payments of the VCG mechanism, however, is
    a computationally hard problem. We thus study the performance of the VCG mechanism
    when bidders are forced to choose bids from a subspace of the valuation space
    for which the VCG outcome can be computed efficiently. We prove improved upper
    bounds on the welfare loss for restrictions to additive bids and upper and lower
    bounds for restrictions to non-additive bids. These bounds show that the welfare
    loss increases in expressiveness. All our bounds apply to equilibrium concepts
    that can be computed in polynomial time as well as to learning outcomes.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Paul
  full_name: Dütting, Paul
  last_name: Dütting
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Martin
  full_name: Starnberger, Martin
  last_name: Starnberger
citation:
  ama: 'Dütting P, Henzinger M, Starnberger M. Valuation compressions in VCG-based
    combinatorial auctions. In: <i>9th International Conference on Web and Internet
    Economics</i>. Vol 8289. Springer Nature; 2013:146–159. doi:<a href="https://doi.org/10.1007/978-3-642-45046-4_13">10.1007/978-3-642-45046-4_13</a>'
  apa: 'Dütting, P., Henzinger, M., &#38; Starnberger, M. (2013). Valuation compressions
    in VCG-based combinatorial auctions. In <i>9th International Conference on Web
    and Internet Economics</i> (Vol. 8289, pp. 146–159). Cambridge, MA, USA: Springer
    Nature. <a href="https://doi.org/10.1007/978-3-642-45046-4_13">https://doi.org/10.1007/978-3-642-45046-4_13</a>'
  chicago: Dütting, Paul, Monika Henzinger, and Martin Starnberger. “Valuation Compressions
    in VCG-Based Combinatorial Auctions.” In <i>9th International Conference on Web
    and Internet Economics</i>, 8289:146–159. Springer Nature, 2013. <a href="https://doi.org/10.1007/978-3-642-45046-4_13">https://doi.org/10.1007/978-3-642-45046-4_13</a>.
  ieee: P. Dütting, M. Henzinger, and M. Starnberger, “Valuation compressions in VCG-based
    combinatorial auctions,” in <i>9th International Conference on Web and Internet
    Economics</i>, Cambridge, MA, USA, 2013, vol. 8289, pp. 146–159.
  ista: 'Dütting P, Henzinger M, Starnberger M. 2013. Valuation compressions in VCG-based
    combinatorial auctions. 9th International Conference on Web and Internet Economics.
    WINE: International Conference on Web and Internet Economics, LNCS, vol. 8289,
    146–159.'
  mla: Dütting, Paul, et al. “Valuation Compressions in VCG-Based Combinatorial Auctions.”
    <i>9th International Conference on Web and Internet Economics</i>, vol. 8289,
    Springer Nature, 2013, pp. 146–159, doi:<a href="https://doi.org/10.1007/978-3-642-45046-4_13">10.1007/978-3-642-45046-4_13</a>.
  short: P. Dütting, M. Henzinger, M. Starnberger, in:, 9th International Conference
    on Web and Internet Economics, Springer Nature, 2013, pp. 146–159.
conference:
  end_date: 2013-12-14
  location: Cambridge, MA, USA
  name: 'WINE: International Conference on Web and Internet Economics'
  start_date: 2013-12-01
date_created: 2022-08-11T11:05:14Z
date_published: 2013-12-01T00:00:00Z
date_updated: 2024-11-06T12:12:00Z
day: '01'
doi: 10.1007/978-3-642-45046-4_13
extern: '1'
external_id:
  arxiv:
  - '1310.3153'
intvolume: '      8289'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1310.3153
month: '12'
oa: 1
oa_version: Preprint
page: 146–159
publication: 9th International Conference on Web and Internet Economics
publication_identifier:
  isbn:
  - '9783642450457'
  issn:
  - 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Valuation compressions in VCG-based combinatorial auctions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8289
year: '2013'
...
---
_id: '11792'
abstract:
- lang: eng
  text: "We study the problem of maximizing a monotone submodular function with viability
    constraints. This problem originates from computational biology, where we are
    given a phylogenetic tree over a set of species and a directed graph, the so-called
    food web, encoding viability constraints between these species. These food webs
    usually have constant depth. The goal is to select a subset of k species that
    satisfies the viability constraints and has maximal phylogenetic diversity. As
    this problem is known to be NP-hard, we investigate approximation algorithm. We
    present the first constant factor approximation algorithm if the depth is constant.
    Its approximation ratio is (1−1\U0001D452√). This algorithm not only applies to
    phylogenetic trees with viability constraints but for arbitrary monotone submodular
    set functions with viability constraints. Second, we show that there is no (1 − 1/e + ε)-approximation
    algorithm for our problem setting (even for additive functions) and that there
    is no approximation algorithm for a slight extension of this setting."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Wolfgang
  full_name: Dvořák, Wolfgang
  last_name: Dvořák
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: David P.
  full_name: Williamson, David P.
  last_name: Williamson
citation:
  ama: 'Dvořák W, Henzinger M, Williamson DP. Maximizing a submodular function with
    viability constraints. In: <i>21st Annual European Symposium on Algorithms</i>.
    Vol 8125. Springer Nature; 2013:409-420. doi:<a href="https://doi.org/10.1007/978-3-642-40450-4_35">10.1007/978-3-642-40450-4_35</a>'
  apa: 'Dvořák, W., Henzinger, M., &#38; Williamson, D. P. (2013). Maximizing a submodular
    function with viability constraints. In <i>21st Annual European Symposium on Algorithms</i>
    (Vol. 8125, pp. 409–420). Sophia Antipolis, France: Springer Nature. <a href="https://doi.org/10.1007/978-3-642-40450-4_35">https://doi.org/10.1007/978-3-642-40450-4_35</a>'
  chicago: Dvořák, Wolfgang, Monika Henzinger, and David P. Williamson. “Maximizing
    a Submodular Function with Viability Constraints.” In <i>21st Annual European
    Symposium on Algorithms</i>, 8125:409–20. Springer Nature, 2013. <a href="https://doi.org/10.1007/978-3-642-40450-4_35">https://doi.org/10.1007/978-3-642-40450-4_35</a>.
  ieee: W. Dvořák, M. Henzinger, and D. P. Williamson, “Maximizing a submodular function
    with viability constraints,” in <i>21st Annual European Symposium on Algorithms</i>,
    Sophia Antipolis, France, 2013, vol. 8125, pp. 409–420.
  ista: 'Dvořák W, Henzinger M, Williamson DP. 2013. Maximizing a submodular function
    with viability constraints. 21st Annual European Symposium on Algorithms. ESA:
    European Symposium on Algorithms, LNCS, vol. 8125, 409–420.'
  mla: Dvořák, Wolfgang, et al. “Maximizing a Submodular Function with Viability Constraints.”
    <i>21st Annual European Symposium on Algorithms</i>, vol. 8125, Springer Nature,
    2013, pp. 409–20, doi:<a href="https://doi.org/10.1007/978-3-642-40450-4_35">10.1007/978-3-642-40450-4_35</a>.
  short: W. Dvořák, M. Henzinger, D.P. Williamson, in:, 21st Annual European Symposium
    on Algorithms, Springer Nature, 2013, pp. 409–420.
conference:
  end_date: 2013-09-04
  location: Sophia Antipolis, France
  name: 'ESA: European Symposium on Algorithms'
  start_date: 2013-09-02
date_created: 2022-08-11T11:18:19Z
date_published: 2013-09-01T00:00:00Z
date_updated: 2024-11-06T12:12:13Z
day: '01'
doi: 10.1007/978-3-642-40450-4_35
extern: '1'
external_id:
  arxiv:
  - '1611.05753'
intvolume: '      8125'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1611.05753
month: '09'
oa: 1
oa_version: Preprint
page: 409 - 420
publication: 21st Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783642404498'
  issn:
  - 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '11792'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Maximizing a submodular function with viability constraints
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8125
year: '2013'
...
---
_id: '11793'
abstract:
- lang: eng
  text: "We study the problem of maintaining a breadth-first spanning tree (BFS tree)
    in partially dynamic distributed networks modeling a sequence of either failures
    or additions of communication links (but not both). We show (1 + ε)-approximation
    algorithms whose amortized time (over some number of link changes) is sublinear
    in D, the maximum diameter of the network. This breaks the Θ(D) time bound of
    recomputing “from scratch”.\r\n\r\nOur technique also leads to a (1 + ε)-approximate
    incremental algorithm for single-source shortest paths (SSSP) in the sequential
    (usual RAM) model. Prior to our work, the state of the art was the classic exact
    algorithm of [9] that is optimal under some assumptions [27]. Our result is the
    first to show that, in the incremental setting, this bound can be beaten in certain
    cases if a small approximation is allowed."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Sebastian
  full_name: Krinninger, Sebastian
  last_name: Krinninger
- first_name: Danupon
  full_name: Nanongkai, Danupon
  last_name: Nanongkai
citation:
  ama: 'Henzinger M, Krinninger S, Nanongkai D. Sublinear-time maintenance of breadth-first
    spanning tree in partially dynamic networks. In: <i>40th International Colloquium
    on Automata, Languages, and Programming</i>. Vol 7966. Springer Nature; 2013:607–619.
    doi:<a href="https://doi.org/10.1007/978-3-642-39212-2_53">10.1007/978-3-642-39212-2_53</a>'
  apa: 'Henzinger, M., Krinninger, S., &#38; Nanongkai, D. (2013). Sublinear-time
    maintenance of breadth-first spanning tree in partially dynamic networks. In <i>40th
    International Colloquium on Automata, Languages, and Programming</i> (Vol. 7966,
    pp. 607–619). Riga, Latvia: Springer Nature. <a href="https://doi.org/10.1007/978-3-642-39212-2_53">https://doi.org/10.1007/978-3-642-39212-2_53</a>'
  chicago: Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time
    Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks.” In
    <i>40th International Colloquium on Automata, Languages, and Programming</i>,
    7966:607–619. Springer Nature, 2013. <a href="https://doi.org/10.1007/978-3-642-39212-2_53">https://doi.org/10.1007/978-3-642-39212-2_53</a>.
  ieee: M. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time maintenance
    of breadth-first spanning tree in partially dynamic networks,” in <i>40th International
    Colloquium on Automata, Languages, and Programming</i>, Riga, Latvia, 2013, vol.
    7966, pp. 607–619.
  ista: 'Henzinger M, Krinninger S, Nanongkai D. 2013. Sublinear-time maintenance
    of breadth-first spanning tree in partially dynamic networks. 40th International
    Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium
    on Automata, Languages, and Programming, LNCS, vol. 7966, 607–619.'
  mla: Henzinger, Monika, et al. “Sublinear-Time Maintenance of Breadth-First Spanning
    Tree in Partially Dynamic Networks.” <i>40th International Colloquium on Automata,
    Languages, and Programming</i>, vol. 7966, Springer Nature, 2013, pp. 607–619,
    doi:<a href="https://doi.org/10.1007/978-3-642-39212-2_53">10.1007/978-3-642-39212-2_53</a>.
  short: M. Henzinger, S. Krinninger, D. Nanongkai, in:, 40th International Colloquium
    on Automata, Languages, and Programming, Springer Nature, 2013, pp. 607–619.
conference:
  end_date: 2013-07-12
  location: Riga, Latvia
  name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
  start_date: 2013-07-08
date_created: 2022-08-11T11:25:13Z
date_published: 2013-07-01T00:00:00Z
date_updated: 2024-11-06T12:12:27Z
day: '01'
doi: 10.1007/978-3-642-39212-2_53
extern: '1'
external_id:
  arxiv:
  - '1512.08147'
intvolume: '      7966'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1512.08147
month: '07'
oa: 1
oa_version: Preprint
page: 607–619
publication: 40th International Colloquium on Automata, Languages, and Programming
publication_identifier:
  isbn:
  - '9783642392115'
  issn:
  - 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '11793'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Sublinear-time maintenance of breadth-first spanning tree in partially dynamic
  networks
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7966
year: '2013'
...
---
_id: '11856'
abstract:
- lang: eng
  text: 'We study dynamic (1 + ϵ)-approximation algorithms for the all-pairs shortest
    paths problem in unweighted undirected n-node m-edge graphs under edge deletions.
    The fastest algorithm for this problem is a randomized algorithm with a total
    update time of Ȏ(mn) and constant query time by Roditty and Zwick (FOCS 2004).
    The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach
    (JACM 1981); it has a total update time of O(mn 2 ) and constant query time. We
    improve these results as follows: (1) We present an algorithm with a total update
    time of Ȏ(n 5/2 ) and constant query time that has an additive error of two in
    addition to the 1 + ϵ multiplicative error. This beats the previous Ȏ(mn) time
    when m = Ω(n 3/2 ). Note that the additive error is unavoidable since, even in
    the static case, an O(n 3-δ )-time (a so-called truly sub cubic) combinatorial
    algorithm with 1 + ϵ multiplicative error cannot have an additive error less than
    2 - ϵ, unless we make a major breakthrough for Boolean matrix multiplication (Dor,
    Halperin and Zwick FOCS 1996) and many other long-standing problems (Vassilevska
    Williams and Williams FOCS 2010). The algorithm can also be turned into a (2 +
    ϵ)-approximation algorithm (without an additive error) with the same time guarantees,
    improving the recent (3 + ϵ)-approximation algorithm with Ȏ(n 5/2+O(1√(log n))
    ) running time of Bernstein and Roditty (SODA 2011) in terms of both approximation
    and time guarantees. (2) We present a deterministic algorithm with a total update
    time of Ȏ(mn) and a query time of O(log log n). The algorithm has a multiplicative
    error of 1 + ϵ and gives the first improved deterministic algorithm since 1981.
    It also answers an open question raised by Bernstein in his STOC 2013 paper. In
    order to achieve our results, we introduce two new techniques: (1) A lazy Even-Shiloach
    tree algorithm which maintains a bounded-distance shortest-paths tree on a certain
    type of emulator called locally persevering emulator. (2) A derandomization technique
    based on moving Even-Shiloach trees as a way to derandomize the standard random
    set argument. These techniques might be of independent interest.'
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Sebastian
  full_name: Krinninger, Sebastian
  last_name: Krinninger
- first_name: Danupon
  full_name: Nanongkai, Danupon
  last_name: Nanongkai
citation:
  ama: 'Henzinger M, Krinninger S, Nanongkai D. Dynamic approximate all-pairs shortest
    paths: Breaking the O(mn) barrier and derandomization. In: <i>54th Annual Symposium
    on Foundations of Computer Science</i>. Institute of Electrical and Electronics
    Engineers; 2013:538-547. doi:<a href="https://doi.org/10.1109/focs.2013.64">10.1109/focs.2013.64</a>'
  apa: 'Henzinger, M., Krinninger, S., &#38; Nanongkai, D. (2013). Dynamic approximate
    all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. In <i>54th
    Annual Symposium on Foundations of Computer Science</i> (pp. 538–547). Berkeley,
    CA, United States: Institute of Electrical and Electronics Engineers. <a href="https://doi.org/10.1109/focs.2013.64">https://doi.org/10.1109/focs.2013.64</a>'
  chicago: 'Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Dynamic
    Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.”
    In <i>54th Annual Symposium on Foundations of Computer Science</i>, 538–47. Institute
    of Electrical and Electronics Engineers, 2013. <a href="https://doi.org/10.1109/focs.2013.64">https://doi.org/10.1109/focs.2013.64</a>.'
  ieee: 'M. Henzinger, S. Krinninger, and D. Nanongkai, “Dynamic approximate all-pairs
    shortest paths: Breaking the O(mn) barrier and derandomization,” in <i>54th Annual
    Symposium on Foundations of Computer Science</i>, Berkeley, CA, United States,
    2013, pp. 538–547.'
  ista: 'Henzinger M, Krinninger S, Nanongkai D. 2013. Dynamic approximate all-pairs
    shortest paths: Breaking the O(mn) barrier and derandomization. 54th Annual Symposium
    on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer
    Science, 538–547.'
  mla: 'Henzinger, Monika, et al. “Dynamic Approximate All-Pairs Shortest Paths: Breaking
    the O(Mn) Barrier and Derandomization.” <i>54th Annual Symposium on Foundations
    of Computer Science</i>, Institute of Electrical and Electronics Engineers, 2013,
    pp. 538–47, doi:<a href="https://doi.org/10.1109/focs.2013.64">10.1109/focs.2013.64</a>.'
  short: M. Henzinger, S. Krinninger, D. Nanongkai, in:, 54th Annual Symposium on
    Foundations of Computer Science, Institute of Electrical and Electronics Engineers,
    2013, pp. 538–547.
conference:
  end_date: 2013-10-29
  location: Berkeley, CA, United States
  name: 'FOCS: Symposium on Foundations of Computer Science'
  start_date: 2013-10-26
date_created: 2022-08-16T08:22:37Z
date_published: 2013-10-01T00:00:00Z
date_updated: 2024-11-06T12:18:28Z
day: '01'
doi: 10.1109/focs.2013.64
extern: '1'
external_id:
  arxiv:
  - '1308.0776'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1308.0776
month: '10'
oa: 1
oa_version: Preprint
page: 538-547
publication: 54th Annual Symposium on Foundations of Computer Science
publication_identifier:
  eisbn:
  - 978-0-7695-5135-7
  issn:
  - 0272-5428
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and
  derandomization'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '11902'
abstract:
- lang: eng
  text: "We study the problem of matching bidders to items where each bidder i has
    general, strictly monotonic utility functions ui,j(pj) expressing his utility
    of being matched to item j at price pj. For this setting we prove that a bidder
    optimal outcome always exists, even when the utility functions are non-linear
    and non-continuous. We give sufficient conditions under\r\nwhich every mechanism
    that finds a bidder optimal outcome is incentive compatible. We also give a mechanism
    that finds a bidder optimal outcome if the conditions for incentive compatibility
    are satisfied. The running time of this mechanism is exponential in the number
    of items, but polynomial in the number of bidders."
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 M, Weber I. Bidder optimal assignments for general utilities.
    <i>Theoretical Computer Science</i>. 2013;478(3):22-32. doi:<a href="https://doi.org/10.1016/j.tcs.2013.01.030">10.1016/j.tcs.2013.01.030</a>
  apa: Dütting, P., Henzinger, M., &#38; Weber, I. (2013). Bidder optimal assignments
    for general utilities. <i>Theoretical Computer Science</i>. Elsevier. <a href="https://doi.org/10.1016/j.tcs.2013.01.030">https://doi.org/10.1016/j.tcs.2013.01.030</a>
  chicago: Dütting, Paul, Monika Henzinger, and Ingmar Weber. “Bidder Optimal Assignments
    for General Utilities.” <i>Theoretical Computer Science</i>. Elsevier, 2013. <a
    href="https://doi.org/10.1016/j.tcs.2013.01.030">https://doi.org/10.1016/j.tcs.2013.01.030</a>.
  ieee: P. Dütting, M. Henzinger, and I. Weber, “Bidder optimal assignments for general
    utilities,” <i>Theoretical Computer Science</i>, vol. 478, no. 3. Elsevier, pp.
    22–32, 2013.
  ista: Dütting P, Henzinger M, Weber I. 2013. Bidder optimal assignments for general
    utilities. Theoretical Computer Science. 478(3), 22–32.
  mla: Dütting, Paul, et al. “Bidder Optimal Assignments for General Utilities.” <i>Theoretical
    Computer Science</i>, vol. 478, no. 3, Elsevier, 2013, pp. 22–32, doi:<a href="https://doi.org/10.1016/j.tcs.2013.01.030">10.1016/j.tcs.2013.01.030</a>.
  short: P. Dütting, M. Henzinger, I. Weber, Theoretical Computer Science 478 (2013)
    22–32.
date_created: 2022-08-17T11:11:04Z
date_published: 2013-03-25T00:00:00Z
date_updated: 2024-11-06T12:24:12Z
day: '25'
doi: 10.1016/j.tcs.2013.01.030
extern: '1'
intvolume: '       478'
issue: '3'
language:
- iso: eng
month: '03'
oa_version: None
page: 22-32
publication: Theoretical Computer Science
publication_identifier:
  issn:
  - 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
  record:
  - id: '11799'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Bidder optimal assignments for general utilities
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 478
year: '2013'
...
---
_id: '11959'
abstract:
- lang: eng
  text: No catalyst required! A highly efficient, catalyst-free process to generate
    diimide in situ from hydrazine monohydrate and molecular oxygen for the selective
    reduction of alkenes has been developed. The use of a gas–liquid segmented flow
    system allowed safe operating conditions and dramatically enhanced this atom-economical
    reaction, resulting in short processing times.
article_processing_charge: No
article_type: letter_note
author:
- first_name: Bartholomäus
  full_name: Pieber, Bartholomäus
  id: 93e5e5b2-0da6-11ed-8a41-af589a024726
  last_name: Pieber
  orcid: 0000-0001-8689-388X
- first_name: Sabrina Teixeira
  full_name: Martinez, Sabrina Teixeira
  last_name: Martinez
- first_name: David
  full_name: Cantillo, David
  last_name: Cantillo
- first_name: C. Oliver
  full_name: Kappe, C. Oliver
  last_name: Kappe
citation:
  ama: 'Pieber B, Martinez ST, Cantillo D, Kappe CO. In situ generation of diimide
    from hydrazine and oxygen: Continuous-flow transfer hydrogenation of olefins.
    <i>Angewandte Chemie International Edition</i>. 2013;52(39):10241-10244. doi:<a
    href="https://doi.org/10.1002/anie.201303528">10.1002/anie.201303528</a>'
  apa: 'Pieber, B., Martinez, S. T., Cantillo, D., &#38; Kappe, C. O. (2013). In situ
    generation of diimide from hydrazine and oxygen: Continuous-flow transfer hydrogenation
    of olefins. <i>Angewandte Chemie International Edition</i>. Wiley. <a href="https://doi.org/10.1002/anie.201303528">https://doi.org/10.1002/anie.201303528</a>'
  chicago: 'Pieber, Bartholomäus, Sabrina Teixeira Martinez, David Cantillo, and C.
    Oliver Kappe. “In Situ Generation of Diimide from Hydrazine and Oxygen: Continuous-Flow
    Transfer Hydrogenation of Olefins.” <i>Angewandte Chemie International Edition</i>.
    Wiley, 2013. <a href="https://doi.org/10.1002/anie.201303528">https://doi.org/10.1002/anie.201303528</a>.'
  ieee: 'B. Pieber, S. T. Martinez, D. Cantillo, and C. O. Kappe, “In situ generation
    of diimide from hydrazine and oxygen: Continuous-flow transfer hydrogenation of
    olefins,” <i>Angewandte Chemie International Edition</i>, vol. 52, no. 39. Wiley,
    pp. 10241–10244, 2013.'
  ista: 'Pieber B, Martinez ST, Cantillo D, Kappe CO. 2013. In situ generation of
    diimide from hydrazine and oxygen: Continuous-flow transfer hydrogenation of olefins.
    Angewandte Chemie International Edition. 52(39), 10241–10244.'
  mla: 'Pieber, Bartholomäus, et al. “In Situ Generation of Diimide from Hydrazine
    and Oxygen: Continuous-Flow Transfer Hydrogenation of Olefins.” <i>Angewandte
    Chemie International Edition</i>, vol. 52, no. 39, Wiley, 2013, pp. 10241–44,
    doi:<a href="https://doi.org/10.1002/anie.201303528">10.1002/anie.201303528</a>.'
  short: B. Pieber, S.T. Martinez, D. Cantillo, C.O. Kappe, Angewandte Chemie International
    Edition 52 (2013) 10241–10244.
date_created: 2022-08-24T11:01:47Z
date_published: 2013-09-23T00:00:00Z
date_updated: 2023-02-21T10:09:21Z
day: '23'
doi: 10.1002/anie.201303528
extern: '1'
intvolume: '        52'
issue: '39'
language:
- iso: eng
month: '09'
oa_version: None
page: 10241-10244
publication: Angewandte Chemie International Edition
publication_identifier:
  eissn:
  - 1521-3773
  issn:
  - 1433-7851
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'In situ generation of diimide from hydrazine and oxygen: Continuous-flow transfer
  hydrogenation of olefins'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 52
year: '2013'
...
---
_id: '11960'
abstract:
- lang: eng
  text: It's not magic! The effects observed in microwave-irradiated chemical transformations
    can in most cases be rationalized by purely bulk thermal phenomena associated
    with rapid heating to elevated temperatures. As discussed in this Essay, the existence
    of so-called nonthermal or specific microwave effects is highly doubtful.
article_processing_charge: No
article_type: letter_note
author:
- first_name: C. Oliver
  full_name: Kappe, C. Oliver
  last_name: Kappe
- first_name: Bartholomäus
  full_name: Pieber, Bartholomäus
  id: 93e5e5b2-0da6-11ed-8a41-af589a024726
  last_name: Pieber
  orcid: 0000-0001-8689-388X
- first_name: Doris
  full_name: Dallinger, Doris
  last_name: Dallinger
citation:
  ama: 'Kappe CO, Pieber B, Dallinger D. Microwave effects in organic synthesis: Myth
    or reality? <i>Angewandte Chemie International Edition</i>. 2013;52(4):1088-1094.
    doi:<a href="https://doi.org/10.1002/anie.201204103">10.1002/anie.201204103</a>'
  apa: 'Kappe, C. O., Pieber, B., &#38; Dallinger, D. (2013). Microwave effects in
    organic synthesis: Myth or reality? <i>Angewandte Chemie International Edition</i>.
    Wiley. <a href="https://doi.org/10.1002/anie.201204103">https://doi.org/10.1002/anie.201204103</a>'
  chicago: 'Kappe, C. Oliver, Bartholomäus Pieber, and Doris Dallinger. “Microwave
    Effects in Organic Synthesis: Myth or Reality?” <i>Angewandte Chemie International
    Edition</i>. Wiley, 2013. <a href="https://doi.org/10.1002/anie.201204103">https://doi.org/10.1002/anie.201204103</a>.'
  ieee: 'C. O. Kappe, B. Pieber, and D. Dallinger, “Microwave effects in organic synthesis:
    Myth or reality?,” <i>Angewandte Chemie International Edition</i>, vol. 52, no.
    4. Wiley, pp. 1088–1094, 2013.'
  ista: 'Kappe CO, Pieber B, Dallinger D. 2013. Microwave effects in organic synthesis:
    Myth or reality? Angewandte Chemie International Edition. 52(4), 1088–1094.'
  mla: 'Kappe, C. Oliver, et al. “Microwave Effects in Organic Synthesis: Myth or
    Reality?” <i>Angewandte Chemie International Edition</i>, vol. 52, no. 4, Wiley,
    2013, pp. 1088–94, doi:<a href="https://doi.org/10.1002/anie.201204103">10.1002/anie.201204103</a>.'
  short: C.O. Kappe, B. Pieber, D. Dallinger, Angewandte Chemie International Edition
    52 (2013) 1088–1094.
date_created: 2022-08-24T11:05:04Z
date_published: 2013-01-21T00:00:00Z
date_updated: 2023-02-21T10:09:26Z
day: '21'
doi: 10.1002/anie.201204103
extern: '1'
intvolume: '        52'
issue: '4'
language:
- iso: eng
month: '01'
oa_version: None
page: 1088-1094
publication: Angewandte Chemie International Edition
publication_identifier:
  eissn:
  - 1521-3773
  issn:
  - 1433-7851
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Microwave effects in organic synthesis: Myth or reality?'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 52
year: '2013'
...
---
_id: '11973'
abstract:
- lang: eng
  text: The use of high-temperature/pressure gas–liquid continuous flow conditions
    dramatically enhances the iron-catalyzed aerobic oxidation of 2-benzylpyridines
    to their corresponding ketones. Pressurized air serves as a readily available
    oxygen source and propylene carbonate as a green solvent in this radically intensified
    preparation of synthetically valuable 2-aroylpyridines.
article_processing_charge: No
article_type: letter_note
author:
- first_name: Bartholomäus
  full_name: Pieber, Bartholomäus
  id: 93e5e5b2-0da6-11ed-8a41-af589a024726
  last_name: Pieber
  orcid: 0000-0001-8689-388X
- first_name: C. Oliver
  full_name: Kappe, C. Oliver
  last_name: Kappe
citation:
  ama: Pieber B, Kappe CO. Direct aerobic oxidation of 2-benzylpyridines in a gas-liquid
    continuous-flow regime using propylene carbonate as a solvent. <i>Green Chemistry</i>.
    2013;15(2):320-324. doi:<a href="https://doi.org/10.1039/c2gc36896j">10.1039/c2gc36896j</a>
  apa: Pieber, B., &#38; Kappe, C. O. (2013). Direct aerobic oxidation of 2-benzylpyridines
    in a gas-liquid continuous-flow regime using propylene carbonate as a solvent.
    <i>Green Chemistry</i>. Royal Society of Chemistry. <a href="https://doi.org/10.1039/c2gc36896j">https://doi.org/10.1039/c2gc36896j</a>
  chicago: Pieber, Bartholomäus, and C. Oliver Kappe. “Direct Aerobic Oxidation of
    2-Benzylpyridines in a Gas-Liquid Continuous-Flow Regime Using Propylene Carbonate
    as a Solvent.” <i>Green Chemistry</i>. Royal Society of Chemistry, 2013. <a href="https://doi.org/10.1039/c2gc36896j">https://doi.org/10.1039/c2gc36896j</a>.
  ieee: B. Pieber and C. O. Kappe, “Direct aerobic oxidation of 2-benzylpyridines
    in a gas-liquid continuous-flow regime using propylene carbonate as a solvent,”
    <i>Green Chemistry</i>, vol. 15, no. 2. Royal Society of Chemistry, pp. 320–324,
    2013.
  ista: Pieber B, Kappe CO. 2013. Direct aerobic oxidation of 2-benzylpyridines in
    a gas-liquid continuous-flow regime using propylene carbonate as a solvent. Green
    Chemistry. 15(2), 320–324.
  mla: Pieber, Bartholomäus, and C. Oliver Kappe. “Direct Aerobic Oxidation of 2-Benzylpyridines
    in a Gas-Liquid Continuous-Flow Regime Using Propylene Carbonate as a Solvent.”
    <i>Green Chemistry</i>, vol. 15, no. 2, Royal Society of Chemistry, 2013, pp.
    320–24, doi:<a href="https://doi.org/10.1039/c2gc36896j">10.1039/c2gc36896j</a>.
  short: B. Pieber, C.O. Kappe, Green Chemistry 15 (2013) 320–324.
date_created: 2022-08-25T10:29:21Z
date_published: 2013-02-01T00:00:00Z
date_updated: 2023-02-21T10:09:54Z
day: '01'
doi: 10.1039/c2gc36896j
extern: '1'
intvolume: '        15'
issue: '2'
language:
- iso: eng
month: '02'
oa_version: None
page: 320-324
publication: Green Chemistry
publication_identifier:
  eissn:
  - 1463-9270
  issn:
  - 1463-9262
publication_status: published
publisher: Royal Society of Chemistry
quality_controlled: '1'
scopus_import: '1'
status: public
title: Direct aerobic oxidation of 2-benzylpyridines in a gas-liquid continuous-flow
  regime using propylene carbonate as a solvent
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2013'
...
---
_id: '2204'
abstract:
- lang: eng
  text: We introduce a new platform for quantum simulation of many-body systems based
    on nonspherical atoms or molecules with zero dipole moments but possessing a significant
    value of electric quadrupole moments. We consider a quadrupolar Fermi gas trapped
    in a 2D square optical lattice, and show that the peculiar symmetry and broad
    tunability of the quadrupole-quadrupole interaction results in a rich phase diagram
    encompassing unconventional BCS and charge density wave phases, and opens up a
    perspective to create a topological superfluid. Quadrupolar species, such as metastable
    alkaline-earth atoms and homonuclear molecules, are stable against chemical reactions
    and collapse and are readily available in experiment at high densities.
article_processing_charge: No
author:
- first_name: Satyan
  full_name: Bhongale, Satyan
  last_name: Bhongale
- first_name: Ludwig
  full_name: Mathey, Ludwig
  last_name: Mathey
- first_name: Erhai
  full_name: Zhao, Erhai
  last_name: Zhao
- first_name: Susanne
  full_name: Yelin, Susanne
  last_name: Yelin
- first_name: Mikhail
  full_name: Lemeshko, Mikhail
  id: 37CB05FA-F248-11E8-B48F-1D18A9856A87
  last_name: Lemeshko
  orcid: 0000-0002-6990-7802
citation:
  ama: Bhongale S, Mathey L, Zhao E, Yelin S, Lemeshko M. Quantum phases of quadrupolar
    fermi gases in optical lattices. <i>Physical Review Letters</i>. 2013;110(15).
    doi:<a href="https://doi.org/10.1103/PhysRevLett.110.155301">10.1103/PhysRevLett.110.155301</a>
  apa: Bhongale, S., Mathey, L., Zhao, E., Yelin, S., &#38; Lemeshko, M. (2013). Quantum
    phases of quadrupolar fermi gases in optical lattices. <i>Physical Review Letters</i>.
    American Physical Society. <a href="https://doi.org/10.1103/PhysRevLett.110.155301">https://doi.org/10.1103/PhysRevLett.110.155301</a>
  chicago: Bhongale, Satyan, Ludwig Mathey, Erhai Zhao, Susanne Yelin, and Mikhail
    Lemeshko. “Quantum Phases of Quadrupolar Fermi Gases in Optical Lattices.” <i>Physical
    Review Letters</i>. American Physical Society, 2013. <a href="https://doi.org/10.1103/PhysRevLett.110.155301">https://doi.org/10.1103/PhysRevLett.110.155301</a>.
  ieee: S. Bhongale, L. Mathey, E. Zhao, S. Yelin, and M. Lemeshko, “Quantum phases
    of quadrupolar fermi gases in optical lattices,” <i>Physical Review Letters</i>,
    vol. 110, no. 15. American Physical Society, 2013.
  ista: Bhongale S, Mathey L, Zhao E, Yelin S, Lemeshko M. 2013. Quantum phases of
    quadrupolar fermi gases in optical lattices. Physical Review Letters. 110(15).
  mla: Bhongale, Satyan, et al. “Quantum Phases of Quadrupolar Fermi Gases in Optical
    Lattices.” <i>Physical Review Letters</i>, vol. 110, no. 15, American Physical
    Society, 2013, doi:<a href="https://doi.org/10.1103/PhysRevLett.110.155301">10.1103/PhysRevLett.110.155301</a>.
  short: S. Bhongale, L. Mathey, E. Zhao, S. Yelin, M. Lemeshko, Physical Review Letters
    110 (2013).
date_created: 2018-12-11T11:56:18Z
date_published: 2013-04-08T00:00:00Z
date_updated: 2021-11-16T08:04:06Z
day: '08'
doi: 10.1103/PhysRevLett.110.155301
extern: '1'
intvolume: '       110'
issue: '15'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1211.3317
month: '04'
oa: 1
oa_version: None
publication: Physical Review Letters
publication_status: published
publisher: American Physical Society
publist_id: '4769'
related_material:
  link:
  - relation: erratum
    url: https://doi.org/10.1103/PhysRevLett.111.239901
status: public
title: Quantum phases of quadrupolar fermi gases in optical lattices
type: journal_article
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 110
year: '2013'
...
---
_id: '2205'
abstract:
- lang: eng
  text: The goal of the present article is to review the major developments that have
    led to the current understanding of molecule-field interactions and experimental
    methods for manipulating molecules with electromagnetic fields. Molecule-field
    interactions are at the core of several, seemingly distinct areas of molecular
    physics. This is reflected in the organisation of this article, which includes
    sections on field control of molecular beams, external field traps for cold molecules,
    control of molecular orientation and molecular alignment, manipulation of molecules
    by non-conservative forces, ultracold molecules and ultracold chemistry, controlled
    many-body phenomena, entanglement of molecules and dipole arrays, and stability
    of molecular systems in high-frequency super-intense laser fields. The article
    contains 852 references.
acknowledgement: National Science Foundation; Natural Sciences and Engineering Research
  Council of Canada
author:
- first_name: Mikhail
  full_name: Mikhail Lemeshko
  id: 37CB05FA-F248-11E8-B48F-1D18A9856A87
  last_name: Lemeshko
  orcid: 0000-0002-6990-7802
- first_name: Roman
  full_name: Krems, Roman V
  last_name: Krems
- first_name: John
  full_name: Doyle, John M
  last_name: Doyle
- first_name: Sabre
  full_name: Kais, Sabre
  last_name: Kais
citation:
  ama: Lemeshko M, Krems R, Doyle J, Kais S. Manipulation of molecules with electromagnetic
    fields. <i>Molecular Physics</i>. 2013;111(12-13):1648-1682. doi:<a href="https://doi.org/10.1080/00268976.2013.813595">10.1080/00268976.2013.813595</a>
  apa: Lemeshko, M., Krems, R., Doyle, J., &#38; Kais, S. (2013). Manipulation of
    molecules with electromagnetic fields. <i>Molecular Physics</i>. Taylor &#38;
    Francis. <a href="https://doi.org/10.1080/00268976.2013.813595">https://doi.org/10.1080/00268976.2013.813595</a>
  chicago: Lemeshko, Mikhail, Roman Krems, John Doyle, and Sabre Kais. “Manipulation
    of Molecules with Electromagnetic Fields.” <i>Molecular Physics</i>. Taylor &#38;
    Francis, 2013. <a href="https://doi.org/10.1080/00268976.2013.813595">https://doi.org/10.1080/00268976.2013.813595</a>.
  ieee: M. Lemeshko, R. Krems, J. Doyle, and S. Kais, “Manipulation of molecules with
    electromagnetic fields,” <i>Molecular Physics</i>, vol. 111, no. 12–13. Taylor
    &#38; Francis, pp. 1648–1682, 2013.
  ista: Lemeshko M, Krems R, Doyle J, Kais S. 2013. Manipulation of molecules with
    electromagnetic fields. Molecular Physics. 111(12–13), 1648–1682.
  mla: Lemeshko, Mikhail, et al. “Manipulation of Molecules with Electromagnetic Fields.”
    <i>Molecular Physics</i>, vol. 111, no. 12–13, Taylor &#38; Francis, 2013, pp.
    1648–82, doi:<a href="https://doi.org/10.1080/00268976.2013.813595">10.1080/00268976.2013.813595</a>.
  short: M. Lemeshko, R. Krems, J. Doyle, S. Kais, Molecular Physics 111 (2013) 1648–1682.
date_created: 2018-12-11T11:56:19Z
date_published: 2013-07-01T00:00:00Z
date_updated: 2020-07-14T12:45:32Z
day: '01'
doi: 10.1080/00268976.2013.813595
extern: 1
intvolume: '       111'
issue: 12-13
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1306.0912
month: '07'
oa: 1
page: 1648 - 1682
publication: Molecular Physics
publication_status: published
publisher: Taylor & Francis
publist_id: '4768'
quality_controlled: 0
status: public
title: Manipulation of molecules with electromagnetic fields
type: review
volume: 111
year: '2013'
...
---
_id: '2206'
abstract:
- lang: eng
  text: Magnetic impurities embedded in inert solids can exhibit long coherence times
    and interact with one another via their intrinsic anisotropic dipolar interaction.
    We argue that, as a consequence of these properties, disordered ensembles of magnetic
    impurities provide an effective platform for realizing a controllable, tunable
    version of the dipolar quantum spin glass seen in LiHoxY1-xF4. Specifically, we
    propose and analyze a system composed of dysprosium atoms embedded in solid helium.
    We describe the phase diagram of the system and discuss the realizability and
    detectability of the quantum spin glass and antiglass phases.
author:
- first_name: Mikhail
  full_name: Mikhail Lemeshko
  id: 37CB05FA-F248-11E8-B48F-1D18A9856A87
  last_name: Lemeshko
  orcid: 0000-0002-6990-7802
- first_name: Norman
  full_name: Yao, Norman Y
  last_name: Yao
- first_name: Alexey
  full_name: Gorshkov, Alexey V
  last_name: Gorshkov
- first_name: Hendrik
  full_name: Weimer, Hendrik
  last_name: Weimer
- first_name: Steven
  full_name: Bennett, Steven D
  last_name: Bennett
- first_name: Takamasa
  full_name: Momose, Takamasa
  last_name: Momose
- first_name: Sarang
  full_name: Gopalakrishnan, Sarang
  last_name: Gopalakrishnan
citation:
  ama: Lemeshko M, Yao N, Gorshkov A, et al. Controllable quantum spin glasses with
    magnetic impurities embedded in quantum solids. <i>Physical Review B - Condensed
    Matter and Materials Physics</i>. 2013;88(1). doi:<a href="https://doi.org/10.1103/PhysRevB.88.014426">10.1103/PhysRevB.88.014426</a>
  apa: Lemeshko, M., Yao, N., Gorshkov, A., Weimer, H., Bennett, S., Momose, T., &#38;
    Gopalakrishnan, S. (2013). Controllable quantum spin glasses with magnetic impurities
    embedded in quantum solids. <i>Physical Review B - Condensed Matter and Materials
    Physics</i>. American Physical Society. <a href="https://doi.org/10.1103/PhysRevB.88.014426">https://doi.org/10.1103/PhysRevB.88.014426</a>
  chicago: Lemeshko, Mikhail, Norman Yao, Alexey Gorshkov, Hendrik Weimer, Steven
    Bennett, Takamasa Momose, and Sarang Gopalakrishnan. “Controllable Quantum Spin
    Glasses with Magnetic Impurities Embedded in Quantum Solids.” <i>Physical Review
    B - Condensed Matter and Materials Physics</i>. American Physical Society, 2013.
    <a href="https://doi.org/10.1103/PhysRevB.88.014426">https://doi.org/10.1103/PhysRevB.88.014426</a>.
  ieee: M. Lemeshko <i>et al.</i>, “Controllable quantum spin glasses with magnetic
    impurities embedded in quantum solids,” <i>Physical Review B - Condensed Matter
    and Materials Physics</i>, vol. 88, no. 1. American Physical Society, 2013.
  ista: Lemeshko M, Yao N, Gorshkov A, Weimer H, Bennett S, Momose T, Gopalakrishnan
    S. 2013. Controllable quantum spin glasses with magnetic impurities embedded in
    quantum solids. Physical Review B - Condensed Matter and Materials Physics. 88(1).
  mla: Lemeshko, Mikhail, et al. “Controllable Quantum Spin Glasses with Magnetic
    Impurities Embedded in Quantum Solids.” <i>Physical Review B - Condensed Matter
    and Materials Physics</i>, vol. 88, no. 1, American Physical Society, 2013, doi:<a
    href="https://doi.org/10.1103/PhysRevB.88.014426">10.1103/PhysRevB.88.014426</a>.
  short: M. Lemeshko, N. Yao, A. Gorshkov, H. Weimer, S. Bennett, T. Momose, S. Gopalakrishnan,
    Physical Review B - Condensed Matter and Materials Physics 88 (2013).
date_created: 2018-12-11T11:56:19Z
date_published: 2013-07-24T00:00:00Z
date_updated: 2021-01-12T06:55:59Z
day: '24'
doi: 10.1103/PhysRevB.88.014426
extern: 1
intvolume: '        88'
issue: '1'
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1307.1130
month: '07'
oa: 1
publication: Physical Review B - Condensed Matter and Materials Physics
publication_status: published
publisher: American Physical Society
publist_id: '4767'
quality_controlled: 0
status: public
title: Controllable quantum spin glasses with magnetic impurities embedded in quantum
  solids
type: journal_article
volume: 88
year: '2013'
...
---
_id: '2207'
abstract:
- lang: eng
  text: The formation of molecules and supramolecular structures results from bonding
    by conservative forces acting among electrons and nuclei and giving rise to equilibrium
    configurations defined by minima of the interaction potential. Here we show that
    bonding can also occur by the non-conservative forces responsible for interaction-induced
    coherent population trapping. The bound state arises in a dissipative process
    and manifests itself as a stationary state at a preordained interatomic distance.
    Remarkably, such a dissipative bonding is present even when the interactions among
    the atoms are purely repulsive. The dissipative bound states can be created and
    studied spectroscopically in present-day experiments with ultracold atoms or molecules
    and can potentially serve for cooling strongly interacting quantum gases.
author:
- first_name: Mikhail
  full_name: Mikhail Lemeshko
  id: 37CB05FA-F248-11E8-B48F-1D18A9856A87
  last_name: Lemeshko
  orcid: 0000-0002-6990-7802
- first_name: Hendrik
  full_name: Weimer, Hendrik
  last_name: Weimer
citation:
  ama: Lemeshko M, Weimer H. Dissipative binding of atoms by non-conservative forces.
    <i>Nature Communications</i>. 2013;4. doi:<a href="https://doi.org/10.1038/ncomms3230">10.1038/ncomms3230</a>
  apa: Lemeshko, M., &#38; Weimer, H. (2013). Dissipative binding of atoms by non-conservative
    forces. <i>Nature Communications</i>. Nature Publishing Group. <a href="https://doi.org/10.1038/ncomms3230">https://doi.org/10.1038/ncomms3230</a>
  chicago: Lemeshko, Mikhail, and Hendrik Weimer. “Dissipative Binding of Atoms by
    Non-Conservative Forces.” <i>Nature Communications</i>. Nature Publishing Group,
    2013. <a href="https://doi.org/10.1038/ncomms3230">https://doi.org/10.1038/ncomms3230</a>.
  ieee: M. Lemeshko and H. Weimer, “Dissipative binding of atoms by non-conservative
    forces,” <i>Nature Communications</i>, vol. 4. Nature Publishing Group, 2013.
  ista: Lemeshko M, Weimer H. 2013. Dissipative binding of atoms by non-conservative
    forces. Nature Communications. 4.
  mla: Lemeshko, Mikhail, and Hendrik Weimer. “Dissipative Binding of Atoms by Non-Conservative
    Forces.” <i>Nature Communications</i>, vol. 4, Nature Publishing Group, 2013,
    doi:<a href="https://doi.org/10.1038/ncomms3230">10.1038/ncomms3230</a>.
  short: M. Lemeshko, H. Weimer, Nature Communications 4 (2013).
date_created: 2018-12-11T11:56:20Z
date_published: 2013-07-30T00:00:00Z
date_updated: 2021-01-12T06:55:59Z
day: '30'
doi: 10.1038/ncomms3230
extern: 1
intvolume: '         4'
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1211.4035
month: '07'
oa: 1
publication: Nature Communications
publication_status: published
publisher: Nature Publishing Group
publist_id: '4766'
quality_controlled: 0
status: public
title: Dissipative binding of atoms by non-conservative forces
type: journal_article
volume: 4
year: '2013'
...
---
_id: '2209'
abstract:
- lang: eng
  text: "A straight skeleton is a well-known geometric structure, and several algorithms
    exist to construct the straight skeleton for a given polygon or planar straight-line
    graph. In this paper, we ask the reverse question: Given the straight skeleton
    (in form of a planar straight-line graph, with some rays to infinity), can we
    reconstruct a planar straight-line graph for which this was the straight skeleton?
    We show how to reduce this problem to the problem of finding a line that intersects
    a set of convex polygons. We can find these convex polygons and all such lines
    in $O(nlog n)$ time in the Real RAM computer model, where $n$ denotes the number
    of edges of the input graph. We also explain how our approach can be used for
    recognizing Voronoi diagrams of points, thereby completing a partial solution
    provided by Ash and Bolker in 1985.\r\n"
alternative_title:
- '2013 10th International Symposium on Voronoi Diagrams in Science and Engineering
  (ISVD 2013) '
article_processing_charge: No
author:
- first_name: Therese
  full_name: Biedl, Therese
  last_name: Biedl
- first_name: Martin
  full_name: Held, Martin
  last_name: Held
- first_name: Stefan
  full_name: Huber, Stefan
  id: 4700A070-F248-11E8-B48F-1D18A9856A87
  last_name: Huber
  orcid: 0000-0002-8871-5814
citation:
  ama: 'Biedl T, Held M, Huber S. Recognizing straight skeletons and Voronoi diagrams
    and reconstructing their input. In: IEEE; 2013:37-46. doi:<a href="https://doi.org/10.1109/ISVD.2013.11">10.1109/ISVD.2013.11</a>'
  apa: 'Biedl, T., Held, M., &#38; Huber, S. (2013). Recognizing straight skeletons
    and Voronoi diagrams and reconstructing their input (pp. 37–46). Presented at
    the ISVD: Voronoi Diagrams in Science and Engineering, St. Petersburg, Russia:
    IEEE. <a href="https://doi.org/10.1109/ISVD.2013.11">https://doi.org/10.1109/ISVD.2013.11</a>'
  chicago: Biedl, Therese, Martin Held, and Stefan Huber. “Recognizing Straight Skeletons
    and Voronoi Diagrams and Reconstructing Their Input,” 37–46. IEEE, 2013. <a href="https://doi.org/10.1109/ISVD.2013.11">https://doi.org/10.1109/ISVD.2013.11</a>.
  ieee: 'T. Biedl, M. Held, and S. Huber, “Recognizing straight skeletons and Voronoi
    diagrams and reconstructing their input,” presented at the ISVD: Voronoi Diagrams
    in Science and Engineering, St. Petersburg, Russia, 2013, pp. 37–46.'
  ista: 'Biedl T, Held M, Huber S. 2013. Recognizing straight skeletons and Voronoi
    diagrams and reconstructing their input. ISVD: Voronoi Diagrams in Science and
    Engineering, 2013 10th International Symposium on Voronoi Diagrams in Science
    and Engineering (ISVD 2013) , , 37–46.'
  mla: Biedl, Therese, et al. <i>Recognizing Straight Skeletons and Voronoi Diagrams
    and Reconstructing Their Input</i>. IEEE, 2013, pp. 37–46, doi:<a href="https://doi.org/10.1109/ISVD.2013.11">10.1109/ISVD.2013.11</a>.
  short: T. Biedl, M. Held, S. Huber, in:, IEEE, 2013, pp. 37–46.
conference:
  end_date: 2013-07-10
  location: St. Petersburg, Russia
  name: 'ISVD: Voronoi Diagrams in Science and Engineering'
  start_date: 2013-07-08
date_created: 2018-12-11T11:56:20Z
date_published: 2013-12-01T00:00:00Z
date_updated: 2025-09-29T14:30:56Z
day: '01'
department:
- _id: HeEd
doi: 10.1109/ISVD.2013.11
external_id:
  isi:
  - '000430602800007'
isi: 1
language:
- iso: eng
month: '12'
oa_version: None
page: 37 - 46
publication_identifier:
  eisbn:
  - '978-0-7695-5037-4 '
publication_status: published
publisher: IEEE
publist_id: '4763'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Recognizing straight skeletons and Voronoi diagrams and reconstructing their
  input
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2013'
...
---
_id: '2210'
abstract:
- lang: eng
  text: 'A straight skeleton is a well-known geometric structure, and several algorithms
    exist to construct the straight skeleton for a given polygon. In this paper, we
    ask the reverse question: Given the straight skeleton (in form of a tree with
    a drawing in the plane, but with the exact position of the leaves unspecified),
    can we reconstruct the polygon? We show that in most cases there exists at most
    one polygon; in the remaining case there is an infinite number of polygons determined
    by one angle that can range in an interval. We can find this (set of) polygon(s)
    in linear time in the Real RAM computer model.'
author:
- first_name: Therese
  full_name: Biedl, Therese
  last_name: Biedl
- first_name: Martin
  full_name: Held, Martin
  last_name: Held
- first_name: Stefan
  full_name: Huber, Stefan
  id: 4700A070-F248-11E8-B48F-1D18A9856A87
  last_name: Huber
  orcid: 0000-0002-8871-5814
citation:
  ama: 'Biedl T, Held M, Huber S. Reconstructing polygons from embedded straight skeletons.
    In: <i>29th European Workshop on Computational Geometry</i>. TU Braunschweig;
    2013:95-98.'
  apa: 'Biedl, T., Held, M., &#38; Huber, S. (2013). Reconstructing polygons from
    embedded straight skeletons. In <i>29th European Workshop on Computational Geometry</i>
    (pp. 95–98). Braunschweig, Germany: TU Braunschweig.'
  chicago: Biedl, Therese, Martin Held, and Stefan Huber. “Reconstructing Polygons
    from Embedded Straight Skeletons.” In <i>29th European Workshop on Computational
    Geometry</i>, 95–98. TU Braunschweig, 2013.
  ieee: T. Biedl, M. Held, and S. Huber, “Reconstructing polygons from embedded straight
    skeletons,” in <i>29th European Workshop on Computational Geometry</i>, Braunschweig,
    Germany, 2013, pp. 95–98.
  ista: 'Biedl T, Held M, Huber S. 2013. Reconstructing polygons from embedded straight
    skeletons. 29th European Workshop on Computational Geometry. EuroCG: European
    Workshop on Computational Geometry, 95–98.'
  mla: Biedl, Therese, et al. “Reconstructing Polygons from Embedded Straight Skeletons.”
    <i>29th European Workshop on Computational Geometry</i>, TU Braunschweig, 2013,
    pp. 95–98.
  short: T. Biedl, M. Held, S. Huber, in:, 29th European Workshop on Computational
    Geometry, TU Braunschweig, 2013, pp. 95–98.
conference:
  end_date: 2013-03-20
  location: Braunschweig, Germany
  name: 'EuroCG: European Workshop on Computational Geometry'
  start_date: 2013-03-17
date_created: 2018-12-11T11:56:21Z
date_published: 2013-03-01T00:00:00Z
date_updated: 2021-01-12T06:56:00Z
day: '01'
department:
- _id: HeEd
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://www.ibr.cs.tu-bs.de/alg/eurocg13/booklet_eurocg13.pdf
month: '03'
oa: 1
oa_version: Submitted Version
page: 95 - 98
publication: 29th European Workshop on Computational Geometry
publication_status: published
publisher: TU Braunschweig
publist_id: '4762'
status: public
title: Reconstructing polygons from embedded straight skeletons
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2237'
abstract:
- lang: eng
  text: We describe new extensions of the Vampire theorem prover for computing tree
    interpolants. These extensions generalize Craig interpolation in Vampire, and
    can also be used to derive sequence interpolants. We evaluated our implementation
    on a large number of examples over the theory of linear integer arithmetic and
    integer-indexed arrays, with and without quantifiers. When compared to other methods,
    our experiments show that some examples could only be solved by our implementation.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Régis
  full_name: Blanc, Régis
  last_name: Blanc
- first_name: Ashutosh
  full_name: Gupta, Ashutosh
  id: 335E5684-F248-11E8-B48F-1D18A9856A87
  last_name: Gupta
- first_name: Laura
  full_name: Kovács, Laura
  last_name: Kovács
- first_name: Bernhard
  full_name: Kragl, Bernhard
  id: 320FC952-F248-11E8-B48F-1D18A9856A87
  last_name: Kragl
  orcid: 0000-0001-7745-9117
citation:
  ama: Blanc R, Gupta A, Kovács L, Kragl B. Tree interpolation in Vampire. 2013;8312:173-181.
    doi:<a href="https://doi.org/10.1007/978-3-642-45221-5_13">10.1007/978-3-642-45221-5_13</a>
  apa: 'Blanc, R., Gupta, A., Kovács, L., &#38; Kragl, B. (2013). Tree interpolation
    in Vampire. Presented at the LPAR: Logic for Programming, Artificial Intelligence,
    and Reasoning, Stellenbosch, South Africa: Springer. <a href="https://doi.org/10.1007/978-3-642-45221-5_13">https://doi.org/10.1007/978-3-642-45221-5_13</a>'
  chicago: Blanc, Régis, Ashutosh Gupta, Laura Kovács, and Bernhard Kragl. “Tree Interpolation
    in Vampire.” Lecture Notes in Computer Science. Springer, 2013. <a href="https://doi.org/10.1007/978-3-642-45221-5_13">https://doi.org/10.1007/978-3-642-45221-5_13</a>.
  ieee: R. Blanc, A. Gupta, L. Kovács, and B. Kragl, “Tree interpolation in Vampire,”
    vol. 8312. Springer, pp. 173–181, 2013.
  ista: Blanc R, Gupta A, Kovács L, Kragl B. 2013. Tree interpolation in Vampire.
    8312, 173–181.
  mla: Blanc, Régis, et al. <i>Tree Interpolation in Vampire</i>. Vol. 8312, Springer,
    2013, pp. 173–81, doi:<a href="https://doi.org/10.1007/978-3-642-45221-5_13">10.1007/978-3-642-45221-5_13</a>.
  short: R. Blanc, A. Gupta, L. Kovács, B. Kragl, 8312 (2013) 173–181.
conference:
  end_date: 2013-12-19
  location: Stellenbosch, South Africa
  name: 'LPAR: Logic for Programming, Artificial Intelligence, and Reasoning'
  start_date: 2013-12-14
date_created: 2018-12-11T11:56:29Z
date_published: 2013-01-14T00:00:00Z
date_updated: 2020-08-11T10:09:42Z
day: '14'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-642-45221-5_13
file:
- access_level: open_access
  checksum: 9cebaafca032e6769d273f393305c705
  content_type: application/pdf
  creator: dernst
  date_created: 2020-05-15T11:10:40Z
  date_updated: 2020-07-14T12:45:34Z
  file_id: '7858'
  file_name: 2013_LPAR_Blanc.pdf
  file_size: 279206
  relation: main_file
file_date_updated: 2020-07-14T12:45:34Z
has_accepted_license: '1'
intvolume: '      8312'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 173 - 181
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: '4724'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Tree interpolation in Vampire
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8312
year: '2013'
...
---
_id: '2238'
abstract:
- lang: eng
  text: "We study the problem of achieving a given value in Markov decision processes
    (MDPs) with several independent discounted reward objectives. We consider a generalised
    version of discounted reward objectives, in which the amount of discounting depends
    on the states visited and on the objective. This definition extends the usual
    definition of discounted reward, and allows to capture the systems in which the
    value of different commodities diminish at different and variable rates.\r\n\r\nWe
    establish results for two prominent subclasses of the problem, namely state-discount
    models where the discount factors are only dependent on the state of the MDP (and
    independent of the objective), and reward-discount models where they are only
    dependent on the objective (but not on the state of the MDP). For the state-discount
    models we use a straightforward reduction to expected total reward and show that
    the problem whether a value is achievable can be solved in polynomial time. For
    the reward-discount model we show that memory and randomisation of the strategies
    are required, but nevertheless that the problem is decidable and it is sufficient
    to consider strategies which after a certain number of steps behave in a memoryless
    way.\r\n\r\nFor the general case, we show that when restricted to graphs (i.e.
    MDPs with no randomisation), pure strategies and discount factors of the form
    1/n where n is an integer, the problem is in PSPACE and finite memory suffices
    for achieving a given value. We also show that when the discount factors are not
    of the form 1/n, the memory required by a strategy can be infinite.\r\n"
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
- first_name: Vojtěch
  full_name: Forejt, Vojtěch
  last_name: Forejt
- first_name: Dominik
  full_name: Wojtczak, Dominik
  last_name: Wojtczak
citation:
  ama: Chatterjee K, Forejt V, Wojtczak D. Multi-objective discounted reward verification
    in graphs and MDPs. 2013;8312:228-242. doi:<a href="https://doi.org/10.1007/978-3-642-45221-5_17">10.1007/978-3-642-45221-5_17</a>
  apa: 'Chatterjee, K., Forejt, V., &#38; Wojtczak, D. (2013). Multi-objective discounted
    reward verification in graphs and MDPs. Presented at the LPAR: Logic for Programming,
    Artificial Intelligence, and Reasoning, Stellenbosch, South Africa: Springer.
    <a href="https://doi.org/10.1007/978-3-642-45221-5_17">https://doi.org/10.1007/978-3-642-45221-5_17</a>'
  chicago: Chatterjee, Krishnendu, Vojtěch Forejt, and Dominik Wojtczak. “Multi-Objective
    Discounted Reward Verification in Graphs and MDPs.” Lecture Notes in Computer
    Science. Springer, 2013. <a href="https://doi.org/10.1007/978-3-642-45221-5_17">https://doi.org/10.1007/978-3-642-45221-5_17</a>.
  ieee: K. Chatterjee, V. Forejt, and D. Wojtczak, “Multi-objective discounted reward
    verification in graphs and MDPs,” vol. 8312. Springer, pp. 228–242, 2013.
  ista: Chatterjee K, Forejt V, Wojtczak D. 2013. Multi-objective discounted reward
    verification in graphs and MDPs. 8312, 228–242.
  mla: Chatterjee, Krishnendu, et al. <i>Multi-Objective Discounted Reward Verification
    in Graphs and MDPs</i>. Vol. 8312, Springer, 2013, pp. 228–42, doi:<a href="https://doi.org/10.1007/978-3-642-45221-5_17">10.1007/978-3-642-45221-5_17</a>.
  short: K. Chatterjee, V. Forejt, D. Wojtczak, 8312 (2013) 228–242.
conference:
  end_date: 2013-12-19
  location: Stellenbosch, South Africa
  name: 'LPAR: Logic for Programming, Artificial Intelligence, and Reasoning'
  start_date: 2013-12-14
date_created: 2018-12-11T11:56:30Z
date_published: 2013-12-01T00:00:00Z
date_updated: 2020-08-11T10:09:42Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-642-45221-5_17
ec_funded: 1
intvolume: '      8312'
language:
- iso: eng
month: '12'
oa_version: None
page: 228 - 242
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
publication_status: published
publisher: Springer
publist_id: '4723'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Multi-objective discounted reward verification in graphs and MDPs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8312
year: '2013'
...
---
_id: '2243'
abstract:
- lang: eng
  text: We show that modal logic over universally first-order definable classes of
    transitive frames is decidable. More precisely, let K be an arbitrary class of
    transitive Kripke frames definable by a universal first-order sentence. We show
    that the global and finite global satisfiability problems of modal logic over
    K are decidable in NP, regardless of choice of K. We also show that the local
    satisfiability and the finite local satisfiability problems of modal logic over
    K are decidable in NEXPTIME.
alternative_title:
- LIPIcs
author:
- first_name: Jakub
  full_name: Michaliszyn, Jakub
  last_name: Michaliszyn
- first_name: Jan
  full_name: Otop, Jan
  id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
  last_name: Otop
citation:
  ama: Michaliszyn J, Otop J. Elementary modal logics over transitive structures.
    2013;23:563-577. doi:<a href="https://doi.org/10.4230/LIPIcs.CSL.2013.563">10.4230/LIPIcs.CSL.2013.563</a>
  apa: 'Michaliszyn, J., &#38; Otop, J. (2013). Elementary modal logics over transitive
    structures. Presented at the CSL: Computer Science Logic, Torino, Italy: Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.CSL.2013.563">https://doi.org/10.4230/LIPIcs.CSL.2013.563</a>'
  chicago: Michaliszyn, Jakub, and Jan Otop. “Elementary Modal Logics over Transitive
    Structures.” Leibniz International Proceedings in Informatics. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2013. <a href="https://doi.org/10.4230/LIPIcs.CSL.2013.563">https://doi.org/10.4230/LIPIcs.CSL.2013.563</a>.
  ieee: J. Michaliszyn and J. Otop, “Elementary modal logics over transitive structures,”
    vol. 23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 563–577, 2013.
  ista: Michaliszyn J, Otop J. 2013. Elementary modal logics over transitive structures.
    23, 563–577.
  mla: Michaliszyn, Jakub, and Jan Otop. <i>Elementary Modal Logics over Transitive
    Structures</i>. Vol. 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013,
    pp. 563–77, doi:<a href="https://doi.org/10.4230/LIPIcs.CSL.2013.563">10.4230/LIPIcs.CSL.2013.563</a>.
  short: J. Michaliszyn, J. Otop, 23 (2013) 563–577.
conference:
  end_date: 2013-09-05
  location: Torino, Italy
  name: 'CSL: Computer Science Logic'
  start_date: 2013-09-02
date_created: 2018-12-11T11:56:32Z
date_published: 2013-09-01T00:00:00Z
date_updated: 2020-08-11T10:09:42Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.CSL.2013.563
ec_funded: 1
file:
- access_level: open_access
  checksum: e0732e73a8b1e39483df7717d53e3e35
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:12:11Z
  date_updated: 2020-07-14T12:45:34Z
  file_id: '4929'
  file_name: IST-2016-136-v1+2_39.pdf
  file_size: 454915
  relation: main_file
file_date_updated: 2020-07-14T12:45:34Z
has_accepted_license: '1'
intvolume: '        23'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 563 - 577
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '267989'
  name: Quantitative Reactive Modeling
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '4708'
pubrep_id: '136'
quality_controlled: '1'
scopus_import: 1
series_title: Leibniz International Proceedings in Informatics
status: public
title: Elementary modal logics over transitive structures
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 23
year: '2013'
...
---
_id: '2244'
abstract:
- lang: eng
  text: 'We consider two systems (α1,...,αm) and (β1,...,βn) of curves drawn on a
    compact two-dimensional surface ℳ with boundary. Each αi and each βj is either
    an arc meeting the boundary of ℳ at its two endpoints, or a closed curve. The
    αi are pairwise disjoint except for possibly sharing endpoints, and similarly
    for the βj. We want to &quot;untangle&quot; the βj from the αi by a self-homeomorphism
    of ℳ; more precisely, we seek an homeomorphism φ: ℳ → ℳ fixing the boundary of
    ℳ pointwise such that the total number of crossings of the αi with the φ(βj) is
    as small as possible. This problem is motivated by an application in the algorithmic
    theory of embeddings and 3-manifolds. We prove that if ℳ is planar, i.e., a sphere
    with h ≥ 0 boundary components (&quot;holes&quot;), then O(mn) crossings can be
    achieved (independently of h), which is asymptotically tight, as an easy lower
    bound shows. In general, for an arbitrary (orientable or nonorientable) surface
    ℳ with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an
    O((m + n)4) upper bound, again independent of h and g. '
acknowledgement: We would like to thank the authors of [GHR13] for mak- ing a draft
  of their paper available to us, and, in particular, T. Huynh for an e-mail correspondence.
alternative_title:
- LNCS
arxiv: 1
author:
- first_name: Jiří
  full_name: Matoušek, Jiří
  last_name: Matoušek
- first_name: Eric
  full_name: Sedgwick, Eric
  last_name: Sedgwick
- first_name: Martin
  full_name: Tancer, Martin
  id: 38AC689C-F248-11E8-B48F-1D18A9856A87
  last_name: Tancer
  orcid: 0000-0002-1191-6714
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: Matoušek J, Sedgwick E, Tancer M, Wagner U. Untangling two systems of noncrossing
    curves. 2013;8242:472-483. doi:<a href="https://doi.org/10.1007/978-3-319-03841-4_41">10.1007/978-3-319-03841-4_41</a>
  apa: 'Matoušek, J., Sedgwick, E., Tancer, M., &#38; Wagner, U. (2013). Untangling
    two systems of noncrossing curves. Presented at the GD: Graph Drawing and Network
    Visualization, Bordeaux, France: Springer. <a href="https://doi.org/10.1007/978-3-319-03841-4_41">https://doi.org/10.1007/978-3-319-03841-4_41</a>'
  chicago: Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Untangling
    Two Systems of Noncrossing Curves.” Lecture Notes in Computer Science. Springer,
    2013. <a href="https://doi.org/10.1007/978-3-319-03841-4_41">https://doi.org/10.1007/978-3-319-03841-4_41</a>.
  ieee: J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Untangling two systems
    of noncrossing curves,” vol. 8242. Springer, pp. 472–483, 2013.
  ista: Matoušek J, Sedgwick E, Tancer M, Wagner U. 2013. Untangling two systems of
    noncrossing curves. 8242, 472–483.
  mla: Matoušek, Jiří, et al. <i>Untangling Two Systems of Noncrossing Curves</i>.
    Vol. 8242, Springer, 2013, pp. 472–83, doi:<a href="https://doi.org/10.1007/978-3-319-03841-4_41">10.1007/978-3-319-03841-4_41</a>.
  short: J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, 8242 (2013) 472–483.
conference:
  end_date: 2013-09-25
  location: Bordeaux, France
  name: 'GD: Graph Drawing and Network Visualization'
  start_date: 2013-09-23
date_created: 2018-12-11T11:56:32Z
date_published: 2013-09-01T00:00:00Z
date_updated: 2025-09-18T14:27:53Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/978-3-319-03841-4_41
external_id:
  arxiv:
  - '1302.6475'
intvolume: '      8242'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1302.6475
month: '09'
oa: 1
oa_version: Preprint
page: 472 - 483
project:
- _id: 25FA3206-B435-11E9-9278-68D0E5697425
  grant_number: PP00P2_138948
  name: 'Embeddings in Higher Dimensions: Algorithms and Combinatorics'
publication_status: published
publisher: Springer
publist_id: '4707'
quality_controlled: '1'
related_material:
  record:
  - id: '1411'
    relation: later_version
    status: public
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Untangling two systems of noncrossing curves
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8242
year: '2013'
...