On the Best Interval Approximation Problem
This paper generalises the existing PTAS for complete graphs from a fixed to an arbitrary number of intervals and disprove an existing conjecture, which states that every instance of BIA admits a solution satisfying at least three quarters of all edges.
∗. PeterBlohm, ∗. FlorianChen, A. Gionis et al.
· 0 citations