Afrouz Jabal Ameli

Afrouz Jabal Ameli

Auto-generated profile, based on publicly available information

Afrouz Jabal Ameli

TU Eindhoven, Eindhoven, The Netherlands

Research Focus & Metrics

Academic Career Length

6Years (2021-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
9 June 2022
Verified
Conference Paper
Open access
FGFabrizio Grandoni
Fabrizio Grandoni
AAAfrouz Jabal Ameli
Afrouz Jabal Ameli
VTVera Traub
Vera Traub
The basic goal of survivable network design is to build cheap networks that guarantee the connectivity of certain pairs of nodes despite the failure of a few edges or nodes. A celebrated result by Jain [Combinatorica'01] provides a 2-approximation for a wide class of these problems. However nothing better is known even for very basic special cases, raising the natural question whether any improved approximation factor is possible at all. In this paper we address one of the most basic problems in this family for which 2 is still the best-known approximation factor, the Forest Augmentation Problem (FAP): given an undirected unweighted graph (that w.l.o.g. we can assume to be a forest) and a collection of extra edges (links), compute a minimum cardinality subset of links whose addition to the graph makes it 2-edge-connected. Several better-than-2 approximation algorithms are known for the special case where the input graph is a tree, a.k.a. the Tree Augmentation Problem (TAP), see e.g. [Grandoni, Kalaitzis, Zenklusen - STOC'18; Cecchetto, Traub, Zenklusen - STOC'21] and references therein. Recently this was achieved also for the weighted version of TAP [Traub, Zenklusen - FOCS'21], and for the k-connectivity generalization of TAP [Byrka, Grandoni, Jabal-Ameli - STOC'20; Cecchetto, Traub, Zenklusen - STOC'21]. These results heavily exploit the fact that the input graph is connected, a condition that does not hold in FAP. In this paper we breach the 2-approximation barrier for FAP. Our result is based on two main ingredients. First, we describe a reduction to the Path Augmentation Problem (PAP), the special case of FAP where the input graph is a collection of disjoint paths. Our reduction is not approximation preserving, however it is sufficiently accurate to improve on a factor 2 approximation. Second, we present a better-than-2 approximation algorithm for PAP, an open problem on its own. Here we exploit a novel notion of implicit credits which might turn out to be helpful in future related work.

1 March 2021 in Theory of Computing Systems
Verified
Journal Article
Open access
PDF file
WGWaldo Gálvez
Waldo Gálvez
FGFabrizio Grandoni
Fabrizio Grandoni
AAAfrouz Jabal Ameli
Afrouz Jabal Ameli
KSKrzysztof Sornat
Krzysztof Sornat
In the k-Connectivity Augmentation Problem we are given a k-edge-connected graph and a set of additional edges called links. Our goal is to find a set of links of minimum size whose addition to the graph makes it (k + 1)-edge-connected. There is an approximation preserving reduction from the mentioned problem to the case k = 1 (a.k.a. the Tree Augmentation Problem or TAP) or k = 2 (a.k.a. the Cactus Augmentation Problem or CacAP). While several better-than-2 approximation algorithms are known for TAP, for CacAP only recently this barrier was breached (hence for k-Connectivity Augmentation in general). As a first step towards better approximation algorithms for CacAP, we consider the special case where the input cactus consists of a single cycle, the Cycle Augmentation Problem (CycAP). This apparently simple special case retains part of the hardness of the general case. In particular, we are able to show that it is APX-hard. In this paper we present a combinatorial $\left (\frac {3}{2}+\varepsilon \right )$ 3 2 + ε -approximation for CycAP, for any constant ε > 0. We also present an LP formulation with a matching integrality gap: this might be useful to address the general case of the problem.

15 June 2025
Verified
Conference Paper
Open access
MBMiguel Bosch-Calvo
Miguel Bosch-Calvo
MGMohit Garg
Mohit Garg
FGFabrizio Grandoni
Fabrizio Grandoni
FHFelix Hommelsheim
Felix Hommelsheim
AAAfrouz Jabal Ameli
Afrouz Jabal Ameli
ALAlexander Lindermayr
Alexander Lindermayr

14 February 2026
Verified
Book Chapter
Closed access
PDF file
AAAfrouz Jabal Ameli
Afrouz Jabal Ameli
FMFaezeh Motiei
Faezeh Motiei
MSMorteza Saghafian
Morteza Saghafian

16 June 2025 in TheoretiCS
Verified
Journal Article
Open access
PDF file
MBMiguel Bosch-Calvo
Miguel Bosch-Calvo
FGFabrizio Grandoni
Fabrizio Grandoni
AAAfrouz Jabal Ameli
Afrouz Jabal Ameli
The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph $G$. Our goal is to find a spanning subgraph $S$ of $G$ with the minimum number of edges which is $2$-vertex-connected, namely $S$ remains connected after the deletion of an arbitrary node. 2VCSS is well-studied in terms of approximation algorithms, and the current best (polynomial-time) approximation factor is $10/7$ by Heeger and Vygen [SIDMA'17] (improving on earlier results by Khuller and Vishkin [STOC'92] and Garg, Vempala and Singla [SODA'93]). Here we present an improved $4/3$ approximation. Our main technical ingredient is an approximation preserving reduction to a conveniently structured subset of instances which are ``almost'' 3-vertex-connected. The latter reduction might be helpful in future work.Comment: 44 pages. This is the TheoretiCS journal version

18 September 2026 in Mathematical Programming
Verified
Journal Article
Open access
PDF file
MBMiguel Bosch-Calvo
Miguel Bosch-Calvo
FGFabrizio Grandoni
Fabrizio Grandoni
AAAfrouz Jabal Ameli
Afrouz Jabal Ameli
In the Triangle-Free (Simple) 2-Matching problem we are given an undirected graph $$G=(V,E)$$ G = ( V , E ) . Our goal is to compute a maximum-cardinality $$M\subseteq E$$ M ⊆ E satisfying the following properties: (1) at most two edges of M are incident on each node (i.e., M is a 2-matching) and (2) M does not induce any triangle. Recently, Hartvigsen [J. Graph Theory 2024] published a complex polynomial-time algorithm for this problem, with a very complex analysis (spanning over 100 pages). This result was originally announced in his Ph.D. thesis from 1984. In this paper we have a fresh look at this problem and present a simple PTAS for it based on local search. Our PTAS exploits the fact that, as long as the current solution is far enough from the optimum, there exists a short augmenting trail (similar to the maximum matching case).