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

Quantum online Streaming algorithms with Logarithmic Memory

INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS 2021年第2期60卷 608-616页

作者： Khadiev, Kamil Khadieva, Aliya Smart Quantum Technol Ltd Kazan Russia Kazan Fed Univ Kazan Russia Univ Latvia Fac Comp Riga Latvia

We consider quantum and classical (deterministic or randomize) streaming online algorithms with respect to competitive ratio. We show that there is a problem that can be solved by a quantum online streaming algorithm better than by classical ones in the case of logarithmic memory. The problem is an online version of the Disjointness problem (Checking weather two sets are disjoint or not).

关键词： Quantum computation online algorithms Logarithmic space Streaming algorithms online minimization problems OBDD Computational complexity

来源：评论

学校读者我要写书评

暂无评论

A LOWER-BOUND FOR RANDOMIZED online SCHEDULING algorithms

引用

INFORMATION PROCESSING LETTERS 1994年第5期51卷 219-222页

作者： CHEN, B VANVLIET, A WOEGINGER, GJ GRAZ TECH UNIV INST MATHA-8010 GRAZAUSTRIA ERASMUS UNIV ROTTERDAM INST ECONOMETR3000 DR ROTTERDAMNETHERLANDS

We prove that any randomize dalgorithm for on-line scheduling jobs on m identical parallel machines must have a worst case ration at least m(m)/m(m)-(m-1)(m)) for every m, which tends to e/(e-1) approximate to 1.58 as... 详细信息

关键词： COMBINATORIAL PROBLEMS online algorithms WORST CASE BOUNDS SCHEDULING RANDOMIZATION

来源：评论

学校读者我要写书评

暂无评论

Markovian online Matching algorithms on Large Bipartite Random Graphs

引用

METHODOLOGY AND COMPUTING IN APPLIED PROBABILITY 2022年第4期24卷 3195-3225页

作者： Aoudi, Mohamed Habib Aliou Diallo Moyal, Pascal Robin, Vincent Univ Technol Compiegne Alliance Sorbonne Univ LMAC Compiegne France Univ Lorraine IECL Nancy France INRIA PASTA Nancy France

In this paper, we present an approximation of the matching coverage on large bipartite graphs, for local online matching algorithms based on the sole knowledge of the remaining degree of the nodes of the graph at hand. This approximation is obtained by applying the Differential Equation Method to a measure-valued process representing an alternative construction, in which the matching and the graph are constructed simultaneously, by a uniform pairing leading to a realization of the bipartite Configuration Model. The latter auxiliary construction is shown to be equivalent in distribution to the original one. It allows to drastically reduce the complexity of the problem, in that the resulting matching coverage can be written as a simple function of the final value of the process, and in turn, approximated by a simple function of the solution of a system of ODE's. By way of simulations, we illustrate the accuracy of our estimate, and then compare the performance of an algorithm based on the minimal residual degree of the nodes, to the classical greedy matching.

关键词： Random graphs Matching online algorithms Stochastic processes

来源：评论

学校读者我要写书评

暂无评论

online competitive algorithms for maximizing weighted throughput of unit jobs

引用

JOURNAL OF DISCRETE algorithms 2006年第2期4卷 255-276页

作者： Chin, Francis Y. L. Chrobak, Marek Fung, Stanley P. Y. Jawor, Wojciech Sgall, Jiri Tichy, Tomas Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Univ Calif Riverside Dept Comp Sci Riverside CA 92521 USA AS CR Math Inst Zitna 25 Prague 115671 Czech Republic

We study an online unit-job scheduling problem arising in buffer management. Each job is specified by its release time, deadline, and a nonnegative weight. Due to overloading conditions, some jobs have to be dropped. The goal is to maximize the total weight of scheduled jobs. We present several competitive online algorithms for various versions of unit-job scheduling, as well as some lower bounds on the competitive ratios. We first give a randomized algorithm RMIX with competitive ratio of e/(e - 1) approximate to 1.582. This is the first algorithm for this problem with competitive ratio smaller than 2. Then we consider s-bounded instances, where the span of each job ( deadline minus release time) is at most s. We give a 1.25-competitive randomized algorithm for 2-bounded instances, matching the known lower bound. We also give a deterministic algorithm EDF alpha, whose competitive ratio on s-bounded instances is 2 - 2/s + o(1/s). For 3-bounded instances its ratio is phi approximate to 1.618, matching the known lower bound. In s-uniform instances, the span of each job is exactly s. We show that no randomized algorithm can be better than 1.25-competitive on s-uniform instances, if the span s is unbounded. For s = 2, our proof gives a lower bound of 4 - 2 root 2 approximate to 1.172. Also, in the 2-uniform case, we prove a lower bound of root 2 approximate to 1.414 for deterministic memoryless algorithms, matching a known upper bound. Finally, we investigate the multiprocessor case and give a 1/(1-(m m+1) (m))- competitive algorithm for m processors. We also show improved lower bounds for the general and s-uniform cases. (C) 2005 Elsevier B.V. All rights reserved.

关键词： Scheduling online algorithms Buffer management

来源：评论

学校读者我要写书评

暂无评论

online Deterministic algorithms for Connected Dominating Set & Set Cover Leasing Problems 9th

Online Deterministic Algorithms for Connected Dominating Set...

引用

9th International Conference on Operations Research and Enterprise Systems (ICORES)

作者： Markarian, Christine Kassar, Abdul-Nasser Haigazian Univ Dept Math Sci Beirut Lebanon Lebanese Amer Univ Dept Informat Technol & Operat Management Beirut Lebanon

ISBN: (纸本)9789897583964

Connected Dominating Set (CDS) and Set Cover (SC) are classical optimization problems that have been widely studied in both theory and practice, as many variants and in different settings, motivated by applications in wireless and social networks. In this paper, we consider the online setting, in which the input sequence arrives in portions over time and the so-called online algorithm needs to react to each portion. online algorithms are measured using the notion of competitive analysis. An online algorithm A is said to have competitive ratio r, where r is the worst-case ratio, over all possible instances of a given minimization problem, of the solution constructed by A to the solution constructed by an offline optimal algorithm that knows the entire input sequence in advance. online Connected Dominating Set (OCDS) (Hamann et al., 2018) is an online variant of CDS that is currently solved by a randomized online algorithm with optimal competitive ratio. We present in this paper the first deterministic online algorithm for OCDS, with optimal competitive ratio. We further introduce generalizations of OCDS, in the leasing model (Meyerson, 2005) and in the multiple hop model (Coelho et al., 2017), and design deterministic online algorithms for each of these generalizations. We also propose the first deterministic online algorithm for the leasing variant of SC (Abshoff et al., 2016), that is currently solved by a randomized online algorithm.

关键词： Connected Dominating Sets Set Cover Leasing online algorithms Competitive Analysis

来源：评论

学校读者我要写书评

暂无评论

online and Dynamic algorithms for Set Cover 2017

Online and Dynamic Algorithms for Set Cover

引用

49th Annual ACM-SIGACT Symposium on Theory of Computing (STOC)

作者： Gupta, Anupam Krishnaswamy, Ravishankar Kumar, Amit Panigrahi, Debmalya Carnegie Mellon Univ Pittsburgh PA 15213 USA Microsoft Res Bengaluru India IIT Delhi New Delhi India Duke Univ Durham NC 27706 USA

ISBN: (纸本)9781450345286

In this paper, we give new results for the set cover problem in the fully dynamic model. In this model, the set of "active" elements to be covered changes over time. The goal is to maintain a near-optimal solution for the currently active elements, while making few changes in each timestep. This model is popular in both dynamic and online algorithms: in the former, the goal is to minimize the update time of the solution, while in the latter, the recourse (number of changes) is bounded. We present generic techniques for the dynamic set cover problem inspired by the classic greedy and primal-dual offine algorithms for set cover. The former leads to a competitive ratio of O(log n(t)), where n(t) is the number of currently active elements at timestep t, while the latter yields competitive ratios dependent on f(t), the maximum number of sets that a currently active element belongs to. We demonstrate that these techniques are useful for obtaining tight results in both settings: update time bounds and limited recourse, exhibiting algorithmic techniques common to these two parallel threads of research.

关键词： Set cover recourse dynamic algorithms competitive ratio online algorithms vertex cover graph matching hypergraph matching

来源：评论

学校读者我要写书评

暂无评论

An experimental study of online scheduling algorithms

引用

ACM Journal of Experimental Algorithmics 2002年 7卷 3-3页

作者： Albers, Susanne Schröder, Bianca Institut für Informatik Albert-Ludwigs-Universität Georges-Köhler-Allee 79 Freiburg 79110 Germany Computer Science Department Carnegie Mellon University 5000 Forbes Avenue Pittsburgh 15213 PA United States

We present the first comprehensive experimental study of online algorithms for Graham's scheduling problem. Graham's scheduling problem is a fundamental problem in scheduling theory where a sequence of jobs has to be scheduled on m identical parallel machines so as to minimize the makespan. Graham gave an elegant algorithm that is (2-1/m)-competitive. Recently a number of new online algorithms were developed that achieve competitive ratios around 1.9. Since competitive analysis can only capture the worst case behavior of an algorithm a question often asked is: Are these new algorithms geared only towards a pathological case or do they perform better in practice, too? We address this question by analyzing the algorithms on various job sequences. In our actual tests, we analyzed the algorithms (1) on real world jobs and (2) on jobs generated by probability distributions. It turns out that the performance of the algorithms depends heavily on the characteristics of the respective work load. On job sequences that are generated by standard probability distributions, Graham's strategy is clearly the best. However, on the real world jobs the new algorithms often outperform Graham's strategy. Our experimental study confirms theoretical results in the sense that there are also job sequences in practice on which the new online algorithms perform better. Our study can help to inform practitioners about the new scheduling strategies as an alternative to Graham's algorithm. © 2002, Association for Computing Machinery. All rights reserved.

关键词： algorithms Experimentation G.4 [mathematical software]: algorithm design and analysis online algorithms Performance Scheduling

来源：评论

学校读者我要写书评

暂无评论

Optimal algorithms for online b-Matching with Variable Vertex Capacities

引用

ALGORITHMICA 2025年第2期87卷 167-190页

作者： Albers, Susanne Schubert, Sebastian Tech Univ Munich Dept Comp Sci Garching Germany

We study the b-matching problem, which generalizes classical online matching introduced by Karp, Vazirani and Vazirani (STOC 1990). Consider a bipartite graph G=(S boolean OR R-center dot,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(S\dot{\cup }R,E)$$\end{document}. Every vertex s is an element of S\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s\in S$$\end{document} is a server with a capacity bs\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b_s$$\end{document}, indicating the number of possible matching partners. The vertices r is an element of R\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r\in R$$\end{document} are requests that arrive online and must be matched immediately to an eligible server. The goal is to maximize the cardinality of the constructed matching. In contrast to earlier work, we study the general setting where servers may have arbitrary, individual capacities. We prove that the most natural and simple online algorithms achieve optimal competitive ratios. As for deterministic algorithms, we give a greedy algorithm RelativeBalance and analyze it by extending the primal-dual framework of Devanur, Jain and Kleinberg (SODA 2013). In the area of randomized algorithms we study the celebrated Ranking algorithm by Karp, Vazirani

关键词： online algorithms Primal-dual analysis Configuration LP b-matching variable vertex capacities unweighted matching vertex-weighted matching

来源：评论

学校读者我要写书评

暂无评论

online Matching Frameworks Under Stochastic Rewards, Product Ranking, and Unknown Patience

引用

OPERATIONS RESEARCH 2025年第2期73卷 iii-viii, 583-1150, C2-C3页

作者： Brubach, Brian Grammel, Nathaniel Ma, Will Srinivasan, Aravind Wellesley Coll Comp Sci Dept Wellesley MA 02481 USA Univ Maryland Dept Comp Sci College Pk MD 20742 USA Columbia Univ Grad Sch Business New York NY 10027 USA Columbia Univ Data Sci Inst New York NY 10027 USA

We study generalizations of online bipartite matching in which each arriving vertex (customer) views a ranked list of offline vertices (products) and matches to (purchases) the first one they deem acceptable. The number of products that the customer has patience to view can be stochastic and dependent on the products seen. We develop a framework that views the interaction with each customer as an abstract resource consumption process and derive new results for these online matching problems under the adversarial, nonstationary, and independent and identically-distributed arrival models, assuming we can (approximately) solve the product ranking problem for each single customer. To that end, we show new results for product ranking under two cascade-click models: an optimal algorithm when each item has its own hazard rate for making the customer depart and a 1/2-approximate algorithm when the customer has a general item-independent patience distribution. We also present a constant-factor 0.027-approximate algorithm in a new model where items are not initially available and arrive over time. We complement these positive results by presenting three additional negative results relating to these problems.

关键词： online algorithms competitive ratio online matching product ranking

来源：评论

学校读者我要写书评

暂无评论

online bipartite matching in the probe-commit model

引用

MATHEMATICAL PROGRAMMING 2025年 1-54页

作者： Borodin, Allan Macrury, Calum Univ Toronto Dept Comp Sci Toronto ON Canada Columbia Univ Grad Sch Business New York NY 10027 USA

We consider the classical online bipartite matching problem in the probe-commit model. In this problem, when an online vertex arrives, its edges must be probed to determine if they exist, based on known edge probabilities. A probing algorithm must respect commitment, meaning that if a probed edge exists, it must be used in the matching. Additionally, each online vertex has a patience constraint which limits the number of probes that can be made to its adjacent edges. We introduce a new configuration linear program and use it to establish the following competitive ratios which depend on the model used to generate the instance graph, and the arrival order of its online vertices:In the worst-case instance model, an optimal 1/ ratio when the vertices arrive in uniformly at random (u.a.r.) *** the known independently distributed (i.d.) instance model, an optimal 1/2 ratio when the vertices arrive in adversarial order, and a 1-1/e\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1-1/e$$\end{document} ratio when the vertices arrive in u.a.r. order. The latter two results improve upon the previous best competitive ratio of 0.46 due to Brubach et al. (Algorithmica 2020). Our 1-1/e\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1-1/e$$\end{document}-competitive algorithm matches the best known result for the prophet secretary matching problem due to Ehsani et al. (SODA 2018). Our algorithm is efficient and implies a 1-1/e\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidem

关键词： Stochastic probing online algorithms Bipartite matching Optimization under uncertainty

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：