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

15th International Conference of the Metaheuristics International Conference (MIC)

作者： Chacpn Sartori, Camilo Blunt, Christian Artificial Intelligence Res Inst IIIA CSIC Campus UAB Bellaterra 08193 Spain

ISBN: (纸本)9783031629211;9783031629228

In the realm of optimization, where intricate landscapes conceal possibly hidden pathways to high-quality solutions, STNWeb serves as a beacon of clarity. This novel web-based visualization platform empowers researchers to delve into the intricate interplay between algorithms and optimization problems, uncovering the factors that influence algorithm performance across diverse problem domains, be they discrete/combinatorial or continuous. By leveraging the inherent power of visual data representation, STNWeb transcends traditional analytical methods, providing a robust foundation for dissecting algorithm behavior and pinpointing the mechanisms that elevate one algorithm above another. This visually-driven approach fosters a deeper understanding of algorithmic strengths and weaknesses, ultimately strengthening the discourse surrounding algorithm selection and refinement for complex optimization tasks.

关键词： Optimization Visualization Web Application analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Alternative Measures for the analysis of Online algorithms

Alternative Measures for the Analysis of Online Algorithms

引用

作者： Dorrigiv, Reza University of Waterloo

学位级别：master

In this thesis we introduce and evaluate several new models for the analysis of online algorithms. In an online problem, the algorithm does not know the entire input from the beginning; the input is revealed in a sequence of steps. At each step the algorithm should make its decisions based on the past and without any knowledge about the future. Many important real-life problems such as paging and routing are intrinsically online and thus the design and analysis ofonline algorithms is one of the main research areas in theoretical computer *** analysis is the standard measure for analysis of online algorithms. It has been applied to many online problems in diverse areas ranging from robot navigation, to network routing, to scheduling, to online graph coloring. While in several instances competitive analysis gives satisfactory results, for certain problems it results in unrealistically pessimistic ratios and/orfails to distinguish between algorithms that have vastly differing performance under any practical characterization. Addressing these shortcomings has been the subject of intense research by many of the best minds in the field. In this thesis, building upon recent advances of others we introduce some new models for analysis of online algorithms, namely Bijective analysis, Average analysis,Parameterized analysis, and Relative Interval analysis. We show that they lead to good results when applied to paging and list update algorithms. Paging and list update are two well known online problems. Paging is one of the main examples of poor behavior of competitive analysis. We show that LRU is the unique optimal online paging algorithm according to Average analysis on sequences with locality of reference. Recall that in practice input sequences for paging havehigh locality of reference. It has been empirically long established that LRU is the best paging algorithm. Yet, Average analysis is the first model that gives strict separation of LRU from all other

关键词： analysis of algorithms Online algorithms Paging List Update Adaptive analysis Data Compression

来源：评论

学校读者我要写书评

暂无评论

Comparison and analysis of some algorithms for implementing priority queues

Comparison and analysis of some algorithms for implementing ...

引用

作者： Goksel, Alinur Naval Postgraduate School

学位级别：硕士

A priority queue is a data structure for maintaining a collection of items, each having an associated key, such that the item with the largest key is easily accessible. Priority queues are implemented by using heap, k-ary tree, single linked-list, leftist tree, linked tree, AVL tree, 2-3 tree and fixed priority property. Required storage for each method was obtained and the worst case time analysis was done in terms of key comparisons and key exchanges during the insertion and deletion process. Finally, each of these methods were run on PDP-11 UNIX TIME SHARING SYSTEM at NPS using different random number generators to get the average CPU time for insertion and deletion process.

关键词： Priority queue analysis of algorithms Worst Case analysis Heap K-ary tree Single Linked-list Leftist tree Linked tree AVL-tree 2-3 tree Fixed Priority

来源：评论

学校读者我要写书评

暂无评论

Ranking and pricing under a cascade model of consumer review browsing

引用

IISE TRANSACTIONS 2025年第1期57卷 16-29页

作者： Zhao, Jingtong Pan, Xin Truong, Van-Anh Song, Jie Renmin Univ China Sch Econ Beijing Peoples R China SF Express Shenzhen Peoples R China Columbia Univ Dept Ind Engn & Operat Res New York NY USA Peking Univ Dept Ind Engn & Management Beijing Peoples R China

In online platforms, the reviews posted by existing consumers are playing an increasingly important role in the purchasing decisions of potential consumers. Motivated by this observation, we study the problems faced by a platform selling a single product with no capacity constraint, where the demand is explicitly influenced by the reviews presented to the consumers. More precisely, we model a consumer's browsing of reviews for a single product as following a cascade click model, with each consumer seeing some initial number of reviews and forming a utility estimate for the product based on the reviews the consumer has read. In the first part of the paper, we consider how to rank the reviews to induce short- and long-term revenue-maximizing purchasing behaviors. In the second part, we study how to set the price of the product. We derive structural insights and bounds on both problems. We also consider the case that the parameters of the model are unknown, where we propose algorithms that learn the parameters and optimize the ranking of the reviews or the price online. We show that our algorithms have regrets O(T23).

关键词： analysis of algorithms approximations/heuristics revenue management

来源：评论

学校读者我要写书评

暂无评论

Busy-Time Scheduling on Heterogeneous Machines: algorithms and analysis

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2022年第12期33卷 3942-3958页

作者： Liu, Mozhengfu Tang, Xueyan Nanyang Technol Univ Sch Comp Sci & Engn Singapore 639798 Singapore

We study a generalized busy-time scheduling model on heterogeneous machines. The input to the model includes a set of jobs and a set of machine types. Each job has a size and a time interval during which it should be processed. Each job is to be placed on a machine for execution. Different types of machines have distinct capacities and cost rates. The total size of the jobs running on a machine must always be kept within the machine's capacity, giving rise to placement restrictions for jobs of various sizes among the machine types. Each machine used is charged according to the time duration in which it is busy, i.e., it is processing jobs. The objective is to schedule the jobs into machines to minimize the total cost of all the machines used. We develop an O(1)-approximation algorithm in the offline setting and an O(mu)-competitive algorithm in the online setting (where mu is the max/min job length ratio), both of which are asymptotically optimal. This article significantly improves the analysis of the algorithms over our preliminary work.

关键词： Busy time scheduling analysis of algorithms approximation ratio competitive ratio

来源：评论

学校读者我要写书评

暂无评论

PROBABILISTIC analysis OF DISJOINT SET UNION algorithms

引用

SIAM JOURNAL ON COMPUTING 1993年第5期22卷 1053-1074页

作者： BOLLOBAS, B SIMON, I LOUISIANA STATE UNIV DEPT MATH BATON ROUGE LA 70803 USA CALIF STATE UNIV HAYWARD DEPT MATH & COMP SCI HAYWARD CA 94542 USA

A number of open questions are settled about the expected costs of two disjoint set Union and Find algorithms raised by Knuth and Schonhage [Theoret. Comput. Sci., 6 (1978), pp. 281-3151. This paper shows that the expected time of the Weighted Quick-Find (QFW) algorithm to perform (n - 1) randomly chosen unions is cn + o (n / log n), where c = 2.0847 .... Through an observation of Tarjan and Van Leeuwen in V. Assoc. Comput. Mach., 22 (1975), pp. 215-2251 this implies linear time bounds to perform 0(n) unions and finds for a class of other union-find algorithms. It is also proved that the expected time of the Unweighted Quick-Find (QF) algorithm is n2/8 + O(n(log n)2). The expected costs of QFW and QF are analyzed when fewer than (n - 1) unions are performed. Among other results, for QFW it is shown that the expected cost of m = o(n) randomly chosen unions is m(1 + o(1)). If m = alphan/2, where alpha less-than-or-equal-to e-2, this cost is m(1 + epsilon(alpha) + o(1)), where epsilon(alpha) --> 0 as a --> 0 and epsilon(e-2) less-than-or-equal-to .026. For QF, the expected cost of n/2 - n2/3(log n)2/3 randomly chosen unions is 0(n log n).

关键词： PROBABILISTIC METHOD RANDOM GRAPHS analysis of algorithms EXPECTED TIME BOUNDS UNION-FIND PROBLEM EQUIVALENCE algorithms DISJOINT SET UNION QUICK-FIND algorithms

来源：评论

学校读者我要写书评

暂无评论

Asynchronous analysis of parallel dynamic programming algorithms

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1996年第4期7卷 425-438页

作者： Lewandowski, G Condon, A Bach, E UNIV WISCONSIN MADISON WI 53706 USA

We examine a very simple asynchronous model of parallel computation that assumes the time to compute a task is random, following some probability distribution. The goal of this model is to capture the effects of unpredictable delays on processors, due to communication delays or cache misses, for example. Using techniques from queueing theory and occupancy problems, we use this model to analyze two parallel dynamic programming algorithms. We show that this model is simple to analyze and correctly predicts which algorithm will perform better in practice. The algorithms we consider are a pipeline algorithm, where each processor i computes in order the entries of rows i, i + p, and so on, where p is the number of processors;and a diagonal algorithm, where entries along each diagonal extending from the left to the top of the table are computed in turn. It is likely that the techniques used here can be useful in the analysis of other algorithms that use barriers or pipelining techniques.

关键词： parallel dynamic programming asynchronous algorithms parallel models of computation queueing theory analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Competitive analysis of randomized paging algorithms

引用

THEORETICAL COMPUTER SCIENCE 2000年第1-2期234卷 203-218页

作者： Achlioptas, D Chrobak, M Noga, J Univ Calif Riverside Dept Math Riverside CA 92521 USA Univ Toronto Dept Comp Sci Toronto ON M5S 3G4 Canada Univ Calif Riverside Dept Comp Sci Riverside CA 92521 USA

The paging problem is defined as follows: we are given a two-level memory system, in which one level is a fast memory, called cache, capable of holding k items, and the second level is an unbounded but slow memory. At each given time step, a request to an item is issued. Given a request to an item p, a miss occurs if p is not present in the fast memory. In response to a miss, we need to choose an item q in the cache and replace it by p. The choice of q needs to be made on-line, without the knowledge of future requests. The objective is to design a replacement strategy with a small number of misses. In this paper we use competitive analysis to study the performance of randomized on-line paging algorithms. Our goal is to show how the concept of work functions, used previously mostly for the analysis of deterministic algorithms, can also be applied, in a systematic fashion, to the randomized case. We present two results: we first show that the: competitive ratio of the marking algorithm is exactly 2H(k) - 1. Previously, it was known to be between H-k and 2(Hk). Then we provide a new, H-k-competitive algorithm for paging. Our algorithm, as well as its analysis, is simpler than the known algorithm by McGeoch and Sleator. Another advantage of our algorithm is that it can be implemented with complexity bounds independent of the number of past requests: O(k(2) log k) memory and O(k(2)) time per request. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： on-line algorithms analysis of algorithms competitive analysis paging randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

CONTINUOUS MODELS THAT ARE EQUIVALENT TO RANDOMNESS FOR THE analysis OF MANY SORTING algorithms

引用

COMPUTING 1983年第1期31卷 11-31页

作者： DOBERKAT, EE Department of Mathematics and Computer Science Clarkson College of Technology Potsdam USA

It is shown that a large class of continuous models for the average case analysis of many sorting algorithms (including quicksort, Shell's sort, heapsort insertion sort) will display the same expected behavior with respect to interchanges and comparisons. This is done by comparing these models with the discrete model in which every permutation has the same probability. Applications to priority queues and to straight insertion sort are given.

关键词： AMS Subject Classifications: 68E05, 68C25 analysis of algorithms sorting

来源：评论

学校读者我要写书评

暂无评论

analysis OF GRID FILE algorithms

引用

BIT 1985年第2期25卷 335-357页

作者： REGNIER, M INST NATL RECH INFORMAT & AUTOMAT F-78153 LE CHESNAYFRANCE

Grid file algorithms were suggested in [12] to provide multi-key access to records in a dynamically growing file. We specify here two algorithms and derive the average sizes of the corresponding directories. We provide an asymptotic analysis. The growth of the indexes appears to be non-linear for uniform distributions:O(v ^c) orO(v ^ξ), wherec=1+b^?1, ξ=1+(s-1)/(sb+1),s is the number of attributes being used,v the file size, andb the page capacity of the system. Finally we give corresponding results for biased distributions and compare transient phases.

关键词： dynamic data structures multi-key access data bases hashing grid file analysis of algorithms asymptotic analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：