8 papers
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…
V844 Herculis: An Exceptional Intermediate Polar Hiding in an Ordinary Dwarf Nova
Anousha Greiveldinger, Peter Garnavich, Colin Littlefield +16
We present time-series spectroscopy of the SU UMa-type dwarf nova V844 Her during quiescence. We discover high-velocity Balmer and He I emission features modulated at a period of 2…
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…
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…