2 Search Results for "Baptiste, Philippe"

Document
DOI: 10.4230/LIPIcs.AofA.2022.6
Random Partitions Under the Plancherel-Hurwitz Measure, High Genus Hurwitz Numbers and Maps

Authors: Guillaume Chapuy, Baptiste Louf, and Harriet Walsh

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

Abstract
We study the asymptotic behaviour of random integer partitions under a new probability law that we introduce, the Plancherel-Hurwitz measure. This distribution, which has a natural definition in terms of Young tableaux, is a deformation of the classical Plancherel measure. It appears naturally in the enumeration of Hurwitz maps, or equivalently transposition factorisations in symmetric groups. We study a regime in which the number of factors in the underlying factorisations grows linearly with the order of the group, and the corresponding maps are of high genus. We prove that the limiting behaviour exhibits a new, twofold, phenomenon: the first part becomes very large, while the rest of the partition has the standard Vershik-Kerov-Logan-Shepp limit shape. As a consequence, we obtain asymptotic estimates for unconnected Hurwitz numbers with linear Euler characteristic, which we use to study random Hurwitz maps in this regime. This result can also be interpreted as the return probability of the transposition random walk on the symmetric group after linearly many steps.
Cite as

Guillaume Chapuy, Baptiste Louf, and Harriet Walsh. Random Partitions Under the Plancherel-Hurwitz Measure, High Genus Hurwitz Numbers and Maps. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chapuy_et_al:LIPIcs.AofA.2022.6,
  author =	{Chapuy, Guillaume and Louf, Baptiste and Walsh, Harriet},
  title =	{{Random Partitions Under the Plancherel-Hurwitz Measure, High Genus Hurwitz Numbers and Maps}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{6:1--6:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.6},
  URN =		{urn:nbn:de:0030-drops-160921},
  doi =		{10.4230/LIPIcs.AofA.2022.6},
  annote =	{Keywords: Random partitions, limit shapes, transposition factorisations, map enumeration, Hurwitz numbers, RSK algorithm, giant components}
}
Document
DOI: 10.4230/DagSemProc.10071.8
Polynomial Time Algorithms for Minimum Energy Scheduling

Authors: Marek Chrobak, Philippe Baptiste, and Christoph Dürr

Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Abstract
The aim of power management policies is to reduce the amount of energy consumed by computer systems while maintaining satisfactory level of performance. One common method for saving energy is to simply suspend the system during the idle times. No energy is consumed in the suspend mode. However, the process of waking up the system itself requires a certain fixed amount of energy, and thus suspending the system is beneficial only if the idle time is long enough to compensate for this additional energy expenditure. In the specific problem studied in the paper, we have a set of jobs with release times and deadlines that need to be executed on a single processor. Preemptions are allowed. The processor requires energy L to be woken up and, when it is on, it uses the energy at a rate of R units per unit of time. It has been an open problem whether a schedule minimizing the overall energy consumption can be computed in polynomial time. We solve this problem in positive, by providing an O(n5)-time algorithm. In addition we provide an O(n4)-time algorithm for computing the minimum energy schedule when all jobs have unit length.
Cite as

Marek Chrobak, Philippe Baptiste, and Christoph Dürr. Polynomial Time Algorithms for Minimum Energy Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{chrobak_et_al:DagSemProc.10071.8,
  author =	{Chrobak, Marek and Baptiste, Philippe and D\"{u}rr, Christoph},
  title =	{{Polynomial Time Algorithms for Minimum Energy Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.8},
  URN =		{urn:nbn:de:0030-drops-25351},
  doi =		{10.4230/DagSemProc.10071.8},
  annote =	{Keywords: Scheduling, algorithm, dynamic programming, energy}
}
  • Refine by Author
  • 1 Baptiste, Philippe
  • 1 Chapuy, Guillaume
  • 1 Chrobak, Marek
  • 1 Dürr, Christoph
  • 1 Louf, Baptiste
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Distribution functions
  • 1 Mathematics of computing → Enumeration
  • 1 Mathematics of computing → Random graphs

  • Refine by Keyword
  • 1 Hurwitz numbers
  • 1 RSK algorithm
  • 1 Random partitions
  • 1 Scheduling
  • 1 algorithm
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2010
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact