Running summarizing tools on a new article

Abstract: We consider the minimum makespan problem for $n$ tasks and two unrelated parallel selfish machines. Let $R_n$ be the best approximation ratio of randomized monotone scale-free algorithms. This class contains the most efficient known algorithms for \emph{truthful} scheduling on two machines. We propose a new $Min{-}Max$ formulation for $R_n$, as well as upper and lower bounds on $R_n$ using this formulation. The lower bound is based on pointwise approximations of cumulative distribution functions (CDFs). The upper bound is obtained from the randomized algorithms in which we use distributions with piecewise rational CDFs. Our method improves upon the existing bounds on $R_n$ for small $n$. In particular, we obtain almost tight bounds for $n=2$ showing that $|R_2-1.505996|<10^{-6}$.