检索结果-内蒙古大学图书馆

learning-augmented algorithms for online subset sum

JOURNAL OF GLOBAL OPTIMIZATION 2023年第2-4期87卷 989-1008页

作者： Xu, Chenyang Zhang, Guochuan Zhejiang Univ Hangzhou Peoples R China

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.

关键词： Competitive analysis Subset sum learning-augmented algorithms Untrusted predictions

来源：评论

学校读者我要写书评

暂无评论

Online State Exploration: Competitive Worst Case and learning-augmented algorithms

Online State Exploration: Competitive Worst Case and Learnin...

引用

5th International Workshop on learning with Imbalanced Domains - Theory and Applications / European Conference on Machine learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD)

作者： Im, Sungjin Moseley, Benjamin Xu, Chenyang Zhang, Ruilong Univ Calif Merced Elect Engn & Comp Sci Merced CA 95343 USA Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA East China Normal Univ Shanghai Key Lab Trustworthy Comp Shanghai Peoples R China Univ Buffalo Dept Comp Sci & Engn Buffalo NY 14068 USA

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 algorithms augmented with the prediction model. The results extend and generalize many known results in the online setting.

关键词： Online Search Online algorithms Competitive Ratio learning-augmented algorithms Worst-case Analysis

来源：评论

学校读者我要写书评

暂无评论

learning-augmented Competitive algorithms for Spatiotemporal Online Allocation with Deadline Constraints

引用

PROCEEDINGS OF THE ACM ON MEASUREMENT AND ANALYSIS OF COMPUTING SYSTEMS 2025年第1期9卷 1-49页

作者： Lechowicz, Adam Christianson, Nicolas Sun, Bo Bashir, Noman Hajiesmaili, Mohammad Wierman, Adam Shenoy, Prashant Univ Massachusetts Amherst MA 01003 USA CALTECH Pasadena CA USA Univ Waterloo Waterloo ON Canada MIT Cambridge MA USA

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.

关键词： online allocation switching costs deadline constraints carbon-aware spatiotemporal load shifting learning-augmented algorithms

来源：评论

学校读者我要写书评

暂无评论

learning-augmented Scheduling

引用

IEEE TRANSACTIONS ON COMPUTERS 2024年第11期73卷 2548-2562页

作者： Zhao, Tianming Li, Wei Zomaya, Albert Y. Univ Sydney Sch Comp Sci Sydney NSW 2006 Australia

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.

关键词： Prediction algorithms Heuristic algorithms Optimal scheduling Dynamic scheduling Single machine scheduling Scheduling algorithms Minimization learning-augmented algorithms scheduling makespan predictions

来源：评论

学校读者我要写书评

暂无评论

The Secretary Problem with Predictions

引用

MATHEMATICS OF OPERATIONS RESEARCH 2023年第2期49卷 653-1302, C2页

作者： Fujii, Kaito Yoshida, Yuichi Natl Inst Informat Tokyo 1018430 Japan

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.

关键词： learning-augmented algorithms secretary problems optimal stopping theory

来源：评论

学校读者我要写书评

暂无评论

Permutation Predictions for Non-Clairvoyant Scheduling 22

Permutation Predictions for Non-Clairvoyant Scheduling

引用

34th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Lindermayr, Alexander Megow, Nicole Univ Bremen Bremen Germany

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.

关键词： Scheduling non-clairvoyant unrelated machines competitive ratio predictions learning-augmented algorithms

来源：评论

学校读者我要写书评

暂无评论

Can Q-learning be Improved with Advice? 35

Can Q-learning be Improved with Advice?

引用

35th Conference on learning Theory (COLT)

作者： Golowich, Noah Moitra, Ankur MIT CSAIL Cambridge MA 02139 USA MIT Math SDSC Cambridge MA USA CSAIL Cambridge MA USA

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.

关键词： Reinforcement learning Q-learning learning-augmented algorithms

来源：评论

学校读者我要写书评

暂无评论

Chasing Convex Bodies and Functions with Black-Box Advice 35

Chasing Convex Bodies and Functions with Black-Box Advice

引用

35th Conference on learning Theory (COLT)

作者： Christianson, Nicolas Handina, Tinashe Wierman, Adam CALTECH Pasadena CA 91125 USA

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.

关键词： Convex body chasing online optimization learning-augmented algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal SSD Management with Predictions

引用

Proceedings of the ACM on Measurement and Analysis of Computing Systems 2025年第2期9卷 1-28页

作者： Tomer Lange Joseph (Seffi) Naor Gala Yadgar Computer Science Dept. Technion - Israel Institute of Technology Haifa Israel

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 *** 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 *** 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.

关键词： flash translation layer garbage collection learning-augmented algorithms solid-state drives

来源：评论

学校读者我要写书评

暂无评论

Robust machine-learned algorithms for efficient grid operation

Environmental Data Science

引用

Environmental Data Science 2025年 4卷 e24-e24页

作者： Christianson, Nicolas Yeh, Christopher Li, Tongxin Hosseini, Mehdi Rad, Mahdi Torabi Golmohammadi, Azarang Wierman, Adam Computing and Mathematical Sciences California Institute of Technology Pasadena CA United States School of Data Science The Chinese University of Hong Kong (Shenzhen) Guangdong Shenzhen China Beyond Limits Glendale CA United States

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. © 2025 Beyond Limits, Inc. and the Author(s).

关键词： energy systems learning-augmented algorithms machine learning robustness online algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：