5 papers
An 8/5 Rounding for Half-Integral Forest-BCR via Root Supports and Circuit Rank
Morteza Alimi
We study the rounding of a supplied half-integral feasible solution of the root-assignment bidirected cut relaxation for Steiner Forest (Forest-BCR). Byrka, Grandoni, and Traub [IP…
An Entropy Potential for Type-Composition Games
Morteza Alimi, Merlin de la Haye, Pascal Lenzner +3
Potential functions are a key tool in theoretical computer science with applications ranging from the runtime analysis of algorithms and data structures, through the analysis of th…
Efficient Dynamic Rank Aggregation
Morteza Alimi, Hourie Mehrabiun, Alireza Zarei
The rank aggregation problem, which has many real-world applications, refers to the process of combining multiple input rankings into a single aggregated ranking. In dynamic settin…
Approximating Graphic Multi-Path TSP and Graphic Ordered TSP
Morteza Alimi, Niklas Dahlmeier, Tobias Mömke +2
The path version of the Traveling Salesman Problem is one of the most well-studied variants of the ubiquitous TSP. Its generalization, the Multi-Path TSP, has recently been used in…
Approximating Prize-Collecting Variants of TSP
Morteza Alimi, Tobias Mömke, Michael Ruderer
We present an approximation algorithm for the Prize-collecting Ordered Traveling Salesman Problem (PCOTSP), which simultaneously generalizes the Prize-collecting TSP and the Ordere…