惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

J
Java Code Geeks
GbyAI
GbyAI
Google DeepMind News
Google DeepMind News
Jina AI
Jina AI
B
Blog
aimingoo的专栏
aimingoo的专栏
酷 壳 – CoolShell
酷 壳 – CoolShell
T
The Blog of Author Tim Ferriss
Last Week in AI
Last Week in AI
月光博客
月光博客
H
Help Net Security
V
Visual Studio Blog
量子位
A
About on SuperTechFans
博客园 - Franky
人人都是产品经理
人人都是产品经理
N
Netflix TechBlog - Medium
云风的 BLOG
云风的 BLOG
雷峰网
雷峰网
Martin Fowler
Martin Fowler
Microsoft Security Blog
Microsoft Security Blog
博客园 - 叶小钗
P
Proofpoint News Feed
MongoDB | Blog
MongoDB | Blog

cs.DS updates on arXiv.org

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications A computational phase transition for learning-to-sample from Ising models Covering vertices by sequential stars Fermi-Dirac machines as quantizations of neurons A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation A Tight Bound on Localization of Electrical Flows Optimal Dimension-Free Sampling for Regularized Classification Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs Beyond the Half-Approximation: Fair and Efficient Online Class Matching Efficient Uniform Sampling of Surjections via their Profiles Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking Learning-Augmented Online Scheduling with Parsimonious Preemption Entropy Equivalence Testing Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees The Secretary Problem with a Stochastic Precursor Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification Block-Sphere Vector Quantization An Approximation Algorithm for Graph Label Selection Iterative Chow Filtering for Learning with Distribution Shift Complexity of Non-Log-Concave Sampling in Fisher Information Stochastic Matching via Local Sparsification Finite Sample Bounds for Learning with Score Matching What is Learnable in Valiant's Theory of the Learnable? Provable Quantization with Randomized Hadamard Transform Min-Max Optimization Requires Exponentially Many Queries Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm A proximal gradient algorithm for composite log-concave sampling
Online Load Balancing on Unrelated Machines with Startup ...
Yossi Azar, Debmalya Panigrahi · 2012-03-21 · via cs.DS updates on arXiv.org

Motivated by applications in energy-efficient scheduling in data centers, Khuller, Li, and Saha introduced the {\em machine activation} problem as a generalization of the classical optimization problems of set cover and load balancing on unrelated machines. In this problem, a set of $n$ jobs have to be distributed among a set of $m$ (unrelated) machines, given the processing time of each job on each machine, where each machine has a startup cost. The goal is to produce a schedule of minimum total startup cost subject to a constraint $\bf L$ on its makespan. While Khuller {\em et al} considered the offline version of this problem, a typical scenario in scheduling is one where jobs arrive online and have to be assigned to a machine immediately on arrival. We give an $(O(\log (mn)\log m), O(\log m))$-competitive randomized online algorithm for this problem, i.e. the schedule produced by our algorithm has a makespan of $O({\bf L} \log m)$ with high probability, and a total expected startup cost of $O(\log (mn)\log m)$ times that of an optimal offline schedule with makespan $\bf L$. The competitive ratios of our algorithm are (almost) optimal. Our algorithms use the online primal dual framework introduced by Alon {\em et al} for the online set cover problem, and subsequently developed further by Buchbinder, Naor, and co-authors. To the best of our knowledge, all previous applications of this framework have been to linear programs (LPs) with either packing or covering constraints. One novelty of our application is that we use this framework for a mixed LP that has both covering and packing constraints. We hope that the algorithmic techniques developed in this paper to simultaneously handle packing and covering constraints will be useful for solving other online optimization problems as well.