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

Improved lower bound on the on-line chain partitioning of semi-orders with representation

DISCRETE MATHEMATICS 2023年第12期346卷

作者： Biro, Csaba Curbelo, Israel R. Univ Louisville Dept Math Louisville KY 40292 USA Kean Univ Dept Math & Comp Sci Union NJ 07083 USA

An on-line chain partitioning algorithm receives a poset, one element at a time, and irrevocably assigns the element to one of the chains in the partition. The on-line chain partitioning problem involves finding the minimal number of chains needed by an on-line algorithm. Chrobak and S ' lusarek considered variants of the on-line chain partitioning problem in which the elements are presented as intervals and intersecting intervals are incomparable. They constructed an on-line algorithm which uses at most 3w - 2 chains, where w is the width of the interval order, and showed that this algorithm is optimal. They also considered the problem restricted to intervals of unit-length and while they showed that first-fit needs at most 2w -1 chains, over 30 years later, it remains unknown whether this is an optimal algorithm. In this paper, we improve upon previously known bounds and show that any on-line algorithm can be forced to use [3/2 w] chains to partition an order presented in the form of its unit interval representation. As a consequence, we completely solve the problem for w = 3. Lastly, we show that loosening the restriction from unit intervals to proper intervals in the bandwidth variant allows us to improve the lower bound by w/3. (c) 2023 Elsevier B.V. All rights reserved.

关键词： on-line algorithm Chain partitioning Semiorder Bandwidth

来源：评论

学校读者我要写书评

暂无评论

Online 2-stage Stable Matching 23

Online 2-stage Stable Matching

引用

Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems

作者： Evripidis Bampis Bruno Escoffier Paul Youssef Sorbonne Université CNRS LIP6 Paris France Sorbonne Université CNRS LIP6 & Institut Universitaire de France Paris France Université Grenoble Alpes LIG Saint Martin d'hères France

ISBN: (纸本)9781450394321

We focus on an online 2-stage problem, motivated by the following situation: consider a system where students shall be assigned to universities. There is a first stage where some students apply, and a first (stable) matching M1 has to be computed. However, some students may decide to leave the system (change their plan, go to a foreign university, or to some institution not in the system). Then, in a second stage (after these deletions), we shall compute a second (final) stable matching M2. As in many situations important changes to the assignments are undesirable, the goal is to minimize the number of divorces/modifications between the two stable matchings M1 and M2. Then, how should we choose M1 and M2? We show that there is an optimal online algorithm to solve this problem. In particular, thanks to a dominance property, we show that we can optimally compute M1 without knowing the students that will leave the system. We generalize the result to some other possible modifications in the input (such as additional capacities of universities). We also tackle the case of more stages, showing that no competitive (online) algorithm can be achieved for the considered problem as soon as there are 3 stages.

关键词： 2-stage stable matching problem on-line algorithm

来源：评论

学校读者我要写书评

暂无评论

An Online algorithm for Routing an Unmanned Aerial Vehicle for Road Network Exploration Operations after Disasters under Different Refueling Strategies

引用

algorithmS 2022年第6期15卷 217-217页

作者： Reyes-Rubiano, Lorena Voegl, Jana Hirsch, Patrick Otto von Guericke Univ Operat Management D-39016 Magdeburg Germany Univ La Sabana Int Sch Econ & Adm Sci Bogota 53753 Colombia Univ Nat Resources & Life Sci Vienna Inst Prod & Logist A-331180 Vienna Austria

This paper is dedicated to studying on-line routing decisions for exploring a disrupted road network in the context of humanitarian logistics using an unmanned aerial vehicle (UAV) with flying range limitations. The exploration aims to extract accurate information for assessing damage to infrastructure and road accessibility of victim locations in the aftermath of a disaster. We propose an algorithm to conduct routing decisions involving the aerial and road network simultaneously, assuming that no information about the state of the road network is available in the beginning. Our solution approach uses different strategies to deal with the detected disruptions and refueling decisions during the exploration process. The strategies differ mainly regarding where and when the UAV is refueled. We analyze the interplay of the type and level of disruption of the network with the number of possible refueling stations and the refueling strategy chosen. The aim is to find the best combination of the number of refueling stations and refueling strategy for different settings of the network type and disruption level.

关键词： disrupted road network immediate response operations on-line algorithm refueling strategies online exploration strategies network cutting procedure labeled network

来源：评论

学校读者我要写书评

暂无评论

Novel method for the on-line estimation of low-frequency impedance of lithium-ion batteries

引用

JOURNAL OF ENERGY STORAGE 2020年 32卷

作者： Karger, Alexander Wildfeuer, Leo Maheshwari, Arpit Wassiliadis, Nikolaos Lienkamp, Markus TWAICE Technol GmbH Munich Germany Tech Univ Munich Dept Mech Engn Inst Automot Technol Munich Germany

Impedance is an important characteristic of lithium-ion batteries since it directly influences their power capability. However, battery impedance is highly dependent on the operating condition and increases over the lifetime of the battery, due to degradation of the latter. Continuous tracking of the impedance can hence provide meaningful insights into the aging status of a battery. However, the on-line determination of battery impedance parameters, especially for its low-frequency part, is a challenging task, which has not yet been solved unambiguously in literature. This work provides an algorithm for the on-line determination of battery impedance, which features a novel approach to quantifying the impedance caused by diffusion processes at low frequencies. The algorithm works by parameterizing an equivalent circuit model comprised of RC elements, which reproduces the Li-ion kinetics. The on-line functionality is enabled by parameterizing the model during parameter identification windows of battery operating data, which allow for the separation of high-frequency and lowfrequency dynamics. The developed algorithm is designed in such a way that it can in future be embedded into a low-cost microcontroller by taking into account the relevant computational and memory limitations. During experimental validation with a commercial Li-ion battery, the root-mean-square error of the simulated voltage during diverse static and dynamic loads is reduced by over 50% compared to a benchmark algorithm without the proposed approach.

关键词： Lithium-ion batteries Impedance estimation on-line algorithm Equivalent circuit model Low-frequency Degradation diagnostics

来源：评论

学校读者我要写书评

暂无评论

An FPGA multiprocessor architecture for Bayesian online change point detection using stochastic computation

引用

MICROPROCESSORS AND MICROSYSTEMS 2020年 74卷 102968-102968页

作者： Figliolia, Tomas Andreou, Andreas G. Xilinx Inc Marriottsville MD USA Johns Hopkins Univ Dept Elect & Comp Engn Baltimore MD 21218 USA

In this paper we report on an event-based stochastic architecture for the Adams/McKay Bayesian Online Change Point Detection algorithm (BOCPD) [1]. In the stochastic computational structures, probabilities are represented natively as stochastic events and computation is carried out directly with these probabilities and not probability density functions. A fully programmable BOCPD processor is synthesized in VHDL. The BOCPD algorithm with on-line learning, to perform foreground/background image segmentation with online learning. Running on a single Kintex 7 FPGA (Opal Kelly XEM7350-K410T) the architecture is capable of real-time processing a 160 x 120 pixels image, at 10 frames per second. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Changepoint analysis Changepoint detection Image segmentation Bayesian inference on-line algorithm Stochastic processing Precision on demand ASIC VHDL Probabilistic event representation

来源：评论

学校读者我要写书评

暂无评论

ISOLATED WORD RECOGNITION BY RECURSIVE HMM PARAMETER ESTIMATION algorithm

引用

COMPUTING AND INFORMATICS 2021年第2期40卷 277-297页

作者： Vaiciulyte, Jurate Sakalauskas, Leonidas Vilniaus Kolegija Univ Appl Sci Fac Elect & Informat Vilnius Lithuania Vilnius Univ Siauliai Acad Shiauliai Lithuania

Automatic speech recognition (ASR) technologies enable humans to communicate with computers. Isolated word recognition (IWR) is an important part of many known ASR systems. Minimizing the word error rate in cases of incremental learning is a unique challenge for developing an on-line ASR system. This paper focuses on on-line IWR using a recursive hidden Markov model (HMM) multivariate parameter estimation algorithm. The maximum likelihood method was used to estimate the unknown parameters of the model, and an algorithm for the adapted recursive EM algorithm for HMMs parameter estimation was derived. The resulting recursive EM algorithm is unique among its counterparts because of state transition probabilities calculation. It obtains more accurate parameter estimates compared to other algorithms of this type. In our experiment, the algorithm was implemented and adapted to several datasets for IWR. Thus, the recognition rate and algorithm convergence results are discussed in this work.

关键词： Hidden Markov models likelihood method on-line algorithm recursive EM algorithm isolated word recognition

来源：评论

学校读者我要写书评

暂无评论

Evolvable fuzzy systems from data streams with missing values: With application to temporal pattern recognition and cryptocurrency prediction

引用

PATTERN RECOGNITION LETTERS 2019年 128卷 278-282页

作者： Garcia, Cristiano Esmin, Ahmed Leite, Daniel Skrjanc, Igor Univ Fed Lavras Dept IT Management Lavras Brazil Univ Fed Lavras Dept Comp Sci Lavras Brazil Univ Fed Lavras Dept Engn Lavras Brazil Univ Ljubljana Fac Elect Engn Ljubljana Slovenia

Data streams with missing values are common in real-world applications. This paper presents an evolving granular fuzzy-rule-based model for temporal pattern recognition and time series prediction in online nonstationary context, where values may be missing. The model has a modified rule structure that includes reduced-term consequent polynomials, and is supplied by an incremental learning algorithm that simultaneously impute missing data and update model parameters and structure. The evolving Fuzzy Granular Predictor (eFGP) handles single and multiple Missing At Random (MAR) and Missing Completely At Random (MCAR) values in nonstationary data streams. Experiments on cryptocurrency prediction show the usefulness, accuracy, processing speed, and eFGP robustness to missing values. Results were compared to those provided by fuzzy and neuro-fuzzy evolving modeling methods. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Temporal pattern recognition on-line algorithm Real-time system Fuzzy system Machine learning

来源：评论

学校读者我要写书评

暂无评论

A Best on-line algorithm for Single Machine Scheduling the Equal Length Jobs with the Special Chain Precedence and Delivery Time

A Best On-line Algorithm for Single Machine Scheduling the E...

引用

4th International Conference on Graphic and Image Processing (ICGIP)

作者： Gu, Cunchang Mu, Yundong Henan Univ Technol Coll Sci Zhengzhou 450000 Peoples R China

ISBN: (纸本)9780819495662

In this paper, we consider a single machine on-line scheduling problem with the special chains precedence and delivery time. All jobs arrive over time. The chains(i) chains arrive at time r(i), it is known that the processing and delivery time of each job on the chain satisfy one special condition CD aforehand: if the job J(j)((i)) is the predecessor of the job J(k)((i)) on the chain chains(i), then they satisfy p(j)((i)) = p(k)((i)) = p >= q(j) >= q(k), i = 1,2, ..., n, where p(j) and q(j) denote the processing time and the delivery time of the job J(j) respectively. Obviously, if the arrival jobs have no chains precedence, it shows that the length of the corresponding chain is 1. The objective is to minimize the time by which all jobs have been delivered. We provide an on-line algorithm with a competitive ratio of root 2, and the result is the best possible.

关键词： Chain precedence equal length job single machine delivery time on-line algorithm

来源：评论

学校读者我要写书评

暂无评论

on-line algorithm for optimal 3D path planning

引用

COMPUTER APPLICATIONS IN ENGINEERING EDUCATION 2012年第4期20卷 713-720页

作者： Hun, Chien-Wan Chen, Hun-Chen Hwang, Ming-Fung Natl United Univ Dept Elect Engn Miaoli Taiwan Natl United Univ Dept Mech Engn Miaoli Taiwan Da Yeh Univ Liberal Arts Ctr Changhua Taiwan

The issues of automatic car operation aiming at in an unknown complex terrain are the most effective path planning and the obstacles avoiding in this complex terrain. For that, an on-line algorithm for guiding a mobile object in an unexplored terrain filled with convex polygonal obstacles is presented. The mobile object was taken as a point-size auto equipped with a sensor system, which is used to detect previously all visible parts of the obstacles surrounding it. Both the visibility and the tangent graph were modified and used in this algorithm to construct the basic concept. At each stage, the next subgoal was selected from local information provided by the sensor. Furthermore, in order to expand the algorithm to handle nonconvex polygonal obstacles and mazes, it was modified by adding backtracking and by removing visited vertices. The algorithm was implemented in MATLAB language, and several numerical examples are shown to evaluate its feasibility. Moreover, the convergence of the algorithm was examined using the visibility graph, and the performance of the algorithm was evaluated by simply comparing with other algorithms for both the length of the path and the traveling time from the initial point to the target point. (C) 2010 Wiley Periodicals, Inc. Comput Appl Eng Educ 20: 713720, 2012

关键词： on-line algorithm convex polygonal obstacle path planning

来源：评论

学校读者我要写书评

暂无评论

On-line Anomaly Detection With High Accuracy

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2018年第3期26卷 1222-1235页

作者： Xie, Kun Li, Xiaocan Wang, Xin Cao, Jiannong Xie, Gaogang Wen, Jigang Zhang, Dafang Qin, Zheng Hunan Univ Coll Comp Sci & Elect Engn Changsha 410006 Hunan Peoples R China Chinese Acad Sci Inst Comp Technol CAS Key Lab Network Data Sci & Technol Beijing Peoples R China SUNY Stony Brook Dept Elect & Comp Engn Stony Brook NY 11794 USA Hong Kong Polytech Univ Dept Comp Hong Kong Hong Kong Peoples R China Chinese Acad Sci Inst Comp Technol Network Res Ctr Beijing 100190 Peoples R China

Traffic anomaly detection is critical for advanced Internet management. Existing detection algorithms generally convert the high-dimensional data to a long vector, which compromises the detection accuracy due to the loss of spatial information of data. Moreover, they are generally designed based on the separation of normal and anomalous data in a time period, which not only introduces high storage and computation cost but also prevents timely detection of anomalies. Online and accurate traffic anomaly detection is critical but difficult to support. To address the challenge, this paper directly models the monitoring data in each time slot as a 2-D matrix, and detects anomalies in the new time slot based on bilateral principal component analysis (B-PCA). We propose several novel techniques in OnlineBPCA to support quick and accurate anomaly detection in real time, including a novel BPCA-based anomaly detection principle that jointly considers the variation of both row and column principal directions for more accurate anomaly detection, an approximate algorithm to avoid using iteration procedure to calculate the principal directions in a close-form, and a sequential anomaly algorithm to quickly update principal directions with low computation and storage cost when receiving a new data matrix at a time slot. To the best of our knowledge, this is the first work that exploits 2-D PCA for anomaly detection. We have conducted extensive simulations to compare our OnlineBPCA with the state-of-art anomaly detection algorithms using real traffic traces Abilene and GEANT. Our simulation results demonstrate that, compared with other algorithms, our OnlineBPCA can achieve significantly better detection performance with low false positive rate, high true positive rate, and low computation cost.

关键词： Anomaly detection on-line algorithm bilateral PCA

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：