As one of Karp's 21 NP-complete problems, the subset sum problem, as well as its generalization, has been well studied. Among the rich literature, there is little work on the online version, where items arrive ove...
详细信息
As one of Karp's 21 NP-complete problems, the subset sum problem, as well as its generalization, has been well studied. Among the rich literature, there is little work on the online version, where items arrive over list and irrevocable decisions on packing them or not must be made immediately. Under the online setting, no deterministic algorithms are competitive, while for randomized algorithms the best competitive ratio is 1/2. It is thus of great interest to improve the performance bounds for both deterministic and randomized algorithms, assuming predicted information is available in the learning-augmented model. Along this line, we revisit online subset sum by showing that, with learnable predictions, there exist learning-augmented algorithms to break through the worst-case bounds on competitive ratio. The theoretical results are also experimentally verified, where we come up with a new idea in designing experiments. Namely, we design neural networks to serve as adversaries, verifying the robustness of online algorithms. Under this framework, several networks are trained to select adversarial instances and the results show that our algorithms are competitive and robust.
This paper introduces the online state exploration problem. In the problem, there is a hidden d-dimensional target state. We are given a distance function between different states in the space and a penalty function d...
详细信息
ISBN:
(纸本)9783031434204;9783031434211
This paper introduces the online state exploration problem. In the problem, there is a hidden d-dimensional target state. We are given a distance function between different states in the space and a penalty function depending on the current state for each incorrect guess. The goal is to move to a vector that dominates the target state starting from the origin in the d-dimensional space while minimizing the total distance and penalty cost. This problem generalizes several natural online discrete optimization problems such as multi-dimensional knapsack cover, cow path, online bidding, and online search. For online state exploration, the paper gives results in the worst-case competitive analysis model and in the online algorithmsaugmented with the prediction model. The results extend and generalize many known results in the online setting.
We introduce and study spatiotemporal online allocation with deadline constraints (SOAD), a new online problem motivated by emerging challenges in sustainability and energy. In SOAD, an online player completes a workl...
详细信息
We introduce and study spatiotemporal online allocation with deadline constraints (SOAD), a new online problem motivated by emerging challenges in sustainability and energy. In SOAD, an online player completes a workload by allocating and scheduling it on the points of a metric space (X, d) while subject to a deadline T. At each time step, a service cost function is revealed that represents the cost of servicing the workload at each point, and the player must irrevocably decide the current allocation of work to points. Whenever the player moves this allocation, they incur a movement cost defined by the distance metric d(., .) that captures, e.g., an overhead cost. SOAD formalizes the open problem of combining general metrics and deadline constraints in the online algorithms literature, unifying problems such as metrical task systems and online search. We propose a competitive algorithm for SOAD along with a matching lower bound establishing its optimality. Our main algorithm, ST-CLIP, is a learning-augmented algorithm that takes advantage of predictions (e.g., forecasts of relevant costs) and achieves an optimal consistency-robustness trade-off. We evaluate our proposed algorithms in a simulated case study of carbon-aware spatiotemporal workload management, an application in sustainable computing that schedules a delay-tolerant batch compute job on a distributed network of data centers. In these experiments, we show that ST-CLIP substantially improves on heuristic baseline methods.
The recent revival in learning theory has provided us with improved capabilities for accurate predictions. This work contributes to an emerging research agenda of online scheduling with predictions by studying makespa...
详细信息
The recent revival in learning theory has provided us with improved capabilities for accurate predictions. This work contributes to an emerging research agenda of online scheduling with predictions by studying makespan minimization in uniformly related machine non-clairvoyant scheduling with job size predictions. Our task is to design online algorithms that use predictions and have performance guarantees tied to prediction quality. We first propose a simple algorithm-independent prediction error metric to quantify prediction quality. Then we design an offline improved 2-relaxed decision procedure approximating the optimal schedule to effectively use the predictions. With the decision procedure, we propose an online O(min {log eta,log m})-competitive static scheduling algorithm assuming a known prediction error. We use this algorithm to construct a robust O(min {log eta,log m})-competitive static scheduling algorithm that does not assume a known error. Finally, we extend these static scheduling algorithms to address dynamic scheduling where jobs arrive over time. The dynamic scheduling algorithms attain the same competitive ratios as the static ones. The presented algorithms require just moderate predictions to break the Omega(log m) competitive ratio lower bound, showing the potential of predictions in managing uncertainty.
Recently, flash-based solid state drives (SSDs) have become a primary storage solution due to their advantages over hard-disk drives. Nonetheless, SSD management presents unique challenges. First, SSDs update data by ...
详细信息
Recently, flash-based solid state drives (SSDs) have become a primary storage solution due to their advantages over hard-disk drives. Nonetheless, SSD management presents unique challenges. First, SSDs update data by writing a new copy to a clean slot, rather than overwriting old data. Second, SSDs support cleaning of entire blocks, while slots cannot be cleaned individually. Third, when cleaning a block, any valid data it stores must first be rewritten to another location, which adversely affects the SSD endurance and throughput. In this work, we address the SSD management problem, where the objective is to minimize the number of rewrites in SSDs. We approach the problem from a theoretical perspective, analyzing algorithms in a worst-case fashion. Motivated by recent advances in machine learning, we consider a learning-augmented setting where the algorithm has access to a predictive oracle, with performance guarantees expressed as a function of the error in the oracle's output. Our main contribution is Gladiator, a novel online algorithm that optimally leverages predictions to enhance the performance of SSDs. Compared to prior work, Gladiator requires no additional non-volatile memory and is less sensitive to prediction errors. We further demonstrate the effectiveness of Gladiator under reasonable assumptions on the input distribution, and extend it to an extremely efficient offline algorithm. Empirical results confirm its superiority over state-of-the-art practical solutions across diverse SSD workloads.
The value maximization version of the secretary problem is the problem of hiring a candidate with the largest value from a randomly ordered sequence of candidates. In this work, we consider a setting where predictions...
详细信息
The value maximization version of the secretary problem is the problem of hiring a candidate with the largest value from a randomly ordered sequence of candidates. In this work, we consider a setting where predictions of candidate values are provided in advance. We propose an algorithm that achieves a nearly optimal value if the predictions are accurate and results in a constant-factor competitive ratio otherwise. We also show that the worst-case competitive ratio of an algorithm cannot be higher than some constant < 1=e, which is the best possible competitive ratio when we ignore predictions, if the algorithm performs nearly optimally when the predictions are accurate. Additionally, for the multiple-choice secretary problem, we propose an algorithm with a similar theoretical guarantee. We empirically illustrate that if the predictions are accurate, the proposed algorithms perform well;meanwhile, if the predictions are inaccurate, performance is comparable to existing algorithms that do not use predictions.
Increasing penetration of variable and intermittent renewable energy resources on the energy grid poses a challenge for reliable and efficient grid operation, necessitating the development of algorithms that are robus...
详细信息
Increasing penetration of variable and intermittent renewable energy resources on the energy grid poses a challenge for reliable and efficient grid operation, necessitating the development of algorithms that are robust to this uncertainty. However, standard algorithms incorporating uncertainty for generation dispatch are computationally intractable when costs are nonconvex, and machine learning-based approaches lack worst-case guarantees on their performance. In this work, we propose a learning-augmented algorithm, RobustML, that exploits the good average-case performance of a machine-learned algorithm for minimizing dispatch and ramping costs of dispatchable generation resources while providing provable worst-case guarantees on cost. We evaluate the algorithm on a realistic model of a combined cycle cogeneration plant, where it exhibits robustness to distribution shift while enabling improved efficiency as renewables penetration increases.
In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements with the objective to minimize the total (weighted) completion time. We revisit t...
详细信息
ISBN:
(纸本)9781450391467
In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements with the objective to minimize the total (weighted) completion time. We revisit this well-studied problem in a recently popular learning-augmented setting that integrates (untrusted) predictions in online algorithm design. While previous works used predictions on processing requirements, we propose a new prediction model, which provides a relative order of jobs which could be seen as predicting algorithmic actions rather than parts of the unknown input. We show that these predictions have desired properties, admit a natural error measure as well as algorithms with strong performance guarantees and that they are learnable in both, theory and practice. We generalize the algorithmic framework proposed in the seminal paper by Kumar et al. (NeurIPS'18) and present the first learning-augmented scheduling results for weighted jobs and unrelated machines. We demonstrate in empirical experiments the practicability and superior performance compared to the previously suggested single-machine algorithms.
Despite rapid progress in theoretical reinforcement learning (RL) over the last few years, most of the known guarantees are worst-case in nature, failing to take advantage of structure that may be known a priori about...
详细信息
Despite rapid progress in theoretical reinforcement learning (RL) over the last few years, most of the known guarantees are worst-case in nature, failing to take advantage of structure that may be known a priori about a given RL problem at hand. In this paper we address the question of whether worst-case lower bounds for regret in online learning of Markov decision processes (MDPs) can be circumvented when information about the MDP, in the form of predictions about its optimal Q-value function, is given to the algorithm. We show that when the predictions about the optimal Q-value function satisfy a reasonably weak condition we call distillation, then we can improve regret bounds by replacing the set of state-action pairs with the set of state-action pairs on which the predictions are grossly inaccurate. This improvement holds for both uniform regret bounds and gap-based ones. Further, we are able to achieve this property with an algorithm that achieves sublinear regret when given arbitrary predictions (i.e., even those which are not a distillation). Our work extends a recent line of work on algorithms with predictions, which has typically focused on simple online problems such as caching and scheduling, to the more complex and general problem of reinforcement learning.
We consider the problem of convex function chasing with black-box advice, where an online decision-maker aims to minimize the total cost of making and switching between decisions in a normed vector space, aided by bla...
详细信息
We consider the problem of convex function chasing with black-box advice, where an online decision-maker aims to minimize the total cost of making and switching between decisions in a normed vector space, aided by black-box advice such as the decisions of a machine-learned algorithm. The decision-maker seeks cost comparable to the advice when it performs well, known as consistency, while also ensuring worst-case robustness even when the advice is adversarial. We first consider the common paradigm of algorithms that switch between the decisions of the advice and a competitive algorithm, showing that no algorithm in this class can improve upon 3-consistency while staying robust. We then propose two novel algorithms that bypass this limitation by exploiting the problem's convexity. The first, INTERP, achieves (root 2 + epsilon)-consistency and O(C/C-2)-robustness for any epsilon > 0, where C is the competitive ratio of an algorithm for convex function chasing or a subclass thereof. The second, BDINTERP, achieves (1 + epsilon)-consistency and O (CD/c)-robustness when the problem has bounded diameter D. Further, we show that BDINTERP achieves near-optimal consistency-robustness trade-off for the special case where cost functions are alpha-polyhedral.
暂无评论