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

8th International Symposium on Combinatorial Optimization (ISCO)

作者： Antoniadis, Antonios Broersma, Hajo Meng, Yang Univ Twente Fac Elect Engn Math & Comp Sci POB 217 NL-7500 AE Enschede Netherlands

ISBN: (纸本)9783031609237;9783031609244

We introduce learning augmented algorithms to the online graph coloring problem. Although the simple greedy algorithm FirstFit is known to perform poorly in the worst case, we are able to establish a relationship between the structure of any input graph G that is revealed online and the number of colors that FirstFit uses for G. Based on this relationship, we propose an online coloring algorithm FirstFitPredictions that extends FirstFit while making use of machine learned predictions. We show that FirstFitPredictions is both consistent and smooth. Moreover, we develop a novel framework for combining online algorithms at runtime specifically for the online graph coloring problem. Finally, we show how this framework can be used to robustify FirstFitPredictions by combining it with any classical online coloring algorithm (that disregards the predictions).

关键词： learning augmented algorithms online algorithms online graph coloring first fit

来源：评论

学校读者我要写书评

暂无评论

online Matching with High Probability 17th

Online Matching with High Probability

引用

17th International Symposium on Algorithmic Game Theory (SAGT)

作者： Mihail, Milena Trobst, Thorben Univ Calif Irvine Dept Comp Sci Irvine CA 92717 USA

ISBN: (纸本)9783031710322;9783031710339

We study the classical, randomized RANKING algorithm, which is known to be (1 - 1/epsilon)-competitive in expectation for the online Bipartite Matching Problem. We give a tail inequality bound (Theorem 1), namely that RANKING is (1 - 1/epsilon - alpha)-competitive with probability at least 1 - e(-2 alpha 2n) where n is the size of the maximum matching in the instance. Building on this, we show similar concentration results for several generalizations of the online Bipartite Matching Problem, including the Fully online Matching Problem and the online Vertex-Weighted Bipartite Matching Problem.

关键词： online algorithms Concentration of Measure online Matching Randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A Subquadratic Bound for online Bisection 41

A Subquadratic Bound for Online Bisection

引用

41st International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Bienkowski, Marcin Schmid, Stefan Univ Wroclaw Wroclaw Poland TU Berlin Berlin Germany Weizenbaum Inst Berlin Germany

ISBN: (纸本)9783959773119

The online bisection problem is a natural dynamic variant of the classic optimization problem, where one has to dynamically maintain a partition of n elements into two clusters of cardinality n/2. During runtime, an online algorithm is given a sequence of requests, each being a pair of elements: an inter-cluster request costs one unit while an intra-cluster one is free. The algorithm may change the partition, paying a unit cost for each element that changes its cluster. This natural problem admits a simple deterministic O(n(2))-competitive algorithm [Avin et al., DISC 2016]. While several significant improvements over this result have been obtained since the original work, all of them either limit the generality of the input or assume some form of resource augmentation (e.g., larger clusters). Moreover, the algorithm of Avin et al. achieves the best known competitive ratio even if randomization is allowed. In this paper, we present the first randomized online algorithm that breaks this natural quadratic barrier and achieves a competitive ratio of (O) over tilde (n(23/12)) without resource augmentation and for an arbitrary sequence of requests.

关键词： Bisection Graph Partitioning online balanced Repartitioning online algorithms competitive Analysis

来源：评论

学校读者我要写书评

暂无评论

Optimal online Discrepancy Minimization 2024

Optimal Online Discrepancy Minimization

引用

56th Annual ACM Symposium on Theory of Computing (STOC)

作者： Kulkarni, Janardhan Reis, Victor Rothvoss, Thomas Microsoft Res Redmond WA 98052 USA Inst Adv Study Princeton NJ USA Univ Washington Seattle WA USA

ISBN: (纸本)9798400703836

We prove that there exists an online algorithm that for any sequence of vectors v(1), ... v(T) is an element of R-n with parallel to v(i)parallel to(2) <= 1, arriving one at a time, decides random signs x, ..., x(T) is an element of {-1, 1}so that for every t <= T, the prefix sum Sigma(t)(i=1) x(i)v(i) is 10-subgaussian. This improves over the work of Alweiss, Liu and Sawhney who kept prefix sums O(root log (nT))-subgaussian, and gives a O(root log T) bound on the discrepancy max(t is an element of T) parallel to Sigma(t)(i=1) x(i)v(i)parallel to(infinity). Our proof combines a generalization of Banaszczyk's prefix balancing result to trees with a cloning argument to find distributions rather than single colorings. We also show a matching Omega(root log T) strategy for an oblivious adversary.

关键词： online algorithms discrepancy vector balancing edge orientation

来源：评论

学校读者我要写书评

暂无评论

algorithms for online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios

引用

OPERATIONS RESEARCH 2020年第6期68卷 1787-1803页

作者： Ma, Will Simchi-Levi, David Columbia Univ Grad Sch Business New York NY 10027 USA MIT Dept Civil & Environm Engn Inst Data Syst & Soc 77 Massachusetts Ave Cambridge MA 02139 USA MIT Operat Res Ctr 77 Massachusetts Ave Cambridge MA 02139 USA

Motivated by the dynamic assortment offerings and item pricings occurring in e-commerce, we study a general problem of allocating finite inventories to heterogeneous customers arriving sequentially. We analyze this problem under the framework of competitive analysis, where the sequence of customers is unknown and does not necessarily follow any pattern. Previous work in this area, studying online matching, advertising, and assortment problems, has focused on the case where each item can only be sold at a single price, resulting in algorithms which achieve the best-possible competitive ratio of 1-1/e. In this paper, we extend all of these results to allow for items havingmultiple feasible prices. Our algorithms achieve the best-possible weight-dependent competitive ratios, which depend on the sets of feasible prices given in advance. Our algorithms are also simple and intuitive;they are based on constructing a class of universal value functions that integrate the selection of items and prices offered. Finally, we test our algorithms on the publicly available hotel data set of Bodea et al. [Bodea T, Ferguson M, Garrow L (2009) Data set-Choice-based revenue management: Data from a major hotel chain. Manufacturing Service Oper. Management 11(2):356-361.], where there are multiple items (hotel rooms), each with multiple prices (fares at which the room could be sold). We find that applying our algorithms, as a hybrid with algorithms that attempt to forecast and learn the future transactions, results in the best performance.

关键词： online algorithms revenue management online matching Adwords

来源：评论

学校读者我要写书评

暂无评论

Breaking the Barrier of 2 for the Competitiveness of Longest Queue Drop

引用

ACM TRANSACTIONS ON algorithms 2024年第4期20卷 1-29页

作者： Antoniadis, Antonios Englert, Matthias Matsakis, Nicolaos Vesely, Pavel Univ Twente Enschede Netherlands Univ Warwick Coventry England Charles Univ Prague Comp Sci Inst Prague Czech Republic

We consider the problem of managing the buffer of a shared-memory switch that transmits packets of unit value. A shared-memory switch consists of an input port, a number of output ports, and a buffer with a specific capacity. In each time step, an arbitrary number of packets arrive at the input port, each packet designated for one output port. Each packet is added to the queue of the respective output port. If the total number of packets exceeds the capacity of the buffer, some packets have to be irrevocably evicted. At the end of each time step, each output port transmits a packet in its queue, and the goal is to maximize the number of transmitted packets. The Longest Queue Drop (LQD) online algorithm accepts any arriving packet to the buffer. However, if this results in the buffer exceeding its memory capacity, then LQD drops a packet from whichever queue is currently the longest, breaking ties arbitrarily. The LQD algorithm was first introduced in 1991, and has been known to be 2-competitive since 2001. Although LQD remains the best known online algorithm for the problem and is of practical interest, determining its true competitiveness is a long-standing open problem. We show that LQD is 1.6918-competitive, establishing the first (2 - P ) upper bound for the competitive ratio of LQD for a constant epsilon> 0 .

关键词： Buffer management online scheduling online algorithms longest queue drop

来源：评论

学校读者我要写书评

暂无评论

Multivehicle Perimeter Defense in Conical Environments

引用

IEEE TRANSACTIONS ON ROBOTICS 2024年 40卷 1439-1456页

作者： Bajaj, Shivam Bopardikar, Shaunak D. Torng, Eric Von Moll, Alexander Casbeer, David W. Michigan State Univ Dept Elect & Comp Engn E Lansing MI 48824 USA Purdue Univ Dept Elect & Comp Engn W Lafayette IN 47907 USA Michigan State Univ Dept Comp Sci & Engn E Lansing MI 48824 USA Air Force Res Lab Control Sci Ctr Dayton OH 45433 USA

In this article, we consider a perimeter defense problem in a planar conical environment in which M identical vehicles, each having a finite capture radius, seek to defend a concentric perimeter from mobile intruders. The intruders are released at the circumference of the environment at arbitrary times and in any number. Upon release, each intruder moves radially toward the perimeter with fixed speed. We provide a worst-case analysis of this problem. Specifically, we present a competitive analysis approach to this problem by measuring the performance of decentralized and cooperative online algorithms for the vehicles against arbitrary inputs, relative to an optimal offline algorithm that has information about entire intruder release sequence in advance. We first establish a necessary condition on the problem parameters that guarantees finite competitiveness of any algorithm. We then design and analyze three decentralized and two cooperative online algorithms and characterize parameter regimes in which they have finite competitive ratios. Specifically, our first two decentralized algorithms are provably 1 and 2-competitive, respectively, whereas our third decentralized algorithm exhibits different competitive ratios in different regimes of problem parameters. Our first cooperative algorithm is 1.5-competitive and our second cooperative algorithm exhibits different competitive ratios in different regimes of problem parameters. Finally, we provide multiple numerical plots in the parameter space to reveal additional insights into the relative performance of our algorithms and discuss an extension to the case of heterogeneous vehicles.

关键词： Games Task analysis Routing Contracts Wildlife Vehicle dynamics Surveillance Agent based systems cooperative agents online algorithms

来源：评论

学校读者我要写书评

暂无评论

Simple and Optimal online Contention Resolution Schemes for k-Uniform Matroids 15

Simple and Optimal Online Contention Resolution Schemes for ...

引用

15th Innovations in Theoretical Computer Science Conference (ITCS)

作者： Dinev, Atanas Weinberg, S. Matthew MIT 77 Massachusetts Ave Cambridge MA 02139 USA Princeton Univ Princeton NJ 08544 USA

ISBN: (纸本)9783959773096

We provide a simple (1 - O(1/root k))-selectable online Contention Resolution Scheme for k-uniform matroids against a fixed-order adversary. If A(i) and G(i) denote the set of selected elements and the set of realized active elements among the first i (respectively), our algorithm selects with probability 1- 1/root k any active element i such that |A(i-1)|+ 1 <= (1-1/root k) center dot E[|G(i)|]+ root k. This implies a (1- O(1/root k)) prophet inequality against fixed-order adversaries for k-uniform matroids that is considerably simpler than previous algorithms [2, 4, 18]. We also prove that no OCRS can be (1 - Omega(root log k/k))-selectable for k-uniform matroids against an almighty adversary. This guarantee is matched by the (known) simple greedy algorithm that selects every active element with probability 1 - Theta(root log k/k) [17].

关键词： online contention resolutions schemes prophet inequalities online algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

online Combinatorial Allocations and Auctions with Few Samples 65

Online Combinatorial Allocations and Auctions with Few Sampl...

引用

65th Symposium on Foundations of Computer Science

作者： Duffing, Paul Kesselheim, Thomas Lucier, Brendan Reiffenhauser, Rebecca Singla, Sahil Google Res Zurich Switzerland Univ Bonn Bonn Germany Microsoft Res New England Cambridge MA USA Univ Amsterdam Amsterdam Netherlands Georgia Tech Atlanta GA USA

ISBN: (纸本)9798331516758;9798331516741

In online combinatorial allocations/auctions, n bidders sequentially arrive, each with a combinatorial valuation (such as submodular/XOS) over subsets of m indivisible items. The aim is to immediately allocate a subset of the remaining items to maximize the total welfare, defined as the sum of bidder valuations. A long line of work has studied this problem when the bidder valuations come from known independent distributions. In particular, for submodular/XOS valuations, we know 2-competitive algorithms/mechanisms that set a fixed price for each item and the arriving bidders take their favorite subset of the remaining items given these prices. However, these algorithms traditionally presume the availability of the underlying distributions as part of the input to the algorithm. Contrary to this assumption, practical scenarios often require the learning of distributions, a task complicated by limited sample availability. This paper investigates the feasibility of achieving O(1)-competitive algorithms under the realistic constraint of having access to only a limited number of samples from the underlying bidder distributions. Our first main contribution shows that a mere single sample from each bidder distribution is sufficient to yield an O(1)competitive algorithm for submodular/XOS valuations. This result leverages a novel extension of the secretary-style analysis, employing the sample to have the algorithm compete against itself. Although online, this first approach does not provide an online truthful mechanism. Our second main contribution shows that a polynomial number of samples suffices to yield a (2+epsilon)-competitive online truthful mechanism for submodular/XOS valuations and any constant epsilon > 0. This result is based on a generalization of the median-based algorithm for the single-item prophet inequality problem to combinatorial settings with multiple items.

关键词： online algorithms prophet inequality posted-price mechanisms

来源：评论

学校读者我要写书评

暂无评论

Lyapunov-based real-time optimization method in microgrids: A comprehensive review

引用

RENEWABLE & SUSTAINABLE ENERGY REVIEWS 2025年 213卷

作者： Alilou, Masoud Shotorbani, Amin Mohammadpour Mohammadi-Ivatloo, Behnam Urmia Univ Technol Engn Fac Khoy Dept Elect Engn Orumiyeh Iran Univ British Columbia Sch Engn Kelowna BC Canada LUT Univ Sch Energy Syst Dept Elect Engn Lappeenranta Finland

An effective energy management system in a microgrid is of paramount importance, optimizing local energy utilization for diverse consumer needs. Prevalent strategies often rely on offline day-ahead or two-stage methods, assuming stable microgrid configurations or precise forecasts-a challenge in practical operations. A real-time energy management system approach struggles to achieve global optimal solutions, though inherently providing robustness against forecast uncertainties. A recent and promising approach is applying the Lyapunov optimization method, known for online optimization, to address challenges in real-time microgrid energy management systems. This paper provides a comprehensive exploration of Lyapunov-based real-time energy management systems in microgrids. We begin by elucidating the integration of the Lyapunov method into microgrid energy management. Categorizing pertinent research papers systematically, we differentiate parameters such as microgrid components with respect to real-time energy management systems, objective functions, and designs of the Lyapunov algorithm, covering establishment of virtual queues, drift-plus-penalty, and the control parameter roles of the algorithm. Integral to our investigation is a thorough assessment of the efficacy of the Lyapunov method in real-time microgrid energy management. The analysis highlights the efficacy of Lyapunov optimization in microgrid energy management system operation and underscores it as a solution to realtime energy management system challenges in microgrids, establishing its merits and applicability in scholarly and practical contexts.

关键词： Energy management Microgrid online algorithms Real-time Lyapunov optimization Virtual queue

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：