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

A best possible online algorithm for minimizing the total completion time and the total soft penalty cost

OPTIMIZATION LETTERS 2024年第1期18卷 319-338页

作者： Ma, Ran Xu, Juannian Zhang, Yuzhong Qingdao Univ Technol Sch Management Engn Qingdao 266525 Peoples R China Southwestern Univ Finance & Econ Sch Business Adm Chengdu 611130 Peoples R China Qufu Normal Univ Inst Operat Res Sch Management Rizhao 276826 Peoples R China

Green high-performance concrete is widely adopted in the construction industry to reduce building energy consumption and enhance quality. Prompt delivery of green high-performance concrete is vital for successful project completion because the processes relating to green high-performance concrete are the critical path in most cases, namely that the project delay will occur if the works involving green high-performance concrete are delayed caused by late delivery of green high-performance concrete. This research proposes an online scheduling model, which takes into account the idle time of green high-performance concrete in manufacturing, that is the time from release until start, in order to improve prompt delivery of green high-performance concrete. Formally, there are irrelevant jobs arriving online over time and the fundamental knowledge of each job J(j) is not declared until it is released at time r(j). Our objective is to minimize the total completion time plus the total soft penalty cost of all jobs, where soft penalty cost of job J(j) is alpha(S-j - r(j)) with soft penalty coefficient > 0, Sj and rj are starting processing time and release date of job J(j), respectively. For this problem, by applying the technique "Peeling Onion", it is explicitly derived that the classic online algorithm DSPT is best possible with competitive ratio 2 + alpha.

关键词： Scheduling online algorithms Optimization Engineering management Soft penalty

来源：评论

学校读者我要写书评

暂无评论

Landscape and Taxonomy of online Parser-Supported Log Anomaly Detection Methods

引用

IEEE ACCESS 2024年 12卷 78193-78218页

作者： Lupton, Scott Washizaki, Hironori Yoshioka, Nobukazu Fukazawa, Yoshiaki Waseda Univ Dept Comp Sci & Commun Engn Tokyo 1698050 Japan Nomura Secur Co Ltd Tokyo 1008130 Japan Waseda Univ Res Inst Sci & Engn Tokyo 1698555 Japan QAML Inc Tokyo 1020074 Japan Univ Human Environm Dept Environm Sci Matsuyama 7900825 Japan

As production system estates become larger and more complex, ensuring stability through traditional monitoring approaches becomes more challenging. Rule-based monitoring is common in industrial settings, but it has limitations. These include the difficulty of crafting rules capable of detecting unforeseen issues and the burden of manually maintaining rule sets. A potential solution to effectively manage complex system states is log anomaly detection. Workflows for log anomaly detection utilize several fundamental components. These include preprocessors for data cleansing, parsers to extract structured information from raw log data, encoding algorithms to convert extracted data into usable model input features, anomaly detection methods to isolate anomalous signals, and feedback mechanisms to incrementally improve model performance. This study explores the current state of research into online parser-supported log anomaly detection methods, investigates recent research trends, compares the performances of parser and anomaly detection methods using common public datasets and metrics, and assesses their performance evolution over time. Additionally, it classifies available methods using a newly introduced taxonomy, highlights current research gaps, and recommends future research directions.

关键词： Anomaly detection Bibliographies Systematics Measurement Market research Deep learning Taxonomy Algorithm design and analysis online services Log parsing log template extraction online algorithms anomaly detection

来源：评论

学校读者我要写书评

暂无评论

online EDGE COLORING VIA TREE RECURRENCES AND CORRELATION DECAY\ast

引用

SIAM JOURNAL ON COMPUTING 2024年第1期53卷 87-110页

作者： Kulkarni, Janardhan Liu, Yang p. Sah, Ashwin Sawhney, Mehtaab s. Tarnawski, Jakub Microsoft Res Redmond WA 98052 USA Stanford Univ Dept Math Stanford CA 94305 USA MIT Cambridge MA 02139 USA MIT Commack NY 11725 USA

We give an online algorithm that with high probability computes a ( e e - 1 + o(1))\Delta edge coloring on a graph G with maximum degree \Delta = \omega(logn) under online edge arrivals against oblivious adversaries, making first progress on the conjecture of Bar -Noy, Motwani, and Naor in this general setting. Our algorithm is based on reducing to a matching problem on locally treelike graphs, and then applying a tree recurrence based approach for arguing correlation decay.

关键词： edge coloring online algorithms tree recurrences correlation decay Redmond.

来源：评论

学校读者我要写书评

暂无评论

online Throughput Maximization on Unrelated Machines: Commitment is No Burden

引用

ACM TRANSACTIONS ON algorithms 2023年第1期19卷 10-10页

作者： Eberle, Franziska Megow, Nicole Schewior, Kevin London Sch Econ & Polit Sci Dept Math Loughton St London WC2A 2AE England Univ Bremen Fac Math & Comp Sci Bibliothekstr 5 D-28213 Bremen Germany Univ Southern Denmark Dept Math & Comp Sci Campusvej 55 DK-5230 Odense Denmark

We consider a fundamental online scheduling problem in which jobs with processing times and deadlines arrive online over time at their release dates. The task is to determine a feasible preemptive schedule on a single or multiple possibly unrelated machines that maximizes the number of jobs that complete before their deadline. Due to strong impossibility results for competitive analysis on a single machine, we require that jobs contain some slack epsilon > 0, which means that the feasible time window for scheduling a job is at least 1 + epsilon times its processing time on each eligible machine. Our contribution is two-fold: (i) We give the first non-trivial online algorithms for throughput maximization on unrelated machines, and (ii), this is the main focus of our paper, we answer the question on how to handle commitment requirements which enforce that a scheduler has to guarantee at a certain point in time the completion of admitted jobs. This is very relevant, e.g., in providing cloud-computing services, and disallows last-minute rejections of critical tasks. We present an algorithm for unrelated machines that is Theta(1/epsilon)-competitive when the scheduler must commit upon starting a job. Somewhat surprisingly, this is the same optimal performance bound (up to constants) as for scheduling without commitment on a single machine. If commitment decisions must be made before a job's slack becomes less than a delta-fraction of its size, we prove a competitive ratio of O(1/epsilon-delta) for 0 < delta < epsilon. This result nicely interpolates between commitment upon starting a job and commitment upon arrival. For the latter commitment model, it is known that no (randomized) online algorithm admits any bounded competitive ratio. While we mainly focus on scheduling without migration, our results also hold when comparing against a migratory optimal solution in case of identical machines.

关键词： Deadline scheduling throughput online algorithms competitive analysis unrelated machines migration

来源：评论

学校读者我要写书评

暂无评论

Optimal Network Protocol Selection for Competing Flows via online Learning

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2023年第8期22卷 4822-4836页

作者： Zhang, Xiaoxi Chen, Siqi Zhang, Yunfan Im, Youngbin Gorlatova, Maria Ha, Sangtae Joe-Wong, Carlee Sun Yat sen Univ Sch Comp Sci & Engn Guangzhou 510006 Guangdong Peoples R China Univ Colorado Dept Comp Sci Boulder CO 80309 USA Duke Univ Dept Elect & Comp Engn Durham NC 27708 USA Ulsan Natl Inst Sci & Technol Sch Elect & Comp Engn Ulsan 44919 South Korea Carnegie Mellon Univ Dept Elect & Comp Engn Pittsburgh PA 15213 USA

Today's Internet must support applications with increasingly dynamic and heterogeneous connectivity requirements, such as video streaming and the Internet of Things. Yet current network management practices generally rely on pre-specified network configurations, which may not be able to cope with dynamic application needs. Moreover, even the best-specified policies will find it difficult to cover all possible scenarios, given applications' increasing heterogeneity and dynamic network conditions, e.g., on volatile wireless links. In this work, we instead propose a model-free learning approach to find the optimal network policies for current network flow requirements. This approach is attractive as comprehensive models do not exist for how different policy choices affect flow performance under changing network conditions. However, it can raise new challenges for online learning algorithms: policy configurations can affect the performance of multiple flows sharing the same network resources, and this performance coupling limits the scalability and optimality of existing online learning algorithms. In this work, we extend multi-armed bandit frameworks to propose new online learning algorithms for protocol selection with provably sublinear regret under certain conditions. We validate the optimality and scalability of our algorithms through data-driven simulations and testbed experiments. (An extended abstract of this work was accepted by IEEE ICNP as a short paper Zhang et al. (2019)).

关键词： Protocols Mobile computing 5G mobile communication Topology Network topology Heuristic algorithms Bandwidth Multi-armed bandits network protocol selection online algorithms online learning

来源：评论

学校读者我要写书评

暂无评论

An improved online replenishment policy and its competitive ratio analysis for a purchase-to-order seller

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第2期46卷 1-14页

作者： Ni, Guanqun Shandong Univ Technol Business Sch Zibo 255000 Peoples R China

For a purchase-to-order seller, there is no inventory and the seller has to purchase goods to fulfill orders already placed. For each purchase, there is a constant ordering cost. For each order, delay cost will be incurred if it is not fulfilled timely. Consequently, there is a tradeoff between the ordering cost and the delay cost for the seller to make replenishment decisions minimizing the total cost. In practice it is impossible or difficult for the seller to know demand information about future orders in advance, and thus this decision-making problem is of an online fashion. In the previous work, this online problem is classified into three cases according to capacity limit and demand quantity, and a 10-competitive online policy is proposed for the general case. In the present paper, an improved 4-competitive online policy is proposed. Besides, an asymptotic lower bound of 2 is derived for this online decision-making problem.

关键词： Replenishment planning online algorithms Competitive analysis PTO

来源：评论

学校读者我要写书评

暂无评论

Improved Bounds for Open online Dial-a-Ride on the Line

引用

ALGORITHMICA 2023年第5期85卷 1372-1414页

作者： Birx, Alexander Disser, Yann Schewior, Kevin Tech Univ Darmstadt Inst Math Darmstadt Germany Tech Univ Darmstadt Grad Sch CE Darmstadt Germany Univ Southern Denmark Dept Math & Comp Sci Odense Denmark

We consider the open, non-preemptive online Dial-a-Ride problem on the real line, where transportation requests appear over time and need to be served by a single server. We give a lower bound of 2.0585 on the competitive ratio, which is the first bound that strictly separates open online Dial-a-Ride on the line from open online TSP on the line in terms of competitive analysis, and is the best currently known lower bound even for general metric spaces. On the other hand, we present an algorithm that improves the best known upper bound from 2.9377 to 2.6662. The analysis of our algorithm is tight.

关键词： Dial-a-ride on the line Elevator problem online algorithms Competitive analysis Smartstart Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

The online Broadcast Range-Assignment Problem

引用

ALGORITHMICA 2023年第12期85卷 3928-3956页

作者： de Berg, Mark Markovic, Aleksandar Umboh, Seeun William TU Eindhoven Dept Comp Sci Eindhoven Netherlands Univ Melbourne Sch Comp & Informat Syst Parkville Australia

Let P = {p(0),..., p(n-1)} be a set of points in R-d, modeling devices in a wireless network. Arange assignment assigns a range r ( pi) to each point pi is an element of P, thus inducing a directed communication graph Gr in which there is a directed edge ( pi, p j) iff dist( pi, p j) <== r ( pi), where dist( pi, p j) denotes the distance between pi and p j. The range-assignment problem is to assign the transmission ranges such that Gr has a certain desirable property, while minimizing the cost of the assignment;here the cost is given by Sigma (pi)is an element of P (r) ( pi)(alpha), for some constant alpha> 1 called the distance-power gradient. We introduce the online version of the range-assignment problem, where the points p j arrive one by one, and the range assignment has to be updated at each arrival. Following the standard in online algorithms, resources given out cannot be taken away-in our case this means that the transmission ranges will never decrease. The property we want to maintain is that Gr has a broadcast tree rooted at the first point p0. Our results include the following. center dot We prove that already inR(1), a 1-competitive algorithm does not exist. In particular, for distance-power gradient alpha = 2 any online algorithm has competitive ratio at least 1.57. center dot For points in R-1 and R-2, we analyze two natural strategies for updating the range assignment upon the arrival of a new point p j. The strategies do not change the assignment if p j is already within range of an existing point, otherwise they increase the range of a single point, as follows: Nearest- Neighbor (nn) increases the range of nn( p j), the nearest neighbor of p j, to dist( p j, nn( p j)),and Cheapest Increase (ci) increases the range of the point pi for which the resulting cost increase to be able to reach the new point p j is minimal. We give lower and upper bounds on the competitive ratio of these strategies as a function of the distance-power gradient a. We also an

关键词： Computational geometry online algorithms Range assignment Broadcast

来源：评论

学校读者我要写书评

暂无评论

More on online weighted edge coloring

引用

DISCRETE OPTIMIZATION 2023年 50卷

作者： Epstein, Leah Univ Haifa Dept Math Haifa Israel

We revisit online weighted edge coloring. In this problem, weighted edges of a graph are presented one by one, to be colored with positive integers. It is required that for every vertex, all its edges of every common color will have a total weight not exceeding 1. We provide an improved upper bound on the performance of a greedy algorithm First Fit for the case of arbitrary weights, and for the case of weights not exceeding 21. Here, the meaning of First Fit is that every edge is colored with a color of the smallest index that will keep the coloring valid. This improves the state-of-the-art with respect to online algorithms for this variant of edge coloring. We also show new lower bounds on the performance of any online algorithm with weights in (0, t1], for any integer t >= 2. (c) 2023 Elsevier B.V. All rights reserved.

关键词： online algorithms Edge coloring

来源：评论

学校读者我要写书评

暂无评论

Time Efficient Implementation for online K-Server Problem on Trees 18th

Time Efficient Implementation for Online K-Server Problem on...

引用

18th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Khadiev, Kamil Yagafarov, Maxim Kazan Fed Univ Kazan Russia

ISBN: (纸本)9789819723393;9789819723409

We consider online algorithms for the k-server problem on trees of size n. Chrobak and Larmore proposed a k-competitive algorithm for this problem that has the optimal competitive ratio. However, the existing implementations have O (k(2) + k center dot log n) or O (k(log n)(2)) time complexity for processing a query, where n is the number of nodes. We propose a new time-efficient implementation of this algorithm that has O(n) time complexity for preprocessing and O (k log k) time for processing a query. The new algorithm is faster than both existing algorithms and the time complexity for query processing does not depend on the tree size.

关键词： online algorithms k-server problem on trees time complexity time efficient implementation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：