8 papers
Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
Afrouz Jabal Ameli, Jesper Nederlof, Shengzhe Wang
We provide improved space-time tradeoffs for permutation problems over additively idempotent semi-rings. In particular, there is an algorithm for the Traveling Salesperson Problem…
New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph
Afrouz Jabal Ameli, Tomohiro Koana, Jesper Nederlof +1
The Strongly Connected Steiner Subgraph (SCSS) problem is a well-studied network design problem that asks for a minimum subgraph that strongly connects a given set of terminals. In…
Learning-Augmented Online Covering Problems
Afrouz Jabal Ameli, Laura Sanita, Moritz Venzin
We give a very general and simple framework to incorporate predictions on requests for online covering problems in a rigorous and black-box manner. Our framework turns any online a…
A Approximation for -Vertex-Connectivity
Miguel Bosch-Calvo, Fabrizio Grandoni, 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 . Ou…
A -Approximation for Two-Edge Connectivity
Miguel Bosch-Calvo, Mohit Garg, Fabrizio Grandoni +3
The 2-Edge-Connected Spanning Subgraph problem (2ECSS) is among the most basic survivable network design problems: given an undirected and unweighted graph, the task is to find a s…
On the MST-ratio: Theoretical Bounds and Complexity of Finding the Maximum
Afrouz Jabal Ameli, Faezeh Motiei, Morteza Saghafian
Given a finite set of red and blue points in $\Rspace^d$, the MST-ratio is defined as the total length of the Euclidean minimum spanning trees of the red points and the blue points…