6 papers · 1 filter
Remote Matching: Exact-Cardinality Approximation and Tight UGC Hardness
Arash Ahadi, Morteza Alimi, Sharareh Alipour +1
In the unrestricted max--min metric -join problem, one seeks an even terminal set maximizing the cost of a minimum -join. Iwata and Ravi gave a factor- approximation…
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…
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…
Mean Isoperimetry with Control on Outliers: Exact and Approximation Algorithms
Morteza Alimi, Amir Daneshgar, Mohammad-Hadi Foroughmand-Araabi
Given a weighted graph with weight functions and , and a subset , the normalized cut value for is defined as…