• ### Delay Asymptotics and Bounds for Multi-Task Parallel Jobs(1710.00296)

Sept. 16, 2018 cs.PF
We study delay of jobs that consist of multiple parallel tasks, which is a critical performance metric in a wide range of applications such as data file retrieval in coded storage systems and parallel computing. In this problem, each job is completed only when all of its tasks are completed, so the delay of a job is the maximum of the delays of its tasks. Despite the wide attention this problem has received, tight analysis is still largely unknown since analyzing job delay requires characterizing the complicated correlation among task delays, which is hard to do. We first consider an asymptotic regime where the number of servers, $n$, goes to infinity, and the number of tasks in a job, $k^{(n)}$, is allowed to increase with $n$. We establish the asymptotic independence of any $k^{(n)}$ queues under the condition $k^{(n)} = o(n^{1/4})$. This greatly generalizes the asymptotic-independence type of results in the literature where asymptotic independence is shown only for a fixed constant number of queues. As a consequence of our independence result, the job delay converges to the maximum of independent task delays. We next consider the non-asymptotic regime. Here we prove that independence yields a stochastic upper bound on job delay for any $n$ and any $k^{(n)}$ with $k^{(n)}\le n$. The key component of our proof is a new technique we develop, called "Poisson oversampling". Our approach converts the job delay problem into a corresponding balls-and-bins problem. However, in contrast with typical balls-and-bins problems where there is a negative correlation among bins, we prove that our variant exhibits positive correlation.
• ### Practical Algorithms for Best-K Identification in Multi-Armed Bandits(1705.06894)

May 19, 2017 cs.DS, cs.LG, stat.ML
In the Best-$K$ identification problem (Best-$K$-Arm), we are given $N$ stochastic bandit arms with unknown reward distributions. Our goal is to identify the $K$ arms with the largest means with high confidence, by drawing samples from the arms adaptively. This problem is motivated by various practical applications and has attracted considerable attention in the past decade. In this paper, we propose new practical algorithms for the Best-$K$-Arm problem, which have nearly optimal sample complexity bounds (matching the lower bound up to logarithmic factors) and outperform the state-of-the-art algorithms for the Best-$K$-Arm problem (even for $K=1$) in practice.
• ### An Attempt to Design a Better Algorithm for the Uncapacitated Facility Location Problem(1610.07434)

Oct. 24, 2016 cs.DS
The uncapacitated facility location has always been an important problem due to its connection to operational research and infrastructure planning. Byrka obtained an algorithm that is parametrized by $\gamma$ and proved that it is optimal when $\gamma>1.6774$. He also proved that the algorithm achieved an approximation ratio of 1.50. A later work by Shi Li achieved an approximation factor of 1.488. In this research, we studied these algorithms and several related works. Although we didn't improve upon the algorithm of Shi Li, our work did provide some insight into the problem. We also reframed the problem as a vector game, which provided a framework to design balanced algorithms for this problem.
• ### Two Stage Optimization with Recourse and Revocation(1610.06701)

Oct. 21, 2016 cs.DS
Two-stage optimization with recourse model is an important and widely used model, which has been studied extensively these years. In this article, we will look at a new variant of it, called the two-stage optimization with recourse and revocation model. This new model differs from the traditional one in that one is allowed to revoke some of his earlier decisions and withdraw part of the earlier costs, which is not unlikely in many real applications, and is therefore considered to be more realistic under many situations. We will adopt several approaches to study this model. In fact, we will develop an LP rounding scheme for some cover problems and show that they can be solved using this scheme and an adaptation of the rounding approach for the deterministic counterpart, provided the polynomial scenario assumption. Stochastic uncapacitated facility location problem will also be studied to show that the approximation algorithm that worked for the two-stage with recourse model worked for this model as well. In addition, we will use other methods to study the model.