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

Multi-Priority Online Scheduling with Cancellations

OPERATIONS RESEARCH 2018年第1期66卷 104-122页

作者： Wang, Xinshang Van-Anh Truong Columbia Univ Dept Ind Engn & Operat Res New York NY 10027 USA

We study a fundamental model of resource allocation in which a finite amount of service capacity must be allocated to a stream of jobs of different priorities arriving randomly over time. Jobs incur costs and may also cancel while waiting for service. To increase the rate of service, overtime capacity can be used at a cost. This model has application in healthcare scheduling, server applications, make-to-order manufacturing systems, general service systems, and green computing. We present an online algorithm that minimizes the total cost due to waiting, cancellations and overtime capacity usage. We prove that our scheduling algorithm has cost at most twice of an optimal offline algorithm. This competitive ratio is the best possible for this class of problems. We also provide extensive numerical experiments to test the performance of our algorithm and its variants.

关键词： analysis of algorithms approximations/heuristic cost analysis

来源：评论

学校读者我要写书评

暂无评论

Reachability problems for continuous chemical reaction networks

引用

NATURAL COMPUTING 2018年第2期17卷 223-230页

作者： Case, Adam Lutz, Jack H. Stull, D. M. Drake Univ Dept Math & Comp Sci Des Moines IA 50311 USA Iowa State Univ Dept Comp Sci Ames IA 50011 USA

Chemical reaction networks (CRNs) model the behavior of molecules in a well-mixed solution. The emerging field of molecular programming uses CRNs not only as a descriptive tool, but as a programming language for chemical computation. Recently, Chen, Doty and Soloveichik introduced rate-independent continuous CRNs (CCRNs) to study the chemical computation of continuous functions. A fundamental question for any CRN model is reachability, the question whether a given target state is reachable from a given start state via a sequence of reactions (a path) in the network. In this paper, we investigate CCRN-REACH, the reachability problem for rate-independent continuous chemical reaction networks. Our main theorem is that, for CCRNs, deciding reachability-and constructing a path if there is one-is computable in polynomial time. This contrasts sharply with the known exponential space hardness of the reachability problem for discrete CRNs. We also prove that the related problem Sub-CCRN-REACH, which asks about reachability in a CCRN using only a given number of its reactions, is NP-complete.

关键词： Reachability Continuous chemical reaction networks analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Multiplicative updates for polynomial root finding

引用

INFORMATION PROCESSING LETTERS 2018年第Apr.期132卷 14-18页

作者： Gillis, Nicolas Univ Mons Fac Polytech Dept Math & Operat Res Rue Houdain 9 B-7000 Mons Belgium

Let f (x) = p(x) q(x) be a polynomial with real coefficients whose roots have nonnegative real part, where p and q are polynomials with nonnegative coefficients. In this paper, we prove the following: Given an initial point x(0) > 0, the multiplicative update x(t+1) = x(t) p(X-t)/9(x(t)) (t = 0, 1,...) monotonically and linearly converges to the largest (resp. smallest) real roots off smaller (resp. larger) than x(0) if p(x(0)) < q(x(0)) (resp. q(x(0)) < p(x(0))). The motivation to study this algorithm comes from the multiplicative updates proposed in the literature to solve optimization problems with nonnegativity constraints;in particular many variants of nonnegative matrix factorization. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Polynomial root finding Multiplicative updates analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

On semi-supervised active clustering of stable instances with oracles

引用

INFORMATION PROCESSING LETTERS 2019年 151卷 105833-000页

作者： Sanyal, Deepayan Das, Swagatam Indian Stat Inst Elect & Commun Sci Unit Kolkata 700108 India

We consider the problem of semi-supervised active clustering under multiplicative perturbation stability with respect to the distance function. Stable instances have an optimal solution that does not change when the distances are perturbed. This captures the notion that the optimal solution is tolerant to measurement errors and uncertainty in the points. Semi-supervision allows us to have an oracle O which answers pairwise queries. We design efficient algorithms to solve problems of multiplicative perturbation stability for semi-supervised clustering by using an ideal as well as a noisy oracle model. We present theoretical performance guarantee of the algorithms. (C) 2019 Elsevier B.V. All rights reserved.

关键词： analysis of algorithms Semi-supervised learning Perturbation stability Noisy oracle

来源：评论

学校读者我要写书评

暂无评论

On testing substitutability

引用

INFORMATION PROCESSING LETTERS 2018年 138卷 19-21页

作者： Croitoru, Cosmina Mehlhorn, Kurt Saarland Univ Saarbrucken Germany Max Planck Inst Informat Saarbrucken Germany

papers [1] and [2] propose algorithms for testing whether the choice function induced by a (strict) preference list of length N over a universe U is substitutable. The running time of these algorithms is O (vertical bar U vertical bar(3).N-3), respectively O (vertical bar U vertical bar(2).N-3). In this note we present an algorithm with running time O (vertical bar U vertical bar(2).N-2). Note that N may be exponential in the size DUI of the universe. (C) 2018 Elsevier B.V. All rights reserved.

关键词： analysis of algorithms Choice functions Substitutability Algorithm complexity

来源：评论

学校读者我要写书评

暂无评论

Generalized mirror descents with non-convex potential functions in atomic congestion games: Continuous time and discrete time

引用

INFORMATION PROCESSING LETTERS 2018年 130卷 36-39页

作者： Chen, Po-An Natl Chiao Tung Univ Inst Informat Management Hsinchu Taiwan

When playing certain specific classes of no-regret algorithms such as multiplicative updates and replicator dynamics in atomic congestion games, some previous convergence analyses were done with the standard Rosenthal potential function in terms of mixed strategy profiles (i.e., probability distributions on atomic flows), which could be non-convex. In several other works, the convergence, when playing the mirror-descent algorithm (a more general family of no-regret algorithms including multiplicative updates, gradient descents, etc.), was guaranteed with a convex potential function in terms of nonatomic flows as an approximation of the Rosenthal one. The convexity of the potential function provides convenience for analysis. One may wonder if the convergence of mirror descents can still be guaranteed directly with the non-convex Rosenthal potential function. In this paper, we answer the question affirmatively for discrete-time generalized mirror descents with the smoothness property (similarly adopted in many previous works for congestion games and markets) and for continuous-time generalized mirror descents with the separability of regularization functions. (C) 2017 Elsevier B.V. All rights reserved.

关键词： analysis of algorithms Mirror descents Congestion games Non-convex Convergence

来源：评论

学校读者我要写书评

暂无评论

Non-depth-first search against independent distributions on an AND-OR tree

引用

INFORMATION PROCESSING LETTERS 2018年 139卷 13-17页

作者： Suzuki, Toshio Tokyo Metropolitan Univ Dept Math Sci Hachioji Tokyo 1920397 Japan

Suzuki and Niida (2015) showed the following results on independent distributions (IDs) on an AND-OR tree, where they took only depth-first algorithms into consideration. (1) Suppose that a positive real number r < 1 is given, and let I(r) denote the class of all !Ds such that the probability of the root having value 0 is r;if, among members of I(r), d is a maximizer of cost of the best algorithm then d is an independent and identical distribution (IID). (2) The same as above holds for the set of all IDs in place of I(r). In the case where non-depth-first algorithms are taken into consideration, the counterparts of (1) and (2) are left open in the above work. Peng et al. (2017) extended (1) and (2) to multi-branching trees, where in (2) they put an additional hypothesis on ID d that the probability of the root having value 0 is neither 0 nor I. We give positive answers for the two questions of Suzuki-Niida. A key to the proof is that if ID d achieves the equilibrium among IDs then d has an optimal algorithm that is depth-first. In addition, we extend theorem 3 of Peng et al. to the case where non-depth-first algorithms are taken into consideration. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Non-depth-first algorithm Independent distribution Multi-branching tree Computational complexity analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximate survey propagation for statistical inference

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2019年第2期2019卷 023401-023401页

作者： Antenucci, Fabrizio Krzakala, Florent Urbani, Pierfrancesco Zdeborova, Lenka Univ Paris Saclay CNRS CEA Inst Phys Theor F-91191 Gif Sur Yvette France CNR NANOTEC Inst Nanotechnol Rome Unit Soft & Living Matter Lab Piazzale Aldo Moro 5 I-00185 Rome Italy CNRS Lab Phys Stat Paris France Sorbonnes Univ Paris France PSL Univ Ecole Normale Suprieure Paris France

Approximate message passing algorithm enjoyed considerable attention in the last decade. In this paper we introduce a variant of the AMP algorithm that takes into account glassy nature of the system under consideration. We coin this algorithm as the approximate survey propagation (ASP) and derive it for a class of low-rank matrix estimation problems. We derive the state evolution for the ASP algorithm and prove that it reproduces the one-step replica symmetry breaking (1RSB) fixed-point equations, well-known in physics of disordered systems. Our derivation thus gives a concrete algorithmic meaning to the 1RSB equations that is of independent interest. We characterize the performance of ASP in terms of convergence and mean-squared error as a function of the free Parisi parameter s. We conclude that when there is a model mismatch between the true generative model and the inference model, the performance of AMP rapidly degrades both in terms of MSE and of convergence, while for well-chosen values of the Parisi parameter s ASP converges in a larger regime and can reach lower errors. Among other results, our analysis leads us to a striking hypothesis that whenever s (or other parameters) can be set in such a way that the Nishimori condition M = Q > 0 is restored, then the corresponding algorithm is able to reach mean-squared error as low as the Bayes-optimal error obtained when the model and its parameters are known and exactly matched in the inference procedure. The remaining drawback is that we have not found a procedure that would systematically find a value of s leading to such low errors, this is a challenging problem let for future work.

关键词： message-passing algorithms statistical inference analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Financial portfolios based on Tsallis relative entropy as the risk measure

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2019年第9期2019卷 093207-093207页

作者： Devi, Sandhya 509 6th Ave S Edmonds WA 98020 USA Shell Int Explorat & Prod Co The Hague Netherlands

Earlier studies have shown that stock market distributions can be well described by distributions derived from Tsallis entropy, which is a generalization of Shannon entropy to non-extensive systems. In this paper, Tsallis relative entropy (TRE), which is the generalization of Kullback-Leibler relative entropy (KLRE) to non-extensive systems, is investigated as a possible risk measure in constructing risk optimal portfolios whose returns beat market returns. Portfolios are constructed by binning the risk values and allocating the stocks to bins according to their risk values. The average return in excess of market returns for each bin is calculated to get the risk-return patterns of the portfolios. The results are compared with those from three other risk measures: (1) the commonly used 'beta' of the capital asset pricing model (CAPM), (2) KLRE, and (3) the ratio of standard deviations. Tests carried out for both long (similar to 18 years) and shorter terms (similar to 9 years), which include the dot-com bubble and the 2008 crash periods, show that a linear fit can be obtained for the risk-excess return profiles of all four risk measures. However, in all cases, the profiles from TRE show a more consistent behavior in terms of both goodness of fit and the variation of returns with risk, than the other three risk measures.

关键词： analysis of algorithms models of financial markets quantitative finance risk measure and management

来源：评论

学校读者我要写书评

暂无评论

Machine learning for email spam filtering: review, approaches and open research problems

引用

HELIYON 2019年第6期5卷 e01802页

作者： Dada, Emmanuel Gbenga Bassi, Joseph Stephen Chiroma, Haruna Abdulhamid, Shafi'i Muhammad Adetunmbi, Adebayo Olusola Ajibuwa, Opeyemi Emmanuel Univ Maiduguri Dept Comp Engn Maiduguri Nigeria Fed Coll Educ Tech Dept Comp Sci Gombe Nigeria Fed Univ Technol Minna Dept Cyber Secur Sci Minna Nigeria Fed Univ Technol Akure Dept Comp Sci Akure Nigeria Univ Ilorin Dept Elect Engn Ilorin Nigeria

The upsurge in the volume of unwanted emails called spam has created an intense need for the development of more dependable and robust antispam fillers. Machine learning methods of recent are being used to successfully detect and filter spam emails. We present a systematic review of some of the popular machine learning based email spam filtering approaches. Our review covers survey of the important concepts, attempts, efficiency, and the research trend in spam filtering. The preliminary discussion in the study background examines the applications of machine learning techniques to the email spam filtering process of the leading internet service providers (ISPs) like Gmail, Yahoo and Outlook emails spam fillers. Discussion on general email spam filtering process, and the various efforts by different researchers in combating spam through the use machine learning techniques was done. Our review compares the strengths and drawbacks of existing machine learning approaches and the open research problems in spam filtering. We recommended deep leaning and deep adversarial learning as the future techniques that can effectively handle the menace of spam emails.

关键词： Computer science Computer security Computer privacy analysis of algorithms Machine learning Spam filtering Deep learning Neural networks Support vector machines Naive Bayes

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：