4 Search Results for "Delfaraz, Esmaeil"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.80
FPT Approximations for Connected Maximum Coverage

Authors: Tanmay Inamdar, Satyabrata Jana, Madhumita Kundu, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We revisit connectivity-constrained coverage through a unifying model, Partial Connected Red-Blue Dominating Set (PartialConRBDS). Given a bipartite graph G = (R∪ B,E) with red vertices R and blue vertices B, an auxiliary connectivity graph G_{conn} on R, and integers k,t, the task is to find a set S ⊆ R with |S| ≤ k such that G_{conn}[S] is connected and S dominates at least t blue vertices. This formulation captures connected variants of Maximum Coverage [Hochbaum-Rao, Inf. Proc. Lett., 2020; D'Angelo-Delfaraz, AAMAS 2025], Partial Vertex Cover, and Partial Dominating Set [Khuller et al., SODA 2014; Lamprou et al., TCS 2021] via standard encodings. Limits to parameterized tractability. PartialConRBDS is W[1]-hard parameterized by k even under strong restrictions: it remains hard when G_{conn} is a clique or a star and the incidence graph G is 3-degenerate, or when G is K_{2,2}-free. Inapproximability. For every ε > 0, there is no polynomial-time (1, 1-1/e+ε)-approximation unless 𝖯 = NP. Moreover, under ETH, no algorithm running in f(k)⋅ n^{o(k)} time achieves an g(k)-approximation for k for any computable function g(⋅), or for any ε > 0, a (1-1/e+ε)-approximation for t. Graphical special cases. Partial Connected Dominating Set is W[2]-hard parameterized by k and inherits the same ETH-based f(k)⋅ n^{o(k)} inapproximability bound as above; Partial Connected Vertex Cover is W[1]-hard parameterized by k. These hardness boundaries delineate a natural "sweet spot" for study: within appropriate structural restrictions on the incidence graph, one can still aim for fine-grained (FPT) approximations. Our algorithms. We solve PartialConRBDS exactly by reducing it to Relaxed Directed Steiner Out-Tree in time (2e)^t ⋅ n^{𝒪(1)}. For biclique-free incidences (i.e., when G excludes K_{d,d} as an induced subgraph), we obtain two complementary parameterized schemes: - An Efficient Parameterized Approximation Scheme (EPAS) running in time 2^{𝒪(k² d/ε)}⋅ n^{𝒪(1)} that either returns a connected solution of size at most k covering at least (1-ε)t blue vertices, or correctly reports that no connected size-k solution covers t; and - A Parameterized Approximation Scheme (PAS) running in time 2^{𝒪(kd(k²+log d))}⋅ n^{𝒪(1/ε)} that either returns a connected solution of size at most (1+ε)k covering at least t blue vertices, or correctly reports that no connected size-k solution covers t. Together, these results chart the boundary between hardness and FPT-approximability for connectivity-constrained coverage.
Cite as

Tanmay Inamdar, Satyabrata Jana, Madhumita Kundu, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. FPT Approximations for Connected Maximum Coverage. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 80:1-80:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{inamdar_et_al:LIPIcs.ITCS.2026.80,
  author =	{Inamdar, Tanmay and Jana, Satyabrata and Kundu, Madhumita and Lokshtanov, Daniel and Saurabh, Saket and Zehavi, Meirav},
  title =	{{FPT Approximations for Connected Maximum Coverage}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{80:1--80:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.80},
  URN =		{urn:nbn:de:0030-drops-253674},
  doi =		{10.4230/LIPIcs.ITCS.2026.80},
  annote =	{Keywords: Partial Dominating Set, Connectivity, Maximum Coverage, FPT Approximation, Fixed-parameter Tractability}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.5
Edge-Minimum Walk of Modular Length in Polynomial Time

Authors: Antoine Amarilli, Benoît Groz, and Nicole Wein

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We study the problem of finding, in a directed graph, an st-walk of length r od q which is edge-minimum, i.e., uses the smallest number of distinct edges. Despite the vast literature on paths and cycles with modularity constraints, to the best of our knowledge we are the first to study this problem. Our main result is a polynomial-time algorithm that solves this task when r and q are constants. We also show how our proof technique gives an algorithm to solve a generalization of the well-known Directed Steiner Network problem, in which connections between endpoint pairs are required to satisfy modularity constraints on their length. Our algorithm is polynomial when the number of endpoint pairs and the modularity constraints on the pairs are constants. In this version of the article, proofs and examples are omitted because of space constraints. Detailed proofs are available in the full version [Antoine Amarilli et al., 2024].
Cite as

Antoine Amarilli, Benoît Groz, and Nicole Wein. Edge-Minimum Walk of Modular Length in Polynomial Time. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{amarilli_et_al:LIPIcs.ITCS.2025.5,
  author =	{Amarilli, Antoine and Groz, Beno\^{i}t and Wein, Nicole},
  title =	{{Edge-Minimum Walk of Modular Length in Polynomial Time}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{5:1--5:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.5},
  URN =		{urn:nbn:de:0030-drops-226330},
  doi =		{10.4230/LIPIcs.ITCS.2025.5},
  annote =	{Keywords: Directed Steiner Network, Modularity}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2024.7
Improved Algorithms for the Capacitated Team Orienteering Problem

Authors: Gianlorenzo D'Angelo, Mattia D'Emidio, Esmaeil Delfaraz, and Gabriele Di Stefano

Published in: OASIcs, Volume 123, 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)

Abstract
We study the Capacitated Team Orienteering Problem, where a fleet of vehicles with capacities have to meet customers with known demands and prizes for a single commodity. The objective is to maximize the total prize and to assign a sequence of customers to each vehicle while keeping the total distance traveled within a given budget and such that the total demand served by each vehicle does not exceed its capacity. The problem has been widely studied both from a theoretical and a practical point of view. The contribution of this paper is twofold: (1) We advance the theoretical knowledge on the problem by providing new approximation algorithms that achieve, under some natural assumption, improved approximation ratios compared to the current best algorithms; (2) We propose four efficient heuristics that outperform the current state-of-the-art practical methods in the sense that they compute solutions that collect nearly the same prize in a significantly smaller running time. We also experimentally test the scalability of the new heuristics, showing that their running time increases approximately linearly with the size of the input, allowing us to process large graphs which were not possible to analyze before.
Cite as

Gianlorenzo D'Angelo, Mattia D'Emidio, Esmaeil Delfaraz, and Gabriele Di Stefano. Improved Algorithms for the Capacitated Team Orienteering Problem. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dangelo_et_al:OASIcs.ATMOS.2024.7,
  author =	{D'Angelo, Gianlorenzo and D'Emidio, Mattia and Delfaraz, Esmaeil and Di Stefano, Gabriele},
  title =	{{Improved Algorithms for the Capacitated Team Orienteering Problem}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{7:1--7:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-350-8},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{123},
  editor =	{Bouman, Paul C. and Kontogiannis, Spyros C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.7},
  URN =		{urn:nbn:de:0030-drops-211957},
  doi =		{10.4230/OASIcs.ATMOS.2024.7},
  annote =	{Keywords: Vehicle Routing, Approximation algorithms, Algorithm Engineering}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.9
Budgeted Out-Tree Maximization with Submodular Prizes

Authors: Gianlorenzo D'Angelo, Esmaeil Delfaraz, and Hugo Gilbert

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We consider a variant of the prize collecting Steiner tree problem in which we are given a directed graph D = (V,A), a monotone submodular prize function p:2^V → ℝ^+ ∪ {0}, a cost function c:V → ℤ^+, a root vertex r ∈ V, and a budget B. The aim is to find an out-subtree T of D rooted at r that costs at most B and maximizes the prize function. We call this problem Directed Rooted Submodular Tree (DRST). For the case of undirected graphs and additive prize functions, Moss and Rabani [SIAM J. Comput. 2007] gave an algorithm that guarantees an O(log|V|)-approximation factor if a violation by a factor 2 of the budget constraint is allowed. Bateni et al. [SIAM J. Comput. 2018] improved the budget violation factor to 1+ε at the cost of an additional approximation factor of O(1/ε²), for any ε ∈ (0,1]. For directed graphs, Ghuge and Nagarajan [SODA 2020] gave an optimal quasi-polynomial time O({log n'}/{log log n'})-approximation algorithm, where n' is the number of vertices in an optimal solution, for the case in which the costs are associated to the edges. In this paper, we give a polynomial time algorithm for DRST that guarantees an approximation factor of O(√B/ε³) at the cost of a budget violation of a factor 1+ε, for any ε ∈ (0,1]. The same result holds for the edge-cost case, to the best of our knowledge this is the first polynomial time approximation algorithm for this case. We further show that the unrooted version of DRST can be approximated to a factor of O(√B) without budget violation, which is an improvement over the factor O(Δ √B) given in [Kuo et al. IEEE/ACM Trans. Netw. 2015] for the undirected and unrooted case, where Δ is the maximum degree of the graph. Finally, we provide some new/improved approximation bounds for several related problems, including the additive-prize version of DRST, the maximum budgeted connected set cover problem, and the budgeted sensor cover problem.
Cite as

Gianlorenzo D'Angelo, Esmaeil Delfaraz, and Hugo Gilbert. Budgeted Out-Tree Maximization with Submodular Prizes. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dangelo_et_al:LIPIcs.ISAAC.2022.9,
  author =	{D'Angelo, Gianlorenzo and Delfaraz, Esmaeil and Gilbert, Hugo},
  title =	{{Budgeted Out-Tree Maximization with Submodular Prizes}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.9},
  URN =		{urn:nbn:de:0030-drops-172945},
  doi =		{10.4230/LIPIcs.ISAAC.2022.9},
  annote =	{Keywords: Prize Collecting Steiner Tree, Directed graphs, Approximation Algorithms, Budgeted Problem}
}
  • Refine by Type
  • 4 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2025
  • 1 2024
  • 1 2022

  • Refine by Author
  • 2 D'Angelo, Gianlorenzo
  • 2 Delfaraz, Esmaeil
  • 1 Amarilli, Antoine
  • 1 D'Emidio, Mattia
  • 1 Di Stefano, Gabriele
  • Show More...

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

  • Refine by Classification
  • 2 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 1 Algorithm Engineering
  • 1 Approximation Algorithms
  • 1 Approximation algorithms
  • 1 Budgeted Problem
  • 1 Connectivity
  • 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