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

robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes

INFORMATION PROCESSING LETTERS 2022年 174卷

作者： Levin, Asaf Technion Fac Ind Engn & Management IL-32000 Haifa Israel

Preemptive scheduling problems of minimizing the makespan on parallel machines are basic problems. Motivated by sensitivity analysis and online algorithms, we investigate the problem of designing robust algorithms that are faced with the input one job at a time, but unlike online algorithms they are allowed to modify a small portion of the solution whenever a new job is released. For the settings of uniformly related machines, it is known that such algorithms cannot maintain an optimal solution (for general input sequences). Thus, we consider the semi-online case where the job sequence has non-increasing job sizes and design an optimal algorithm with migration factor 1. Previously such result was known only for the case of identical machines where it holds for an arbitrary input sequence. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Scheduling robust algorithms Migration factor Online algorithms Analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

robust algorithms for Online k-means Clustering 31

Robust Algorithms for Online k-means Clustering

引用

31st International Conference on Algorithmic Learning Theory (ALT)

作者： Bhaskara, Aditya Ruwanpathirana, Aravinda Kanchana Univ Utah Sch Comp Salt Lake City UT 84112 USA

In the online version of the classic k-means clustering problem, the points of a dataset u(1), u(2),... arrive one after another in an arbitrary order. When the algorithm sees a point, it should either add it to the set of centers, or let go of the point. Once added, a center cannot be removed. The goal is to end up with set of roughly k centers, while competing in k-means objective value with the best set of k centers in hindsight. Online versions of k-means and other clustering problem have received significant attention in the literature. The key idea in many algorithms is that of adaptive sampling: when a new point arrives, it is added to the set of centers with a probability that depends on the distance to the centers chosen so far. Our contributions are as follows: 1. We give a modified adaptive sampling procedure that obtains a better approximation ratio (improving it from logarithmic to constant). 2. Our main result is to show how to perform adaptive sampling when data has outliers (>> k points that are potentially arbitrarily far from the actual data, thus rendering distance-based sampling prone to picking the outliers). 3. We also discuss lower bounds for k-means clustering in an online setting.

关键词： Online algorithms k-means clustering robust algorithms

来源：评论

学校读者我要写书评

暂无评论

robust adaptive algorithms for fast principal component analysis

引用

DIGITAL SIGNAL PROCESSING 2022年第0期127卷

作者： Bekhtaoui, Zineb Abed-Meraim, Karim Meche, Abdelkrim Univ Sci & Technol Oran Mohamed Boudiaf USTOMB Lab Signaux & Images BP 1505 Bir El Djir Oran Algeria Univ Orleans PRISME Lab Orleans France

In this paper, we investigate the robust estimation of the principal eigenvectors of multivariate observations in an adaptive scheme. Indeed, this problem known as PCA (Principal Component Analysis) has already many efficient solutions in batch or non-impulsive noise environment. Our objective is to develop fast adaptive methods for the PCA when the observed data is corrupted by impulsive noise or outliers or in the case of missing data. Hence, different low complexity algorithms are introduced for the estimation and tracking of the desired principal components in the three previous scenarios. Their effectiveness is illustrated via simulation experiments and comparative study. (C) 2022 Elsevier Inc. All rights reserved.

关键词： PCA Eigenvectors tracking Givens rotation robust algorithms Linear complexity

来源：评论

学校读者我要写书评

暂无评论

robust algorithms for Low-Rank and Sparse Matrix Models

Robust Algorithms for Low-Rank and Sparse Matrix Models

引用

作者： Moore, Brian University of Michigan

Data in statistical signal processing problems is often inherently matrix-valued, and a natural first step in working with such data is to impose a model with structure that captures the distinctive features of the underlying data. Under the right model, one can design algorithms that can reliably tease weak signals out of highly corrupted data. In this thesis, we study two important classes of matrix structure: low-rankness and sparsity. In particular, we focus on robust principal component analysis (PCA) models that decompose data into the sum of low-rank and sparse (in an appropriate sense) components. robust PCA models are popular because they are useful models for data in practice and because efficient algorithms exist for solving them. This thesis focuses on developing new robust PCA algorithms that advance the state-of-the-art in several key respects. First, we develop a theoretical understanding of the effect of outliers on PCA and the extent to which one can reliably reject outliers from corrupted data using thresholding schemes. We apply these insights and other recent results from low-rank matrix estimation to design robust PCA algorithms with improved low-rank models that are well-suited for processing highly corrupted data. On the sparse modeling front, we use sparse signal models like spatial continuity and dictionary learning to develop new methods with important adaptive representational capabilities. We also propose efficient algorithms for implementing our methods, including an extension of our dictionary learning algorithms to the online or sequential data setting. The underlying theme of our work is to combine ideas from low-rank and sparse modeling in novel ways to design robust algorithms that produce accurate reconstructions from highly undersampled or corrupted data. We consider a variety of application domains for our methods, including foreground-background separation, photometric stereo, and inverse problems such as video inpainting and d

关键词： machine learning signal processing optimization statistics robust algorithms dictionary learning Thesis

来源：评论

学校读者我要写书评

暂无评论

robust algorithms for Preemptive Scheduling

引用

ALGORITHMICA 2014年第1期69卷 26-57页

作者： Epstein, Leah Levin, Asaf Univ Haifa Dept Math IL-31905 Haifa Israel Technion Israel Inst Technol Fac Ind Engn & Management IL-32000 Haifa Israel

Preemptive scheduling problems on parallel machines are classic problems. Given the goal of minimizing the makespan, they are polynomially solvable even for the most general model of unrelated machines. In these problems, a set of jobs is to be assigned to run on a set of m machines. A job can be split into parts arbitrarily and these parts are to be assigned to time slots on the machines without parallelism, that is, for every job, at most one of its parts can be processed at each time. Motivated by sensitivity analysis and online algorithms, we investigate the problem of designing robust algorithms for constructing preemptive schedules. robust algorithms receive one piece of input at a time. They may change a small portion of the solution as an additional part of the input is revealed. The capacity of change is based on the size of the new piece of input. For scheduling problems, the supremum ratio between the total size of the jobs (or parts of jobs) which may be re-scheduled upon the arrival of a new job j, and the size of j, is called migration factor. We design a strongly optimal algorithm with the migration factor for identical machines. Strongly optimal algorithms avoid idle time and create solutions where the (non-increasingly) sorted vector of completion times of the machines is lexicographically minimal. In the case of identical machines this results not only in makespan minimization, but the created solution is also optimal with respect to any a"" (p) norm (for p > 1). We show that an algorithm of a smaller migration factor cannot be optimal with respect to makespan or any other a"" (p) norm, thus the result is best possible in this sense as well. We further show that neither uniformly related machines nor identical machines with restricted assignment admit an optimal algorithm with a constant migration factor. This lower bound holds both for makespan minimization and for any a"" (p) norm. Finally, we analyze the case of two machines and show that in thi

关键词： Preemptive scheduling Migration factor robust algorithms

来源：评论

学校读者我要写书评

暂无评论

Variants and objectives for ordinal scheduling

引用

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2025年 1-36页

作者： Epstein, Leah Univ Haifa Fac Nat Sci Dept Math Haifa Israel

In ordinal scheduling problems, jobs are presented sorted by non-increasing sizes. However, it is not known in advance how many jobs of positive sizes will be presented, and what their exact sizes will be. This information is revealed only when the algorithm terminates. We analyze several variants for this problem with different objectives. The main studied model is where the number of machines m >= 2 is also not known in advance, and only an upper bound M >= m is given. Jobs have to be partitioned into M inseparable groups called bags, which will be combined by the algorithm afterwards. The bags are to be merged one by one, where merging is applied until the actual number of machines m is reached, and the output consists of the m bags. We analyze this model with respect to maximization of the minimum load. We also discuss a variant where the merging process is based on the knowledge of m but not on job sizes, and we study additional objectives including makes- pan minimization.

关键词： Ordinal scheduling robust algorithms Makespan Load maximization

来源：评论

学校读者我要写书评

暂无评论

robust Subspace Tracking with Contamination Mitigation via α-Divergence 48

Robust Subspace Tracking with Contamination Mitigation via ...

引用

48th IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2023

作者： Thanh, Le Trung Rekavandi, Aref Miri Seghouane, Abd-Krim Abed-Meraim, Karim University of Orléans Orléans France Vnu University of Engineering and Technology Hanoi Viet Nam University of Melbourne Melbourne Australia

ISBN: (纸本)9781728163277

We studied the problem of robust subspace tracking (RST) in contaminated environments. Leveraging the fast approximated power iteration and α-divergence, a novel robust algorithm called αFAPI was developed for tracking the underlying principal subspace of streaming data over time. αFAPI is fast and it outperforms many RST methods while only having a low complexity linear to the data dimension. Some experiments were conducted to illustrate the performance of αFAPI. © 2023 IEEE.

关键词： contamination non-Gaussian noises robust algorithms Subspace tracking α-divergence

来源：评论

学校读者我要写书评

暂无评论

Identifying outbreaks in sewer networks: An adaptive sampling scheme under network's uncertainty

引用

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA 2024年第14期121卷 1页

作者： Baboun, Jose Beaudry, Isabelle S. Castro, Luis M. Gutierrez, Felipe Jara, Alejandro Rubioa, Benjamin Verschaea, Jose Pontificia Univ Catolica Chile Inst Math & Computat Engn Fac Matemat Santiago 7820436 Chile Pontificia Univ Catolica Chile Inst Math & Computat Engn Fac Ingn Santiago 7820436 Chile Mt Holyoke Coll Dept Math & Stat South Hadley MA 01075 USA Pontificia Univ Catolica Chile Dept Stat Santiago 7820436 Chile Pontificia Univ Catolica Chile MiDaS Ctr Discovery Struct Complex Data Santiago 7820436 Chile Pontificia Univ Catolica Chile Dept Comp Sci Santiago 7820436 Chile

Motivated by the implementation of a SARS-Cov-2 sewer surveillance system in Chile during the COVID-19 pandemic, we propose a set of mathematical and algorithmic tools that aim to identify the location of an outbreak under uncertainty in the network structure. Given an upper bound on the number of samples we can take on any given day, our framework allows us to detect an unknown infected node by adaptively sampling different network nodes on different days. Crucially, despite the uncertainty of the network, the method allows univocal detection of the infected node, albeit at an extra cost in time. This framework relies on a specific and well-chosen strategy that defines new nodes to test sequentially, with a heuristic that balances the granularity of the information obtained from the samples. We extensively tested our model in real and synthetic networks, showing that the uncertainty of the underlying graph only incurs a limited increase in the number of iterations, indicating that the methodology is applicable in practice.

关键词： wastewater-based epidemiology public health surveillance systems robust algorithms search in uncertain trees

来源：评论

学校读者我要写书评

暂无评论

Assessment methods for inter-laboratory comparisons of the dicentric assay

引用

INTERNATIONAL JOURNAL OF RADIATION BIOLOGY 2023年第3期99卷 431-438页

作者： Gonzalez Mesa, Jorge Ernesto Holladay, Bret Higueras, Manuel Di Giorgio, Marina Barquinero, Joan Francesc Ctr Protecc & Higiene Radiac Calle 20 4113 Havana 11400 Cuba Calif Polytech State Univ San Luis Obispo Stat Dept San Luis Obispo CA 93407 USA Univ La Rioja Sci Computat & Technol Innovat Ctr SCoTIC Logrono Spain Univ La Rioja Dept Matemat & Comp Logrono Spain Autoridad Regulatoria Nucl Buenos Aires DF Argentina Univ Autonoma Barcelona Dept Biol Anim Biol Vegetal & Ecol Barcelona Spain

Purpose To test the performance of different algorithms that can be used in inter-laboratory comparisons based on dicentric chromosome analysis, and to evaluate the impact of considering a priori values different to calculate individual laboratory performance based on the ionizing radiation dose estimation. Methods Mean and standard deviation estimations in inter-laboratory comparisons are tested on simulated data and data from previously published inter-laboratory comparisons using three robust algorithms, Algorithm A, Algorithm B and Q/Hampel, all programmed in R-project language and implemented in a Shiny application. The simulated data were generated assuming three different probabilities to contaminate inter-laboratory comparisons samples with atypical dose values. Comparison between different algorithms was also done using published exercises where blood samples were irradiated at 0 and 0.7 Gy that represent a challenge for the assessment of an inter-laboratory comparison. Results The best performance was obtained with the Q/Hampel algorithm for the estimation of the dose mean and with the Algorithm B for the estimation of the dose standard deviation under the conditions tested in the simulations. The Q/Hampel algorithm showed the best performance when non-irradiated samples were evaluated and there was a high proportion of identical values. The presence identical values cause the Algorithm B to fail. Real examples illustrating the need to consider standard deviation priors, and the need to use algorithms resistant to a high proportion of identical values are presented. Conclusions Q/Hampel algorithm is a serious candidate to estimate the dose mean in the inter-laboratory comparisons, and to estimate both parameters when the proportion of identical values equals or higher than the half of the results. When the proportion of identical values is less than the half of the results, the Algorithm B should be considered as a candidate to estimate the standard deviat

关键词： Dicentric assay laboratory comparisons robust algorithms Shiny application

来源：评论

学校读者我要写书评

暂无评论

A/B Testing and Best-arm Identification for Linear Bandits with robustness to Non-stationarity 27

A/B Testing and Best-arm Identification for Linear Bandits w...

引用

27th International Conference on Artificial Intelligence and Statistics (AISTATS)

作者： Xiong, Zhihan Camilleri, Romain Fazel, Maryam Jain, Lalit Jamieson, Kevin Univ Washington Seattle WA 98195 USA

We investigate the fixed-budget best-arm identification (BAI) problem for linear bandits in a potentially non-stationary environment. Given a finite arm set X subset of R-d, a fixed budget T, and an unpredictable sequence of parameters {theta(t)}(t=1)(T), an algorithm will aim to correctly identify the best arm x* := arg max(x is an element of X) x(inverted perpendicular) Sigma(T)(t=1) theta(t) with probability as high as possible. Prior work has addressed the stationary setting where theta(t) = theta(1) for all t and demonstrated that the error probability decreases as exp(-T/rho*) for a problem-dependent constant rho*. But in many real-world A/B/n multivariate testing scenarios that motivate our work, the environment is non-stationary and an algorithm expecting a stationary setting can easily fail. For robust identification, it is well-known that if arms are chosen randomly and non-adaptively from a G-optimal design over X at each time then the error probability decreases as exp(-T Delta(2)((1))/d), where Delta((1)) = min(x not equal x*)(x*-x)(inverted perpendicular)1/T Sigma(T)(t=1) theta(t). As there exist environments where Delta(2)((1))/d << 1/rho*, we are motivated to propose a novel algorithm P1-RAGE that aims to obtain the best of both worlds: robustness to non-stationarity and fast rates of identification in benign settings. We characterize the error probability of P1-RAGE and demonstrate empirically that the algorithm indeed never performs worse than G-optimal design but compares favorably to the best algorithms in the stationary setting.

关键词： A/B testing fixed-budget best-arm identification non-stationary linear bandits robust algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：