3 Search Results for "Schalekamp, Frans"

Document
DOI: 10.4230/LIPIcs.ESA.2025.27
Online Makespan Scheduling Under Scenarios

Authors: Ekin Ergen

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We consider a natural extension of online makespan scheduling on identical parallel machines by introducing scenarios. A scenario is a subset of jobs, and the task of our problem is to find a global assignment of the jobs to machines so that the maximum makespan under a scenario, i.e., the maximum makespan of any schedule restricted to a scenario, is minimized. For varying values of the number of scenarios and machines, we explore the competitiveness of online algorithms. We prove tight and near-tight bounds, several of which are achieved through novel constructions. In particular, we leverage the interplay between the unit processing time case of our problem and the hypergraph coloring problem both ways: We use hypergraph coloring techniques to steer an adversarial family of instances proving lower bounds for our problem, which in turn leads to lower bounds for several variants of online hypergraph coloring.
Cite as

Ekin Ergen. Online Makespan Scheduling Under Scenarios. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ergen:LIPIcs.ESA.2025.27,
  author =	{Ergen, Ekin},
  title =	{{Online Makespan Scheduling Under Scenarios}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.27},
  URN =		{urn:nbn:de:0030-drops-244950},
  doi =		{10.4230/LIPIcs.ESA.2025.27},
  annote =	{Keywords: online scheduling, scenario-based model, online algorithms}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.21
Dual Charging for Half-Integral TSP

Authors: Nathan Klein and Mehrshad Taziki

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

Abstract
In this extended abstract, we show that the max entropy algorithm is a randomized 1.49776 approximation for half-integral TSP, improving upon the previous known bound of 1.49993 from Karlin et al. This also improves upon the best-known approximation for half-integral TSP due to Gupta et al. Our improvement results from using the dual, instead of the primal, to analyze the expected cost of the matching. We believe this method of analysis could lead to a simpler proof that max entropy is a better-than-3/2 approximation in the general case.
Cite as

Nathan Klein and Mehrshad Taziki. Dual Charging for Half-Integral TSP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{klein_et_al:LIPIcs.APPROX/RANDOM.2025.21,
  author =	{Klein, Nathan and Taziki, Mehrshad},
  title =	{{Dual Charging for Half-Integral TSP}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{21:1--21:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.21},
  URN =		{urn:nbn:de:0030-drops-243879},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.21},
  annote =	{Keywords: Approximation Algorithms, Graph Algorithms, Randomized Rounding, Linear Programming}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.70
A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest

Authors: Frans Schalekamp, Anke van Zuylen, and Suzanne van der Ster

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades, since it can be used to compute the Subtree Prune-and-Regraft (SPR) distance between two phylogenetic trees. Our result improves on the very recent 2.5-approximation algorithm due to Shi, Feng, You and Wang (2015). Our algorithm is the first approximation algorithm for this problem that uses LP duality in its analysis.
Cite as

Frans Schalekamp, Anke van Zuylen, and Suzanne van der Ster. A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{schalekamp_et_al:LIPIcs.ICALP.2016.70,
  author =	{Schalekamp, Frans and van Zuylen, Anke and van der Ster, Suzanne},
  title =	{{A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{70:1--70:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.70},
  URN =		{urn:nbn:de:0030-drops-62149},
  doi =		{10.4230/LIPIcs.ICALP.2016.70},
  annote =	{Keywords: Maximum agreement forest, phylogenetic tree, SPR distance, subtree prune-and-regraft distance, computational biology}
}
  • Refine by Type
  • 3 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2016

  • Refine by Author
  • 1 Ergen, Ekin
  • 1 Klein, Nathan
  • 1 Schalekamp, Frans
  • 1 Taziki, Mehrshad
  • 1 van Zuylen, Anke
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Online algorithms
  • 1 Theory of computation → Routing and network design problems

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Graph Algorithms
  • 1 Linear Programming
  • 1 Maximum agreement forest
  • 1 Randomized Rounding
  • 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