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

25th International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Soma, Tasuku Tung, Kam Chuen Yoshida, Yuichi Inst Stat Math Tokyo Japan Univ Waterloo Waterloo ON Canada Natl Inst Informat Tokyo Japan

ISBN: (纸本)9783031598340;9783031598357

We provide the first online algorithm for spectral hypergraph sparsification. In the online setting, hyperedges with positive weights are arriving in a stream, and upon the arrival of each hyperedge, we must irrevocably decide whether or not to include it in the sparsifier. Our algorithm produces an (epsilon, delta)-spectral sparsifier with multiplicative error e and additive error delta that has O(epsilon(-2) n log n log r log(1+ epsilon W/delta n)) hyperedges with high probability, where epsilon, delta is an element of (0, 1), n is the number of nodes, r is the rank of the hypergraph, and W is the sum of edge weights. The space complexity of our algorithm is O(n(2)), while previous algorithms required space complexity Omega(m), where m is the number of hyperedges. This provides an exponential improvement in the space complexity since m can be exponential in n.

关键词： online algorithms Hypergraph Sparsification Spectral algorithms Generic Chaining

来源：评论

学校读者我要写书评

暂无评论

online algorithms to schedule a proportionate flexible flow shop of batching machines

引用

JOURNAL OF SCHEDULING 2022年第6期25卷 643-657页

作者： Hertrich, Christoph Weiss, Christian Ackermann, Heiner Heydrich, Sandy Krumke, Sven O. Tech Univ Kaiserslautern Dept Math D-67663 Kaiserslautern Germany Tech Univ Berlin Inst Math D-10623 Berlin Germany Fraunhofer Inst Ind Math ITWM Dept Optimizat D-67663 Kaiserslautern Germany

This paper is the first to consider online algorithms to schedule a proportionate flexible flow shop of batching machines (PFFB). The scheduling model is motivated by manufacturing processes of individualized medicaments, which are used in modern medicine to treat some serious illnesses. We provide two different online algorithms, proving also lower bounds for the offline problem to compute their competitive ratios. The first algorithm is an easy-to-implement, general local scheduling heuristic. It is 2-competitive for PFFBs with an arbitrary number of stages and for several natural scheduling objectives. We also show that for total/average flow time, no deterministic algorithm with better competitive ratio exists. For the special case with two stages and the makespan or total completion time objective, we describe an improved algorithm that achieves the best possible competitive ratio phi = 1+root 5/2 the golden ratio. All our results also hold for proportionate (non-flexible) flow shops of batching machines (PFB) for which this is also the first paper to study online algorithms.

关键词： Planning of pharmaceutical production Proportionate flow shop Flexible flow shop Botching machines online algorithms Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Network Robustness Under Connectivity Constraints

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2022年第4期9卷 2266-2277页

作者： Muthirayan, Deepan Khargonekar, Pramod P. Univ Calif Irvine Dept Elect Engn & Comp Sci Irvine CA 92697 USA

In this paper, we present algorithms for designing networks that are robust to node failures with minimal or limited number of links. We present algorithms for both the static network setting and the dynamic network setting;setting where new nodes can arrive in the future. For the static setting, we present algorithms for constructing the optimal network in terms of the number of links used for a given node size and the number of nodes that can fail. We then consider the dynamic setting where it is disruptive to remove any of the older links. For this setting, we present online algorithms for two cases: (i) when the number of nodes that can fail remains constant and (ii) when only the proportion of the nodes that can fail remains constant. We show that the proposed algorithm for the first case saves nearly 3/4th of the total possible links at any point of time. We then present algorithms for various levels of the fraction of the nodes that can fail and characterize their link usage. We show that when 1/2 the number of nodes can fail at any point of time, the proposed algorithm saves nearly 1/2 of the total possible links at any point of time. We show that when the number of nodes that can fail is limited to the fraction 1/(2 m) (m is an element of N), the proposed algorithm saves nearly as much as (1 - 1/2 m) of the total possible links at any point of time. We also show that when the number of nodes that can fail at any point of time is 1/2 of the number of nodes plus n, n is an element of N, the number of links saved by the proposed algorithm reduces only linearly in n. We conjecture that the saving ratio achieved by the algorithms we present is optimal for the dynamic setting.

关键词： Dynamic networks online algorithms Network robustness optimal networks

来源：评论

学校读者我要写书评

暂无评论

online algorithms for the Interval Scheduling Problem in the Cloud: Affinity Pair Threshold Based Approaches

IEEE TRANSACTIONS ON SUSTAINABLE COMPUTING

引用

IEEE TRANSACTIONS ON SUSTAINABLE COMPUTING 2022年第2期7卷 441-455页

作者： Oikonomou, Panagiotis Tziritas, Nikos Loukopoulos, Thanasis Theodoropoulos, Georgios Hanai, Masatoshi Khan, Samee U. Southern Univ Sci & Technol Dept Comp Sci & Engn Shenzhen 518055 Guangdong Peoples R China Univ Thessaly Dept Comp Sci & Telecommun Lamia 35131 Greece Univ Thessaly Dept Comp Sci & Biomed Informat Lamia 35131 Greece Mississippi State Univ Dept Elect & Comp Engn Starkville MS 39762 USA

In the interval scheduling problem, jobs have known start and end times (referred to as job intervals) and must be assigned to processing nodes for their whole duration. Although the problem originally stems from the resource allocation demands of resident processes in operating systems, it found a renewed interest in the Cloud context, both in IaaS and SaaS, since reservations for virtual machines and services often have known activation intervals. A common objective of interval scheduling is to minimize busy time of machines which relates (among others) to minimizing the number of machines participating in the computation. As a consequence, bin packing techniques have been applied in the past. In this paper we tackle the online version of the problem, whereby future job arrivals are unknown. We propose novel algorithms that work as a pre-processing step to any bin packing scheme by offering recommendations that are enforced in all packing decisions. Job overlaps are used to characterize pairwise job affinity and subsequently provide threshold based job allocation recommendations. Thresholds are calculated using lower bound theoretical analysis upon two extreme workloads (sparse and dense). Experimental evaluation using real world workloads illustrates the merits of our approach against state-of-the-art algorithms.

关键词： Task analysis Servers Scheduling Resource management Optimal scheduling Energy consumption Computer science Interval scheduling bin packing online algorithms resource allocation

来源：评论

学校读者我要写书评

暂无评论

From Batch to Stream: Automatic Generation of online algorithms

引用

PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL 2024年第PLDI期8卷 1014-1039页

作者： Wang, Ziteng Pailoor, Shankara Prakash, Aaryan Wang, Yuepeng Dillig, Isil Univ Texas Austin Austin TX 78712 USA Simon Fraser Univ Burnaby BC Canada

online streaming algorithms, tailored for continuous data processing, offer substantial benefits but are often more intricate to design than their offline counterparts. This paper introduces a novel approach for automatically synthesizing online streaming algorithms from their offline versions. In particular, we propose a novel methodology, based on the notion of relational function signature (RFS), for deriving an online algorithm given its offline version. Then, we propose a concrete synthesis algorithm that is an instantiation of the proposed methodology. Our algorithm uses the RFS to decompose the synthesis problem into a set of independent subtasks and uses a combination of symbolic reasoning and search to solve each subproblem. We implement the proposed technique in a new tool called Opera and evaluate it on over 50 tasks spanning two domains: statistical computations and online auctions. Our results show that Opera can automatically derive the online version of the original algorithm for 98% of the tasks. Our experiments also demonstrate that Opera significantly outperforms alternative approaches, including adaptations of SyGuS solvers to this problem as well as two of Opera's own ablations.

关键词： Program Synthesis online algorithms Incremental Computation Stream Processing

来源：评论

学校读者我要写书评

暂无评论

Parallel online algorithms for the Bin Packing Problem

引用

ALGORITHMICA 2023年第1期85卷 296-323页

作者： Fekete, Sandor P. Grosse-Holz, Jonas Keldenich, Phillip Schmidt, Arne TU Braunschweig Dept Comp Sci Braunschweig Germany

We study parallel online algorithms: For some fixed integer k, a collective of k parallel processes that perform online decisions on the same sequence of events forms a k-copy algorithm. For any given time and input sequence, the overall performance is determined by the best of the k individual total results. Problems of this type have been considered for online makespan minimization;they are also related to optimization with advice on future events, i.e., a number of bits available in advance. Parallel online algorithms are also of interest in practical scenarios in which redundancy is used for hedging against undesired outcomes. We develop PREDICTIVE HARMONIC(3) (PH3), a relatively simple family of k-copy algorithms for the online Bin Packing Problem, whose joint competitive factor converges to 1.5 for increasing k. In particular, we show that k = 6 suffices to guarantee a factor of 1.5714 for PH3, which is better than 1.57829, the performance of the best known 1-copy algorithm ADVANCED HARMONIC, while k = 11 suffices to achieve a factor of 1.5406, beating the known lower bound of 1.54278 for a single online algorithm. In the context of online optimization with advice, our approach implies that 4 bits suffice to achieve a factor better than this bound of 1.54278, which is considerably less than the previous bound of 15 bits.

关键词： online algorithms Bin packing Redundancy Competitive analysis k-copy online algorithms

来源：评论

学校读者我要写书评

暂无评论

Multiprocessor jobs, preemptive schedules, and one-competitive online algorithms

引用

OPERATIONS RESEARCH LETTERS 2023年第6期51卷 583-590页

作者： Sgall, Jiri Woeginger, Gerhard J. Charles Univ Prague Comp Sci Inst Fac Math & Phys Malostranske Nam 2 CZ-11800 Prague 1 Czech Republic Rhein Westfal TH Aachen Dept Comp Sci Aachen Germany

We study online preemptive makespan minimization on m parallel machines, where multiprocessor jobs arrive over time and have widths (i.e., the number of machines used) from some fixed set W subset of {1, 2, ..., m}. For every number m of machines we concisely characterize all the sets W for which there exists a 1-competitive fully online algorithm and all the sets W for which there is a 1-competitive nearly online algorithm.(c) 2023 Elsevier B.V. All rights reserved.

关键词： online algorithms Scheduling Parallel jobs Preemption Makespan

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Prize-Collecting Optimization Problems 23rd

Online Algorithms for Prize-Collecting Optimization Problems

引用

23rd International Conference on Enterprise Information Systems (ICEIS)

作者： Markarian, Christine El-Kassar, Abdul Nasser Univ Dubai Dept Engn & Informat Technol Dubai U Arab Emirates Lebanese Amer Univ Dept Informat Technol & Operat Management Beirut Lebanon

ISBN: (纸本)9783031089657;9783031089640

Many real-world optimization problems are online by nature, requiring provably-good decisions that need to be made in the present without knowing the future. At the heart of such decisions are online algorithms. The input to an online algorithm is not given all at once but arrives in portions over time. The online algorithm reacts to each arriving portion while targeting the optimization objective against the entire input. In this paper, we consider a well-established branch of online optimization problems in which some input portions can be rejected by paying an associated penalty and these penalties are incorporated into the objective function. We study the online prize-collecting variants of three well-known optimization problems: Connected Dominating Set, Vertex Cover, and Non-metric Facility Location, and propose online algorithms for these variants, measured using the competitive analysis framework. The latter compares, in the worst case, the performance of the online algorithm to the optimal offline solution constructed given all the input sequence at once. Furthermore, we extend the study of prize-collecting optimizations problems to the leasing setting in which resources are leased, rather than bought, for different durations and prices.

关键词： Optimization online algorithms Competitive analysis Prize-collecting Penalties Facility location Vertex cover Connected dominating set Leasing

来源：评论

学校读者我要写书评

暂无评论

online algorithms with Learned Predictions

Online Algorithms with Learned Predictions

引用

作者： Anand, Keerti Duke University

学位级别：Ph.D., Doctor of Philosophy

Optimization under uncertainty is a classic theme in the fields of algorithm design and machine learning. The traditional design of online algorithms have however proved to be insufficient for practical instances, since it only tries to optimize for the worst-case (but possibly highly unlikely) future scenarios. The availability of data and the advent of powerful machine learning paradigms has led to a promising approach of leveraging predictions about the future to aid in making decisions under uncertainty. This motivates us to explore whether algorithm design can go beyond the worst-case, i.e., is it possible to design efficient algorithms that perform well for the typical instances, while retaining a suitable robustness guarantee for the worst-case instance? This entails our vision of combining the power of Machine Learning and Algorithm design to get the best of both worlds. This can be categorized into two inter-dependent parts : (1) How to design the prediction pipeline to generate forecasts about the future unknowns and (2) Given such predictions, how to re-design the decision-making algorithm to best leverage them. In this thesis, we investigate both of these questions, and summarize the key contributions as follows: Rent or Buy Problem: We investigate the rent-or-buy problem and design a simple online algorithm that leverages predictions from classification black-box model whose performance is directly dependent on the prediction error of the classification task. We then demonstrate that by incorporating the optimization benchmarks in prediction model leads to significantly better performance, while maintaining a worst-case adversarial result. online Search: We define a general online search framework that captures classic problems like (generalized) ski rental, bin packing, minimum makespan scheduling, etc. We then model the task of making predictions as a regression problem and show nearly tight bounds on the sample complexity of this regression problem.

关键词： online algorithms Learned predictions Machine Learning

来源：评论

学校读者我要写书评

暂无评论

online algorithms with Predictions

Online Algorithms with Predictions

引用

作者： Sun, Kevin Duke University

学位级别：Ph.D., Doctor of Philosophy

Mitigating uncertainty due to our inherent inability to predict the future is the founding pillar of online algorithms. However, the standard "worst-case" assumption is often too pessimistic, and fails to distinguish between the performance of algorithms in practice. At the same time, there has also been a proliferation of advancements in the field of machine learning, which allows us to generate predictions about the future based on the past. Thus, a natural question arises: How can we use machine-learned predictions about the future to design algorithms that can provably overcome the best worst-case performance guarantees? In this dissertation, we address this question in multiple contexts. First, we consider paging, a classical problem in online algorithms. There are n pages, each with an associated weight, and there is a cache of size k < n. At each time step, some page is requested, and if it is not in the cache, then the algorithm must evict a page in the cache and fetch the requested page. The goal is to minimize the total weight of fetched pages. For this problem, we show that two existing prediction models do not asymptotically benefit any algorithm. We then define a new prediction model, show that it allows us to obtain a 2-competitive algorithm, and prove various upper and lower bounds in terms of the error in the predictions. Second, we consider a different prediction model, which we apply to unweighted paging and online covering problems. This model, at each time step, reveals some information about the optimal solution with (small) probability, and does not reveal any meaningful information otherwise. (The exact definition of this revealed information depends on the specific problem.) For paging, we analyze the algorithm that simply follows the prediction, and give a more sophisticated algorithm that achieves the optimal competitive ratio up to a constant factor. For a general class of online covering problems, we give an algorithm that, up to constant

关键词： online algorithms Uncertainty Machine learning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：