5 Search Results for "Schubert, Sebastian"

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.13
Optimal Online Bipartite Matching in Degree-2 Graphs

Authors: Amey Bhangale, Arghya Chakraborty, and Prahladh Harsha

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Online bipartite matching is a classical problem in online algorithms and we know that both the deterministic fractional and randomized integral online matchings achieve the same competitive ratio of 1-1/e. In this work, we study classes of graphs where the online degree is restricted to 2. As expected, one can achieve a competitive ratio of better than 1-1/e in both the deterministic fractional and randomized integral cases, but surprisingly, these ratios are not the same. It was already known that for fractional matching, a 0.75 competitive ratio algorithm is optimal. We show that the folklore Half-Half algorithm achieves a competitive ratio of η ≈ 0.717772… and more surprisingly, show that this is optimal by giving a matching lower-bound. This yields a separation between the two problems: deterministic fractional and randomized integral, showing that it is impossible to obtain a perfect rounding scheme.
Cite as

Amey Bhangale, Arghya Chakraborty, and Prahladh Harsha. Optimal Online Bipartite Matching in Degree-2 Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhangale_et_al:LIPIcs.ISAAC.2025.13,
  author =	{Bhangale, Amey and Chakraborty, Arghya and Harsha, Prahladh},
  title =	{{Optimal Online Bipartite Matching in Degree-2 Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.13},
  URN =		{urn:nbn:de:0030-drops-249216},
  doi =		{10.4230/LIPIcs.ISAAC.2025.13},
  annote =	{Keywords: Online Algorithm, Bipartite matching}
}
Document
DOI: 10.4230/OASIcs.SpaceCHI.2025.30
A Research Framework to Develop a Real-Time Synchrony Index to Monitor Team Cohesion and Performance in Long-Duration Space Exploration

Authors: Federico Nemmi, Emma Chabani, Laure Boyer, Charlie Madier, and Daniel Lewkowicz

Published in: OASIcs, Volume 130, Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)

Abstract
As humanity prepares for long-distance space exploration, optimizing group performance, the ability of a group to achieve its goals efficiently, is critical. Astronaut crews will endure isolation, confinement, and operational stress, making group synchrony - the alignment of behaviors, emotions, and physiological states - a key factor in mission success. Synchrony influences team cohesion, performance, and resilience, necessitating effective crew management strategies. This paper proposes a framework for a real-time, unobtrusive index of group synchrony to support astronauts and mission control. Research indicates that team cohesion fluctuates in isolated environments, with reduced communication and interpersonal conflicts emerging over time. A system tracking synchrony could mitigate these issues, providing proactive support and improving remote management. Additionally, it could serve as a cognitive and physiological feedback tool for astronauts and a decision-making aid for mission control, enhancing well-being and efficiency. Our approach integrates behavioral and physiological synchrony measures to assess team cohesion and performance. We propose a multi-modal synchrony index combining movement coordination, communication patterns, and physiological signals such as heart rate, electrodermal activity, and EEG. This index will be validated across different tasks to ensure applicability across diverse mission scenarios. By developing a robust synchrony index, we address a fundamental challenge in space missions: sustaining team effectiveness under extreme conditions. Beyond space exploration, our findings could benefit high-risk, high-isolation teams in submarine crews, polar expeditions, and remote research groups. Our collaboration with the Centre National d'Etudes Spatiales, the Institut de Médecine et de Physiologie Spatiales, and the Toulouse University Hospital marks the first step, with experimental data collection starting this year. Ultimately, this research fosters more adaptive, responsive, and resilient teams for future space missions.
Cite as

Federico Nemmi, Emma Chabani, Laure Boyer, Charlie Madier, and Daniel Lewkowicz. A Research Framework to Develop a Real-Time Synchrony Index to Monitor Team Cohesion and Performance in Long-Duration Space Exploration. In Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025). Open Access Series in Informatics (OASIcs), Volume 130, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{nemmi_et_al:OASIcs.SpaceCHI.2025.30,
  author =	{Nemmi, Federico and Chabani, Emma and Boyer, Laure and Madier, Charlie and Lewkowicz, Daniel},
  title =	{{A Research Framework to Develop a Real-Time Synchrony Index to Monitor Team Cohesion and Performance in Long-Duration Space Exploration}},
  booktitle =	{Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)},
  pages =	{30:1--30:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-384-3},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{130},
  editor =	{Bensch, Leonie and Nilsson, Tommy and Nisser, Martin and Pataranutaporn, Pat and Schmidt, Albrecht and Sumini, Valentina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SpaceCHI.2025.30},
  URN =		{urn:nbn:de:0030-drops-240200},
  doi =		{10.4230/OASIcs.SpaceCHI.2025.30},
  annote =	{Keywords: Performance, Synchronie, Crew monitoring, Cohesion}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.22
FaaSLoad: Fine-Grained Performance and Resource Measurement for Function-As-a-Service

Authors: Mathieu Bacou

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
Cloud computing relies on a deep stack of system layers: virtual machine, operating system, distributed middleware and language runtime. However, those numerous, distributed, virtual layers prevent any low-level understanding of the properties of FaaS applications, considered as programs running on real hardware. As a result, most research analyses only consider coarse-grained properties such as global performance of an application, and existing datasets include only sparse data. FaaSLoad is a tool to gather fine-grained data about performance and resource usage of the programs that run on Function-as-a-Service cloud platforms. It considers individual instances of functions to collect hardware and operating-system performance information, by monitoring them while injecting a workload. FaaSLoad helps building a dataset of function executions to train machine learning models, studying at fine grain the behavior of function runtimes, and replaying real workload traces for in situ observations. This research software project aims at being useful to cloud system researchers with features such as guaranteeing reproducibility and correctness, and keeping up with realistic FaaS workloads. Our evaluations show that FaaSLoad helps us understanding the properties of FaaS applications, and studying the latter under real conditions.
Cite as

Mathieu Bacou. FaaSLoad: Fine-Grained Performance and Resource Measurement for Function-As-a-Service. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 22:1-22:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bacou:LIPIcs.OPODIS.2024.22,
  author =	{Bacou, Mathieu},
  title =	{{FaaSLoad: Fine-Grained Performance and Resource Measurement for Function-As-a-Service}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{22:1--22:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.22},
  URN =		{urn:nbn:de:0030-drops-225581},
  doi =		{10.4230/LIPIcs.OPODIS.2024.22},
  annote =	{Keywords: cloud, serverless, Function-as-a-Service, measurement, performance, resource utilization, dataset generation, workload injection}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.4
Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities

Authors: Susanne Albers and Sebastian Schubert

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We study the b-matching problem in bipartite graphs G = (S,R,E). Each vertex s ∈ S is a server with individual capacity b_s. The vertices r ∈ R are requests that arrive online and must be assigned instantly to an eligible server. The goal is to maximize the size of the constructed matching. We assume that G is a (k,d)-graph [J. Naor and D. Wajc, 2018], where k specifies a lower bound on the degree of each server and d is an upper bound on the degree of each request. This setting models matching problems in timely applications. We present tight upper and lower bounds on the performance of deterministic online algorithms. In particular, we develop a new online algorithm via a primal-dual analysis. The optimal competitive ratio tends to 1, for arbitrary k ≥ d, as the server capacities increase. Hence, nearly optimal solutions can be computed online. Our results also hold for the vertex-weighted problem extension, and thus for AdWords and auction problems in which each bidder issues individual, equally valued bids. Our bounds improve the previous best competitive ratios. The asymptotic competitiveness of 1 is a significant improvement over the previous factor of 1-1/e^{k/d}, for the interesting range where k/d ≥ 1 is small. Recall that 1-1/e ≈ 0.63. Matching problems that admit a competitive ratio arbitrarily close to 1 are rare. Prior results rely on randomization or probabilistic input models.
Cite as

Susanne Albers and Sebastian Schubert. Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.ESA.2022.4,
  author =	{Albers, Susanne and Schubert, Sebastian},
  title =	{{Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.4},
  URN =		{urn:nbn:de:0030-drops-169420},
  doi =		{10.4230/LIPIcs.ESA.2022.4},
  annote =	{Keywords: online algorithms, deterministic algorithms, primal-dual analysis, b-matching, bounded-degree graph, variable vertex capacities, unweighted matching, vertex-weighted matching}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.2
Optimal Algorithms for Online b-Matching with Variable Vertex Capacities

Authors: Susanne Albers and Sebastian Schubert

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
We study the b-matching problem, which generalizes classical online matching introduced by Karp, Vazirani and Vazirani (STOC 1990). Consider a bipartite graph G = (S ̇∪ R,E). Every vertex s ∈ S is a server with a capacity b_s, indicating the number of possible matching partners. The vertices r ∈ R are requests that arrive online and must be matched immediately to an eligible server. The goal is to maximize the cardinality of the constructed matching. In contrast to earlier work, we study the general setting where servers may have arbitrary, individual capacities. We prove that the most natural and simple online algorithms achieve optimal competitive ratios. As for deterministic algorithms, we give a greedy algorithm RelativeBalance and analyze it by extending the primal-dual framework of Devanur, Jain and Kleinberg (SODA 2013). In the area of randomized algorithms we study the celebrated Ranking algorithm by Karp, Vazirani and Vazirani. We prove that the original Ranking strategy, simply picking a random permutation of the servers, achieves an optimal competitiveness of 1-1/e, independently of the server capacities. Hence it is not necessary to resort to a reduction, replacing every server s by b_s vertices of unit capacity and to then run Ranking on this graph with ∑_{s ∈ S} b_s vertices on the left-hand side. From a theoretical point of view our result explores the power of randomization and strictly limits the amount of required randomness. From a practical point of view it leads to more efficient allocation algorithms. Technically, we show that the primal-dual framework of Devanur, Jain and Kleinberg cannot establish a competitiveness better than 1/2 for the original Ranking algorithm, choosing a permutation of the servers. Therefore, we formulate a new configuration LP for the b-matching problem and then conduct a primal-dual analysis. We extend this analysis approach to the vertex-weighted b-matching problem. Specifically, we show that the algorithm PerturbedGreedy by Aggarwal, Goel, Karande and Mehta (SODA 2011), again with a sole randomization over the set of servers, is (1-1/e)-competitive. Together with recent work by Huang and Zhang (STOC 2020), our results demonstrate that configuration LPs can be strictly stronger than standard LPs in the analysis of more complex matching problems.
Cite as

Susanne Albers and Sebastian Schubert. Optimal Algorithms for Online b-Matching with Variable Vertex Capacities. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 2:1-2:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{albers_et_al:LIPIcs.APPROX/RANDOM.2021.2,
  author =	{Albers, Susanne and Schubert, Sebastian},
  title =	{{Optimal Algorithms for Online b-Matching with Variable Vertex Capacities}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{2:1--2:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.2},
  URN =		{urn:nbn:de:0030-drops-146957},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.2},
  annote =	{Keywords: Online algorithms, primal-dual analysis, configuration LP, b-matching, variable vertex capacities, unweighted matching, vertex-weighted matching}
}
  • Refine by Type
  • 5 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2022
  • 1 2021

  • Refine by Author
  • 2 Albers, Susanne
  • 2 Schubert, Sebastian
  • 1 Bacou, Mathieu
  • 1 Bhangale, Amey
  • 1 Boyer, Laure
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 3 Theory of computation → Online algorithms
  • 1 Applied computing → Life and medical sciences
  • 1 Computer systems organization → Cloud computing
  • 1 General and reference → Measurement

  • Refine by Keyword
  • 2 b-matching
  • 2 primal-dual analysis
  • 2 unweighted matching
  • 2 variable vertex capacities
  • 2 vertex-weighted matching
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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