Júlia Baligács

About me

I am a postdoctoral researcher at the University of Oxford, where I work in Christian Coester’s group. Previously, I was a postdoc at the University of Warsaw, and I completed my PhD at TU Darmstadt in September 2025.

I am interested in a broad range of problems in discrete mathematics and theoretical computer science. My research focuses primarily on combinatorial optimization, online algorithms, and approximation algorithms.

jbaligacs@gmail.com arXiv DBLP

Publications

  • A tight lower bound for malicious online bipartite matching with limited recourse budget

    with Bartłomiej Bosek, Paweł Putra, Marek Sokołowski, and Anna Zych-Pawlewicz

    to appear in Proceedings of the 38th ACM-SIAM Symposium on Discrete Algorithms (SODA 2027)

    arXiv
    abstract

    We study one-sided online bipartite matching with recourse. In this setting, one side of a bipartite graph is known in advance, while vertices on the other side arrive online together with their incident edges. After each arrival, the algorithm must maintain a maximum-cardinality matching while minimizing the total number of reallocations, also known as the recourse budget. Despite extensive work, the exact recourse complexity of the problem remains unsettled: the best lower bound is Ω(n log n), whereas the best upper bound is O(n log² n), where n denotes the number of online vertices. Tight upper bounds of O(n log n) are known only for restricted graph classes, such as forests.

    The best known upper bounds are attained by a very simple and natural algorithm SAP, which after each arrival applies a shortest augmenting path, and it is conjectured to be optimal. All known upper bound analyses of this algorithm do not depend on the particular maximum matching maintained by the algorithm. Consequently, they also apply to a more difficult problem, which we call the malicious matching setting: after each arrival, the maintained matching is replaced by a worst-case maximum matching for the next step. This led to the conjecture that the malicious setting still admits an O(n log n) recourse bound, in line with the conjectured optimal complexity of the original model.

    Our main result is an Ω(n log² n) lower bound for the malicious matching setting, thus disproving the conjecture. Together with the previous upper bound, this settles the asymptotic recourse complexity of the malicious variant of the problem. We complement our lower bound with an upper bound of O(n log n) for expander graphs.

    BibTeX 
    @misc{baligacs2026tight,
  title = {A tight lower bound for malicious online bipartite matching
           with limited recourse budget},
  author = {Baligács, Júlia and Bosek, Bartłomiej and Putra, Paweł and
            Sokołowski, Marek and Zych-Pawlewicz, Anna},
  year = {2026},
  eprint = {2608.22524},
  archivePrefix = {arXiv},
  note = {To appear in Proceedings of the 38th ACM-SIAM Symposium
          on Discrete Algorithms (SODA 2027)},
  url = {https://arxiv.org/abs/2608.22524}
}

  • Temporal cliques admit linear spanners

    to appear in Proceedings of the 38th ACM-SIAM Symposium on Discrete Algorithms (SODA 2027)

    arXiv
    abstract

    A temporal graph is a graph in which every edge carries a non-empty set of time labels, and it is temporally connected if for every two vertices u and v, there exists a u–v path with non-decreasing time labels. A spanner is a subset of its edges preserving temporal connectivity. Unlike static graphs, temporally connected graphs need not admit sparse spanners; nonetheless, minimizing spanner size is a central and widely studied problem. A particularly intriguing question is whether temporal cliques admit spanners of linear size. Despite considerable effort over the past years, the best known upper bound remained O(n log n). We finally resolve this question, proving that every temporal clique on n vertices admits a spanner of size 7n. Moreover, such a spanner can be computed in polynomial time.

    BibTeX 
    @misc{baligacs2026temporal,
  title = {Temporal cliques admit linear spanners},
  author = {Baligács, Júlia},
  year = {2026},
  eprint = {2606.05156},
  archivePrefix = {arXiv},
  note = {To appear in Proceedings of the 38th ACM-SIAM Symposium
          on Discrete Algorithms (SODA 2027)},
  url = {https://arxiv.org/abs/2606.05156}
}

  • Almost Linear 3-Spanners of Temporal Cliques

    with Davide Bilò, Václav Blažej, Maël Dumas, and Anna Zych-Pawlewicz

    Preprint, 2026

    arXiv
    abstract

    Temporal graphs model dynamic networks by assigning positive integer time labels to the edges, while information propagates along temporal paths, whose edge labels are traversed in nondecreasing order. A temporal α-spanner of a temporal graph with n vertices is a temporal subgraph that approximates the minimum-hop temporal distance between every pair of vertices within a factor of α. While general temporal graphs may not admit sparse temporal α-spanners for any value of α, temporal cliques are known to admit temporal (2k − 1)-spanners of size Õ(kn1 + 1/k) for every positive integer k.

    We present a simple recursive algorithm that computes, for every temporal clique on n vertices, a temporal 3-spanner of size n1 + 2/√(ln n) = n1 + o(1), thereby improving the previous best upper bound of Õ(n3/2). We also show that a modified version of our algorithm computes temporal 3-spanners of size O(nL) when the lifetime is bounded by L, i.e., all time labels are in {1, …, L}, thus improving the previous bound of O(2Ln log n). Both results are particularly striking in light of the known lower bound of Ω(n²) on the size of temporal 2-spanners, which already holds for temporal cliques of lifetime L ≥ 3.

    Both algorithms rely on a new simple recursive decomposition that certifies temporal connectivity for a large collection of source-target pairs using only O(n) carefully selected edges and recursively processes only the remaining pairs. Besides yielding substantially improved upper bounds, this approach is significantly simpler than previous constructions.

    BibTeX 
    @misc{baligacs2026almost,
  title = {Almost Linear 3-Spanners of Temporal Cliques},
  author = {Baligács, Júlia and Bilò, Davide and Blažej, Václav and
            Dumas, Maël and Zych-Pawlewicz, Anna},
  year = {2026},
  eprint = {2609.02851},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.02851}
}

  • Randomization helps in online graph exploration: breaking the deterministic lower bound on cycles

    with Jan Hązła and Lena Volk

    Preprint, 2026

    arXiv
    abstract

    In online graph exploration, introduced by Kalyanasundaram and Pruhs (1994), an agent must visit all vertices of an initially unknown weighted graph and return to its starting position, while the graph is revealed only locally at visited vertices. Although the problem has attracted considerable attention, previous work has focused exclusively on deterministic algorithms. Randomized strategies are often substantially harder to analyze because of a fundamental challenge inherent to exploration. In this work, we give the first positive result showing that randomization can improve competitive guarantees in online graph exploration. To this end, we focus on cycles, a simple graph class which nevertheless captures a key difficulty of online exploration. Our main contribution is RandHeavyTest, a randomized algorithm for online exploration of cycles whose competitive ratio we prove to be at most 1.315. This establishes a strict separation from the deterministic setting, where the optimal competitive ratio is approximately 1.366, and thus gives the first provable advantage of randomization in online graph exploration. A key step towards this result is a new, simplified optimal deterministic algorithm, HeavyTest, whose formulation naturally suggests the randomized variant. We complement our upper bounds with lower bounds of 1.115 for arbitrary randomized algorithms and 1.207 for the natural class of forward-greedy algorithms, which includes RandHeavyTest.

    BibTeX 
    @misc{baligacs2026randomization,
  title = {Randomization helps in online graph exploration:
           breaking the deterministic lower bound on cycles},
  author = {Baligács, Júlia and Hązła, Jan and Volk, Lena},
  year = {2026},
  eprint = {2607.11203},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.11203}
}

  • A coarse block-cut tree theorem

    with Václav Blažej, Jadwiga Czyżewska, Michał Pilipczuk, and Evangelos Protopapas

    Preprint, 2026

    arXiv
    abstract

    We prove a coarse analogue of the classic fact that every graph can be decomposed along its cut-vertices into 2-connected components. Precisely, we prove that for every graph G and a positive integer d, G admits a tree decomposition whose adhesion sets have weak diameter at most 3d + 2 so that no two vertices u and v lying in the same bag can be separated by a set of weak diameter at most d whose distance from u and v is more than d. By the coarse Menger theorem for two paths, this condition admits also a dual formulation, phrased in terms of the existence of two paths that are far from each other and connect the vicinity of u with the vicinity of v.

    BibTeX 
    @misc{baligacs2026coarse,
  title = {A coarse block-cut tree theorem},
  author = {Baligács, Júlia and Blažej, Václav and
            Czyżewska, Jadwiga and Pilipczuk, Michał and
            Protopapas, Evangelos},
  year = {2026},
  eprint = {2607.07111},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.07111}
}

  • Inevitability of polarization in geometric opinion exchange

    with Abdou Majeed Alidou, Max Hahn-Klimroth, Jan Hązła, Lukas Hintze, and Olga Scheftelowitsch

    Mathematics of Operations Research (MOR), 2026

    article arXiv
    abstract

    Polarization and unexpected correlations between opinions on diverse topics (including in politics, culture and consumer choices) are an object of sustained attention. However, numerous theoretical models do not seem to convincingly explain these phenomena. This paper is motivated by a recent line of work, studying models where polarization can be explained in terms of biased assimilation and geometric interplay between opinions on various topics. The agent opinions are represented as unit vectors on a multidimensional sphere and updated according to geometric rules. In contrast to previous work, we focus on the classical opinion exchange setting, where the agents update their opinions in discrete time steps, with a pair of agents interacting randomly at every step. The opinions are updated according to an update rule belonging to a general class. Our findings are twofold. First, polarization appears to be ubiquitous in the class of models we study, requiring only relatively modest assumptions reflecting biased assimilation. Second, there is a qualitative difference between two-dimensional dynamics on the one hand, and three or more dimensions on the other. Accordingly, we prove almost sure polarization for a large class of update rules in two dimensions. Then, we prove polarization in three and more dimensions in more limited cases and try to shed light on central difficulties that are absent in two dimensions.

    BibTeX 
    @article{alidou2026inevitability,
  title = {Inevitability of polarization in geometric opinion exchange},
  author = {Alidou, Abdou Majeed and Baligács, Júlia and
            Hahn-Klimroth, Max and Hązła, Jan and Hintze, Lukas and
            Scheftelowitsch, Olga},
  journal = {Mathematics of Operations Research},
  year = {2026},
  doi = {10.1287/moor.2024.0696},
  url = {https://doi.org/10.1287/moor.2024.0696}
}

  • Exploration of graphs with excluded minors

    with Yann Disser, Irene Heinrich, and Pascal Schweitzer

    Journal of Computer and System Sciences (JCSS), 2026

    article arXiv preliminary version at ESA 2023
    abstract

    We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs (1994) and prove a constant competitive ratio on minor-free graphs. This result encompasses and significantly extends the graph classes that were previously known to admit a constant competitive ratio. The main ingredient of our proof is that we find a connection between the performance of the particular exploration algorithm Blocking and the existence of light spanners. Conversely, we exploit this connection to construct light spanners of bounded genus graphs. In particular, we achieve a lightness that improves on the best known upper bound for genus g > 0 and recovers the known tight bound for the planar case (g = 0).

    BibTeX 
    @article{baligacs2026exploration,
  title = {Exploration of graphs with excluded minors},
  author = {Baligács, Júlia and Disser, Yann and Heinrich, Irene and
            Schweitzer, Pascal},
  journal = {Journal of Computer and System Sciences},
  volume = {156},
  pages = {103725},
  year = {2026},
  doi = {10.1016/j.jcss.2025.103725},
  url = {https://doi.org/10.1016/j.jcss.2025.103725}
}
    conference slides (PDF) seminar slides (PDF)

  • Tight analysis of the Lazy algorithm for open online dial-a-ride

    with Yann Disser, Nils Mosis, and David Weckbecker

    SIAM Journal on Discrete Mathematics (SIDMA), 2026

    article preliminary versions: WAOA 2022 WADS 2023
    abstract

    In the open online dial-a-ride problem, a single server has to deliver transportation requests appearing over time in some metric space, subject to minimizing the completion time. We improve on the best known upper bounds on the competitive ratio on general metric spaces and on the half-line, for both the preemptive and nonpreemptive version of the problem. We achieve this by presenting a new algorithm called Lazy. More precisely, we show that it has competitive ratio 2.457 on general metric spaces and 2.366 on the half-line. This is the first upper bound that beats known lower bounds of 2.5 for schedule-based algorithms as well as the natural Replan algorithm. Furthermore, we provide matching lower bounds on the competitive ratio of Lazy, which yields that our analysis is tight.

    BibTeX 
    @article{baligacs2026lazy,
  title = {Tight analysis of the {Lazy} algorithm for open online dial-a-ride},
  author = {Baligács, Júlia and Disser, Yann and Mosis, Nils and
            Weckbecker, David},
  journal = {SIAM Journal on Discrete Mathematics},
  volume = {40},
  number = {1},
  pages = {260--281},
  year = {2026},
  doi = {10.1137/24M1657833},
  url = {https://doi.org/10.1137/24M1657833}
}

  • Online and incremental fractional vertex cover on trees

    with Bartłomiej Bosek, Yann Disser, Andreas Emil Feldmann, Grzegorz Gutowski, Katarzyna Kępińska, Paweł Putra, and Anna Zych-Pawlewicz

    Proceedings of the 34th Annual European Symposium on Algorithms (ESA 2026)

    article arXiv
    abstract

    In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori and the edges arrive one at a time. The goal is to maintain a fractional vertex cover of the tree, i.e., an assignment of fractional weights from [0, 1] to the vertices such that the weights of endpoints of every edge sum up to at least one. After each edge arrival, we need to modify the fractional vertex cover to cover the new edge as well. However, we can only increase the values assigned to vertices. The problem was studied before (in the vertex arrival model) by Wang and Wong, who motivated it as a generalization of the ski-rental problem, but also (more importantly) by its close connection to the dual online matching problem. They presented a 1.901-competitive algorithm for general graphs in the vertex arrival model. We present an 11/6 ≈ 1.83-competitive algorithm for trees in the more general edge arrival model.

    In addition, we study the fractional vertex cover problem in an incremental model, where we again seek a fractional vertex cover after every update, but all the updates to the tree are known to the algorithm a priori. In this model, we give a 1.5-competitive algorithm and provide a matching lower bound.

    BibTeX 
    @inproceedings{baligacs2026online,
  title = {Online and incremental fractional vertex cover on trees},
  author = {Baligács, Júlia and Bosek, Bartłomiej and Disser, Yann and
            Feldmann, Andreas Emil and Gutowski, Grzegorz and
            Kępińska, Katarzyna and Putra, Paweł and
            Zych-Pawlewicz, Anna},
  booktitle = {34th Annual European Symposium on Algorithms ({ESA} 2026)},
  volume = {388},
  pages = {158:1--158:15},
  year = {2026},
  editor = {Bille, Philip and Pettie, Seth and Storandt, Sabine},
  doi = {10.4230/LIPIcs.ESA.2026.158},
  url = {https://doi.org/10.4230/LIPIcs.ESA.2026.158}
}

  • Improved bounds for online TSP on the half-line

    with Yann Disser and Linda Thelen

    Proceedings of the 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

    article
    abstract

    In the open online traveling salesperson problem, requests appear over time at different positions of a metric space. A single agent traveling at unit speed must serve all requests, by visiting their positions, with the objective of minimizing the completion time. We propose online algorithms for this problem for the case that the metric space is the half-line. First, we present a 2-competitive algorithm in which the server always either moves at unit speed or remains stationary, which improves on the previously best-known ratio of 2.04. We further observe that algorithms must sometimes move slower than unit speed to achieve competitive ratios below 2. We introduce a second algorithm that beats the barrier of 2 by carefully modulating its speed, and prove a tight bound of 1.75 on its competitive ratio. Finally, we slightly strengthen a known lower bound on the best-possible competitive ratio on the half-line from 1.627 to 1.646.

    BibTeX 
    @inproceedings{baligacs2026improved,
  title = {Improved bounds for online {TSP} on the half-line},
  author = {Baligács, Júlia and Disser, Yann and Thelen, Linda},
  booktitle = {Proceedings of the 20th Scandinavian Symposium on
               Algorithm Theory},
  volume = {370},
  pages = {4:1--4:17},
  year = {2026},
  doi = {10.4230/LIPIcs.SWAT.2026.4},
  url = {https://doi.org/10.4230/LIPIcs.SWAT.2026.4}
}

  • A lower bound of 4 for online graph exploration

    to appear in Proceedings of the 17th Latin American Theoretical Informatics Symposium (LATIN 2026)

    arXiv
    abstract

    In the online graph exploration problem, a single agent needs to visit every vertex of an initially unknown graph, which is learned over time in an online fashion, and return to its starting position. We prove that the competitive ratio is at least 4, improving on the previously best known lower bound of 10/3. A key ingredient is showing that several restrictions can be imposed on the agent's behavior without affecting the competitive ratio. As a byproduct, certain graph properties, such as the triangle inequality or being subcubic, can be assumed without affecting the competitive ratio.

    BibTeX 
    @inproceedings{baligacs2026lower,
  title = {A lower bound of 4 for online graph exploration},
  author = {Baligács, Júlia},
  booktitle = {Proceedings of the 17th Latin American Theoretical
               Informatics Symposium},
  year = {2026},
  eprint = {2607.15113},
  archivePrefix = {arXiv},
  note = {To appear},
  url = {https://arxiv.org/abs/2607.15113}
}
    conference slides (PDF)

  • Geometric opinion exchange polarizes in every dimension

    with Abdou Majeed Alidou and Jan Hązła

    Preprint, 2025

    arXiv
    abstract

    A recent line of work studies models of opinion exchange where agent opinions about d topics are tracked simultaneously. The opinions are represented as vectors on the unit (d−1)-sphere, and the update rule is based on the overall correlation between the relevant vectors. The update rule reflects the assumption of biased assimilation, i.e., a pair of opinions is brought closer together if their correlation is positive and further apart if their correlation is negative. This model seems to induce the polarization of opinions into two antipodal groups. This is in contrast to many other known models which tend to achieve consensus. The polarization property has been recently proved for d = 2, but the general case of d ≥ 3 remained open. In this work, we settle the general case, using a more detailed understanding of the model dynamics and tools from the theory of random processes.

    BibTeX 
    @misc{alidou2025geometric,
  title = {Geometric opinion exchange polarizes in every dimension},
  author = {Alidou, Abdou Majeed and Baligács, Júlia and Hązła, Jan},
  year = {2025},
  eprint = {2510.08190},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.08190}
}

  • Symmetry classes of Hamiltonian cycles

    with Sofia Brenner, Annette Lutz, and Lena Volk

    Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

    article arXiv
    abstract

    We initiate the study of Hamiltonian cycles up to symmetries of the underlying graph. Our focus lies on the extremal case of Hamiltonian-transitive graphs, i.e., Hamiltonian graphs where, for every pair of Hamiltonian cycles, there is a graph automorphism mapping one cycle to the other. This generalizes the extensively studied uniquely Hamiltonian graphs. In this paper, we show that Cayley graphs of abelian groups are not Hamiltonian-transitive (under some mild conditions and some non-surprising exceptions), i.e., they contain at least two structurally different Hamiltonian cycles. To show this, we reduce Hamiltonian-transitivity to properties of the prime factors of a Cartesian product decomposition, which we believe is interesting in its own right. We complement our results by constructing infinite families of regular Hamiltonian-transitive graphs and take a look at the opposite extremal case by constructing a family with many different Hamiltonian cycles up to symmetry.

    BibTeX 
    @inproceedings{baligacs2025symmetry,
  title = {Symmetry classes of {Hamiltonian} cycles},
  author = {Baligács, Júlia and Brenner, Sofia and Lutz, Annette and
            Volk, Lena},
  booktitle = {Proceedings of the 50th International Symposium on
               Mathematical Foundations of Computer Science},
  volume = {345},
  pages = {15:1--15:18},
  year = {2025},
  doi = {10.4230/LIPIcs.MFCS.2025.15},
  url = {https://doi.org/10.4230/LIPIcs.MFCS.2025.15}
}

  • The metric Menger problem

    with Joseph MacManus

    Preprint, 2024

    arXiv
    abstract

    We study a generalization of the well-known disjoint paths problem which we call the metric Menger problem, denoted MM(r,k), where one is given two subsets of a graph and must decide whether they can be connected by k paths of pairwise distance at least r. We prove that this problem is NP-complete for every r ≥ 3 and k ≥ 2 by giving a reduction from 3SAT. This resolves a conjecture recently stated by Georgakopoulos and Papasoglu. On the other hand, we show that the problem is in XP when parameterised by treewidth and maximum degree by observing that it is “locally checkable”. In the case r ≤ 3, we prove that it suffices to parameterise by treewidth. We also state some open questions relating to this work.

    BibTeX 
    @misc{baligacs2024metric,
  title = {The metric {Menger} problem},
  author = {Baligács, Júlia and MacManus, Joseph},
  year = {2024},
  eprint = {2403.05630},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2403.05630}
}

  • A (5/3 + ε)-approximation for tricolored non-crossing Euclidean TSP

    with Yann Disser, Andreas Emil Feldmann, and Anna Zych-Pawlewicz

    Proceedings of the 32nd Annual European Symposium on Algorithms (ESA 2024)

    article arXiv
    abstract

    In the tricolored Euclidean traveling salesperson problem, we are given k = 3 sets of points in the plane and are looking for disjoint tours, each covering one of the sets. Arora (1998) famously gave a PTAS based on “patching” for the case k = 1 and, recently, Dross et al. (2023) generalized this result to k = 2. Our contribution is a (5/3 + ε)-approximation algorithm for k = 3 that further generalizes Arora's approach. It is believed that patching is generally no longer possible for more than two tours. We circumvent this issue by either applying a conditional patching scheme for three tours or using an alternative approach based on a weighted solution for k = 2.

    BibTeX 
    @inproceedings{baligacs2024approximation,
  title = {A $(5/3 + \varepsilon)$-approximation for tricolored
           non-crossing {Euclidean TSP}},
  author = {Baligács, Júlia and Disser, Yann and Feldmann, Andreas Emil and
            Zych-Pawlewicz, Anna},
  booktitle = {Proceedings of the 32nd Annual European Symposium on
               Algorithms},
  volume = {308},
  pages = {15:1--15:15},
  year = {2024},
  doi = {10.4230/LIPIcs.ESA.2024.15},
  url = {https://doi.org/10.4230/LIPIcs.ESA.2024.15}
}
    conference slides (PDF) seminar slides (PDF)

  • Exploration of graphs with excluded minors

    with Yann Disser, Irene Heinrich, and Pascal Schweitzer

    Proceedings of the 31st Annual European Symposium on Algorithms (ESA 2023)

    article arXiv
    abstract

    We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs (1994) and prove a constant competitive ratio on minor-free graphs. This result encompasses and significantly extends the graph classes that were previously known to admit a constant competitive ratio. The main ingredient of our proof is that we find a connection between the performance of the particular exploration algorithm Blocking and the existence of light spanners. Conversely, we exploit this connection to construct light spanners of bounded genus graphs. In particular, we achieve a lightness that improves on the best known upper bound for genus g > 0 and recovers the known tight bound for the planar case (g = 0).

    BibTeX 
    @inproceedings{baligacs2023exploration,
  title = {Exploration of graphs with excluded minors},
  author = {Baligács, Júlia and Disser, Yann and Heinrich, Irene and
            Schweitzer, Pascal},
  booktitle = {Proceedings of the 31st Annual European Symposium on
               Algorithms},
  volume = {274},
  pages = {11:1--11:15},
  year = {2023},
  doi = {10.4230/LIPIcs.ESA.2023.11},
  url = {https://doi.org/10.4230/LIPIcs.ESA.2023.11}
}
    conference slides (PDF) seminar slides (PDF)

  • Tight analysis of the Lazy algorithm for open online dial-a-ride

    with Yann Disser, Farehe Soheil, and David Weckbecker

    Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023)

    article arXiv
    abstract

    In the open online dial-a-ride problem, a single server has to deliver transportation requests appearing over time in some metric space, subject to minimizing the completion time. We improve on the best known upper bounds on the competitive ratio on general metric spaces and on the half-line, for both the preemptive and non-preemptive version of the problem. We achieve this by revisiting the algorithm Lazy recently suggested at WAOA 2022 and giving an improved and tight analysis. More precisely, we show that it has competitive ratio 2.457 on general metric spaces and 2.366 on the half-line. This is the first upper bound that beats known lower bounds of 2.5 for schedule-based algorithms as well as the natural Replan algorithm.

    BibTeX 
    @inproceedings{baligacs2023lazy,
  title = {Tight analysis of the {Lazy} algorithm for open online dial-a-ride},
  author = {Baligács, Júlia and Disser, Yann and Soheil, Farehe and
            Weckbecker, David},
  booktitle = {Proceedings of the 18th Algorithms and Data Structures
               Symposium},
  volume = {14079},
  pages = {43--64},
  year = {2023},
  doi = {10.1007/978-3-031-38906-1_4},
  url = {https://doi.org/10.1007/978-3-031-38906-1_4}
}
    conference slides (PDF)

  • An improved algorithm for open online dial-a-ride

    with Yann Disser, Nils Mosis, and David Weckbecker

    Proceedings of the 20th Workshop on Approximation and Online Algorithms (WAOA 2022)

    article arXiv
    abstract

    We consider the open online dial-a-ride problem, where transportation requests appear online in a metric space and need to be served by a single server. The objective is to minimize the completion time until all requests have been served. We present a new, parameterized algorithm for this problem and prove that it attains a competitive ratio of 1 + φ ≈ 2.618 for some choice of its parameter, where φ is the golden ratio. This improves the best known bounds for open online dial-a-ride both for general metric spaces as well as for the real line. We also give a lower bound of 2.457 for the competitive ratio of our algorithm for any parameter choice.

    BibTeX 
    @inproceedings{baligacs2022improved,
  title = {An improved algorithm for open online dial-a-ride},
  author = {Baligács, Júlia and Disser, Yann and Mosis, Nils and
            Weckbecker, David},
  booktitle = {Proceedings of the 20th Workshop on Approximation and
               Online Algorithms},
  volume = {13538},
  pages = {154--171},
  year = {2022},
  doi = {10.1007/978-3-031-18367-6_8},
  url = {https://doi.org/10.1007/978-3-031-18367-6_8}
}

Selected talks

  • A lower bound of 4 for online graph exploration

    Latin American Theoretical Informatics Symposium (LATIN 2026), Florianópolis, Brazil · slides

  • Online graph exploration: an overview

    Seminar at the University of Warsaw, Poland

  • Approximation algorithms for Euclidean TSP

    AIMS Rwanda, Kigali

  • A (5/3 + ε)-approximation for tricolored non-crossing Euclidean TSP

    European Symposium on Algorithms (ESA 2024), Egham, United Kingdom · slides

  • A (5/3 + ε)-approximation for tricolored non-crossing Euclidean TSP

    Seminar at TU Darmstadt, Germany · slides

  • Exploration of graphs with excluded minors

    CSLog Seminar, University of Bremen (online)

  • Exploration of graphs with excluded minors

    Discrete Algorithms Insights Seminar (DAIS), Darmstadt, Germany · slides

  • Exploration of graphs with excluded minors

    European Symposium on Algorithms (ESA 2023), Amsterdam, Netherlands · slides

  • Tight analysis of the Lazy algorithm for open online dial-a-ride

    Algorithms and Data Structures Symposium (WADS 2023), Montréal, Canada · slides

Brief CV

–

PhD in Mathematics

TU Darmstadt, Germany

advisor: Yann Disser

dissertation: Online and multi-agent approximations for the traveling salesperson problem

doctoral scholarship awarded by the Studienstiftung des deutschen Volkes (Apr 2023–Sep 2025)

teaching assistant for:

  • Discrete Optimization (summer 2025)
  • Aussagenlogik und Prädikatenlogik (summer 2023)
  • Einführung in die Optimierung (winter 2022/23)
  • Seminar on the Probabilistic Method (summer 2022)
  • Mathematik für Informatik II (summer 2022)
  • Mathematik für Informatik I (winter 2021/22)

–

BSc in Mathematics

TU Darmstadt, Germany