Search for: All records

The configuration balancing problem with stochastic requests generalizes well-studied resource allocation problems such as load balancing and virtual circuit routing. There are givenmresources andnrequests; each request has multiple possibleconfigurations, each of which increases the load of each resource by some amount. The goal is to select one configuration for each request to minimize themakespan: the load of the most-loaded resource. In the stochastic setting, the amount by which a configuration increases the resource load is uncertain until the configuration is chosen, but we are given a probability distribution. We develop both offline and online algorithms for configuration balancing with stochastic requests. When the requests are known offline, we give a non-adaptive policy for configuration balancing with stochastic requests that$$O(\frac{\log m}{\log \log m})$$$O\left(\frac{logm}{loglogm}\right)$-approximates the optimal adaptive policy, which matches a known lower bound for the special case of load balancing on identical machines. When requests arrive online in a list, we give a non-adaptive policy that is$$O(\log m)$$$O(logm)$competitive. Again, this result is asymptotically tight due to information-theoretic lower bounds for special cases (e.g., for load balancing on unrelated machines). Finally, we show how to leverage adaptivity in the special case of load balancing onrelatedmachines to obtain a constant-factor approximation offline and an$$O(\log \log m)$$$O(loglogm)$-approximation online. A crucial technical ingredient in all of our results is a new structural characterization of the optimal adaptive policy that allows us to limit the correlations between its decisions.

This paper considers approximation algorithms for generalizedk-median problems. These problems can be informally described ask-median with a constant number of extra constraints, and includesk-median with outliers, and knapsack median. Our first contribution is a pseudo-approximation algorithm for generalizedk-median that outputs a 6.387-approximate solution, with a constant number of fractional variables. The algorithm builds on the iterative rounding framework introduced by Krishnaswamy, Li, and Sandeep fork-median with outliers as reported (Krishnaswamy et al. in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018). The main technical innovation is allowing richer constraint sets in the iterative rounding and using the structure of the resulting extreme points. Using our pseudo-approximation algorithm, we give improved approximation algorithms fork-median with outliers and knapsack median. This involves combining our pseudo-approximation with pre- and post-processing steps to round a constant number of fractional variables at a small increase in cost. Our algorithms achieve approximation ratios$$6.994 + \epsilon $$$6.994+ϵ$and$$6.387 + \epsilon $$$6.387+ϵ$fork-median with outliers and knapsack median, respectively. These improve on the best-known approximation ratio$$7.081 + \epsilon $$$7.081+ϵ$for both problems as reported (Krishnaswamy et al. in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018).

This paper considers the basic problem of scheduling jobs online with preemption to maximize the number of jobs completed by their deadline onmidentical machines. The main result is anO(1) competitive deterministic algorithm for any number of machines$$m >1$$$m>1$.