Search Results

Documents authored by Ghazy, Ahmed

Document
DOI: 10.4230/LIPIcs.ESA.2026.53
Faster Exponential Algorithms for Multi-Machine Scheduling Problems

Authors: Anubhav Dhar, Anita Dürr, Ahmed Ghazy, Jakob Greilhuber, and Karol Węgrzycki

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
Minimizing the weighted completion times (P ‖ Σ w_j C_j) and weighted number of tardy jobs (P ‖ Σ w_j U_j) on multiple identical machines are two classical NP-hard scheduling problems. As shown by Lenté et al. (2014), both problems can be solved in time 𝒪^⋆(3ⁿ). In this paper, we improve these bounds to 𝒪(2.755ⁿ) and 𝒪^⋆(2ⁿ), respectively. Our algorithm for P ‖ Σ w_j C_j exploits the meet-in-the-middle paradigm and an efficient data structure answering linear programming queries. Additionally, when the number of machines is at most 6, we show that the running time for P ‖ Σ w_j C_j can further be improved. Both scheduling problems are generalizations of the classical Bin Packing problem, which can be solved in 𝒪^⋆(2ⁿ) time. Improving this running time is an important open question. We show that, when assuming the Asymptotic Rank Conjecture (ARC), Bin Packing can be solved in time 𝒪((2-ε)ⁿ) for some ε > 0. Our algorithm makes use of two main ingredients: the recent 𝒪((2-ε)ⁿ)-time algorithm of Nederlof et al. [SICOMP'23] for Bin Packing when the number of bins is a fixed constant, and the 𝒪((2-ε)ⁿ)-time algorithm of Björklund et al. [SODA'25] for special instances of the 3-way Partitioning problem when assuming ARC.
Cite as

Anubhav Dhar, Anita Dürr, Ahmed Ghazy, Jakob Greilhuber, and Karol Węgrzycki. Faster Exponential Algorithms for Multi-Machine Scheduling Problems. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 53:1-53:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dhar_et_al:LIPIcs.ESA.2026.53,
  author =	{Dhar, Anubhav and D\"{u}rr, Anita and Ghazy, Ahmed and Greilhuber, Jakob and W\k{e}grzycki, Karol},
  title =	{{Faster Exponential Algorithms for Multi-Machine Scheduling Problems}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{53:1--53:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.53},
  URN =		{urn:nbn:de:0030-drops-271894},
  doi =		{10.4230/LIPIcs.ESA.2026.53},
  annote =	{Keywords: Scheduling, exact algorithms, exponential-time algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2026.98
Where Treewidth and Pathwidth Diverge: Towards a Uniform Kernel for Pathwidth-η Deletion

Authors: Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann, and Roohani Sharma

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
For a constant η ≥ 0, Pathwidth-η Deletion is the problem of deciding whether, for a given graph G and integer k, there is a set S ⊆ V(G) of size at most k such that the pathwidth of G - S is at most η. The problems Treewidth-η Deletion and Treedepth-η Deletion are defined similarly for the parameters treewidth and treedepth, respectively. A landmark result of Fomin et al. [FOCS, 2012] shows that, for any constant η, all three problems admit a kernel on O(k^c(η)) vertices, where c(η) is a constant depending on η. Giannopoulou et al. [ACM TALG, 2017] show that, in some sense, this result is optimal for Treewidth-η Deletion: for η ≥ 2 and even when parameterizing by the size of a vertex cover M of the input graph, there is no kernel of size O(|M|^{(η+1)/2-ε}), for any ε > 0. Contrasting this result, they prove that Treedepth-η Deletion admits a uniform polynomial kernel, that is, a kernel of size O(k^c) for a constant c that is independent of η. In comparison, the question whether Pathwidth-η Deletion admits a uniform polynomial kernel has been neglected in the literature. As treewidth and pathwidth tend to behave similarly, it is natural to expect that no uniform polynomial kernel exists when parameterizing by the size of a vertex cover. Surprisingly, we show this not to be the case. More concretely, we prove the existence of a uniform polynomial kernel for Pathwidth-η Deletion when parameterizing by 1) the solution size k plus the size of a set M such that G - M has bounded treedepth, 2) the (vertex-deletion) distance to pathwidth-1 graphs, 3) the distance to the class of graphs with treedepth at most η + 1. This pinpoints a striking difference between Pathwidth-η Deletion and Treewidth-η Deletion and leads us to conjecture that Pathwidth-η Deletion admits a uniform polynomial kernel when parameterizing by the solution size k.
Cite as

Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann, and Roohani Sharma. Where Treewidth and Pathwidth Diverge: Towards a Uniform Kernel for Pathwidth-η Deletion. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 98:1-98:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ghazy_et_al:LIPIcs.ESA.2026.98,
  author =	{Ghazy, Ahmed and Greilhuber, Jakob and Hartmann, Tim A. and Sharma, Roohani},
  title =	{{Where Treewidth and Pathwidth Diverge: Towards a Uniform Kernel for Pathwidth-\eta Deletion}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{98:1--98:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.98},
  URN =		{urn:nbn:de:0030-drops-272343},
  doi =		{10.4230/LIPIcs.ESA.2026.98},
  annote =	{Keywords: Uniform kernelization, pathwidth deletion, treedepth, elimination distance}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.31
From Chinese Postman to Salesman and Beyond: Shortest Tour δ-Covering All Points on All Edges

Authors: Fabian Frei, Ahmed Ghazy, Tim A. Hartmann, Florian Hörsch, and Dániel Marx

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
A well-studied continuous model of graphs, introduced by Dearing and Francis [Transportation Science, 1974], considers each edge as a continuous unit-length interval of points. For δ ≥ 0, we introduce the problem δ-Tour, where the objective is to find the shortest tour that comes within a distance of δ of every point on every edge. It can be observed that 0-Tour is essentially equivalent to the Chinese Postman Problem, which is solvable in polynomial time. In contrast, 1/2-Tour is essentially equivalent to the graphic Traveling Salesman Problem (TSP), which is NP-hard but admits a constant-factor approximation in polynomial time. We investigate δ-Tour for other values of δ, noting that the problem’s behavior and the insights required to understand it differ significantly across various δ regimes. On the one hand, we first examine the approximability of the problem for every fixed δ > 0: 1) For every fixed 0 < δ < 3/2, the problem δ-Tour admits a constant-factor approximation and is APX-hard, while for every fixed δ ≥ 3/2, the problem admits an O(log n)-approximation in polynomial time and has no polynomial-time o(log n)-approximation, unless P = NP. Our techniques also yield a new APX-hardness result for graphic TSP on cubic bipartite graphs. When parameterizing by the length of a shortest tour, it is relatively easy to show that 3/2 is the threshold of fixed-parameter tractability: 2) For every fixed 0 < δ < 3/2, the problem δ-Tour is fixed-parameter tractable (FPT) when parameterized by the length of a shortest tour, while it is W[2]-hard for every fixed δ ≥ 3/2. On the other hand, if δ is considered to be part of the input, then an interesting nontrivial phenomenon appears when δ is a constant fraction of the number of vertices: 3) If δ is part of the input, then the problem can be solved in time f(k)n^O(k), where k = ⌈n/δ⌉; however, assuming the Exponential-Time Hypothesis (ETH), there is no algorithm that solves the problem and runs in time f(k)n^o(k/log k).
Cite as

Fabian Frei, Ahmed Ghazy, Tim A. Hartmann, Florian Hörsch, and Dániel Marx. From Chinese Postman to Salesman and Beyond: Shortest Tour δ-Covering All Points on All Edges. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{frei_et_al:LIPIcs.ISAAC.2024.31,
  author =	{Frei, Fabian and Ghazy, Ahmed and Hartmann, Tim A. and H\"{o}rsch, Florian and Marx, D\'{a}niel},
  title =	{{From Chinese Postman to Salesman and Beyond: Shortest Tour \delta-Covering All Points on All Edges}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.31},
  URN =		{urn:nbn:de:0030-drops-221582},
  doi =		{10.4230/LIPIcs.ISAAC.2024.31},
  annote =	{Keywords: Chinese Postman Problem, Traveling Salesman Problem, Continuous Graphs, Approximation Algorithms, Inapproximability, Parameterized Complexity}
}
Document
DOI: 10.4230/LIPIcs.DISC.2024.26
Content-Oblivious Leader Election on Rings

Authors: Fabian Frei, Ran Gelles, Ahmed Ghazy, and Alexandre Nolin

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
In content-oblivious computation, n nodes wish to compute a given task over an asynchronous network that suffers from an extremely harsh type of noise, which corrupts the content of all messages across all channels. In a recent work, Censor-Hillel, Cohen, Gelles, and Sela (Distributed Computing, 2023) showed how to perform arbitrary computations in a content-oblivious way in 2-edge connected networks but only if the network has a distinguished node (called root) to initiate the computation. Our goal is to remove this assumption, which was conjectured to be necessary. Achieving this goal essentially reduces to performing a content-oblivious leader election since an elected leader can then serve as the root required to perform arbitrary content-oblivious computations. We focus on ring networks, which are the simplest 2-edge connected graphs. On oriented rings, we obtain a leader election algorithm with message complexity O(n ⋅ ID_max), where ID_max is the maximal assigned ID. As it turns out, this dependency on ID_max is inherent: we show a lower bound of Ω(n log(ID_max/n)) messages for content-oblivious leader election algorithms. We also extend our results to non-oriented rings, where nodes cannot tell which channel leads to which neighbor. In this case, however, the algorithm does not terminate but only reaches quiescence.
Cite as

Fabian Frei, Ran Gelles, Ahmed Ghazy, and Alexandre Nolin. Content-Oblivious Leader Election on Rings. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 26:1-26:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{frei_et_al:LIPIcs.DISC.2024.26,
  author =	{Frei, Fabian and Gelles, Ran and Ghazy, Ahmed and Nolin, Alexandre},
  title =	{{Content-Oblivious Leader Election on Rings}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{26:1--26:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.26},
  URN =		{urn:nbn:de:0030-drops-212527},
  doi =		{10.4230/LIPIcs.DISC.2024.26},
  annote =	{Keywords: Content-Oblivious Computation, Faulty Communication, Leader Election, Ring Networks, Ring Orientation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.34
Exploring the Approximability Landscape of 3SUM

Authors: Karl Bringmann, Ahmed Ghazy, and Marvin Künnemann

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Since an increasing number of problems in P have conditional lower bounds against exact algorithms, it is natural to study which of these problems can be efficiently approximated. Often, however, there are many potential ways to formulate an approximate version of a problem. We ask: How sensitive is the (in-)approximability of a problem in P to its precise formulation? To this end, we perform a case study using the popular 3SUM problem. Its many equivalent formulations give rise to a wide range of potential approximate relaxations. Specifically, to obtain an approximate relaxation in our framework, one can choose among the options: (a) 3SUM or Convolution 3SUM, (b) monochromatic or trichromatic, (c) allowing under-approximation, over-approximation, or both, (d) approximate decision or approximate optimization, (e) single output or multiple outputs and (f) implicit or explicit target (given as input). We show general reduction principles between some variants and find that we can classify the remaining problems (over polynomially bounded positive integers) into three regimes: 1) (1+ε)-approximable in near-linear time Õ(n + 1/ε), 2) (1+ε)-approximable in near-quadratic time Õ(n/ε) or Õ(n+1/ε²), or 3) non-approximable, i.e., requiring time n^{2± o(1)} even for any approximation factor. In each of these three regimes, we provide matching upper and conditional lower bounds. To prove our results, we establish two results that may be of independent interest: Over polynomially bounded integers, we show subquadratic equivalence of (min,+)-convolution and polyhedral 3SUM, and we prove equivalence of the Strong 3SUM conjecture and the Strong Convolution 3SUM conjecture.
Cite as

Karl Bringmann, Ahmed Ghazy, and Marvin Künnemann. Exploring the Approximability Landscape of 3SUM. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.ESA.2024.34,
  author =	{Bringmann, Karl and Ghazy, Ahmed and K\"{u}nnemann, Marvin},
  title =	{{Exploring the Approximability Landscape of 3SUM}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.34},
  URN =		{urn:nbn:de:0030-drops-211057},
  doi =		{10.4230/LIPIcs.ESA.2024.34},
  annote =	{Keywords: Fine-grained Complexity, Conditional Lower Bounds, Approximation Schemes, Min-Plus Convolution}
}

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