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

Assortment Planning for Recommendations at Checkout Under Inventory Constraints

MATHEMATICS OF OPERATIONS RESEARCH 2024年第1期49卷 1-651, C2页

作者： Chen, Xi Ma, Will Simchi-Levi, David Xin, Linwei NYU Stern Sch Business New York NY 10012 USA Columbia Univ Grad Sch Business New York NY 10027 USA MIT Inst Data Syst & Soc Cambridge MA 02139 USA MIT Dept Civil & Environm Engn Cambridge MA 02139 USA MIT Operat Res Ctr Cambridge MA 02139 USA Univ Chicago Booth Sch Business Chicago IL 60637 USA

In this paper, we consider a personalized assortment planning problem under inventory constraints, where each arriving customer type is defined by a primary item of interest. As long as that item is in stock, the customer adds it to the shopping cart, at which point the retailer can recommend to the customer an assortment of add-ons to go along with the primary item. This problem is motivated by the new "recommendation at checkout" systems that have been deployed at many online retailers, and it also serves as a framework that unifies many existing problems in online algorithms (e.g., personalized assortment planning, single-leg booking, and online matching with stochastic rewards). In our problem, add-on recommendation opportunities are eluded when primary items go out of stock, which poses additional challenges for the development of an online policy. We overcome these challenges by introducing the notion of an inventory protection level in expectation and derive an algorithm with a 1/4-competitive ratio guarantee under adversarial arrivals.

关键词： revenue management personalized recommendations online algorithms competitive ratio

来源：评论

学校读者我要写书评

暂无评论

An Improved Deterministic Algorithm for the online Min-Sum Set Cover Problem 1

引用

21st International Workshop on Approximation and online algorithms (WAOA) part of ALGO Conference

作者： Basiak, Mateusz Bienkowski, Marcin Tatarczuk, Agnieszka Univ Wroclaw Wroclaw Poland

ISBN: (数字)9783031498152

ISBN: (纸本)9783031498145;9783031498152

We study the online variant of the Min-Sum Set Cover problem (Mssc), a generalization of the well-known list update problem. In the Mssc problem, an algorithm has to maintain the time-varying permutation of the list of n elements, and serve a sequence of requests R-1, R-2,..., R-t,.... Each R-t is a subset of elements of cardinality at most r. For a requested set R-t, an online algorithm has to pay the cost equal to the position of the first element from R-t on its list. Then, it may arbitrarily permute its list, paying the number of swapped adjacent element pairs. We present the first constructive deterministic algorithm, whose competitive ratio does not depend on n. Our algorithm is O(r(2))-competitive, which beats both the existential upper bound of O(r(4)) by Bienkowski and Mucha [AAAI '23] and the previous constructive bound of O(r(3/2) center dot root n) by Fotakis et al. [ICALP '20]. Furthermore, we show that our algorithm attains an asymptotically optimal competitive ratio of O(r) when compared to the best fixed permutation of elements.

关键词： Min-sum set cover Derandomization online algorithms Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

online Hitting Set of d-Dimensional Fat Objects 21th

Online Hitting Set of d-Dimensional Fat Objects

引用

21st International Workshop on Approximation and online algorithms (WAOA) part of ALGO Conference

作者： Alefkhani, Shanli Khodaveisi, Nima Mari, Mathieu IDEAS NCBR Warsaw Poland Univ Warsaw Warsaw Poland

ISBN: (纸本)9783031498145;9783031498152

We consider an online version of the geometric minimum hitting set problem that can be described as a game between an adversary and an algorithm. For some integers d and N, let P be the set of points in (0, N)(d) with integral coordinates, and let O be a family of subsets of P, called objects. Both P and O are known in advance by the algorithm and by the adversary. Then, the adversary gives some objects one by one, and the algorithm has to maintain a valid hitting set for these objects using points from P, with an immediate and irrevocable decision. We measure the performance of the algorithm by its competitive ratio, that is the ratio between the number of points used by the algorithm and the offline minimum hitting set for the sub-sequence of objects chosen by the adversary. We present a simple deterministic online algorithm with competitive ratio ((4a + 1)(2d) logN) when objects correspond to a family of a-fat objects. Informally, alpha-fatness measures how cube-like is an object. We show that no algorithm can achieve a better ratio when a and d are fixed constants. In particular, our algorithm works for two-dimensional disks and d-cubes which answers two open questions from related previous papers in the special case where the set of points corresponds to all the points of integral coordinates with a fixed d-cube.

关键词： online algorithms Minimum hitting set Euclidean Plane

来源：评论

学校读者我要写书评

暂无评论

Two-way and one-way quantum and classical automata with advice for online minimization problems

引用

THEORETICAL COMPUTER SCIENCE 2022年 920卷 76-94页

作者： Khadiev, Kamil Khadieva, Aliya Ziatdinov, Mansur Mannapov, Ilnaz Kravchenko, Dmitry Rivosh, Alexander Yamilov, Ramis RAS Zavoisky Phys Tech Inst FRC Kazan Sci Ctr 10-7 Sibirsky Trakt St Kazan 420029 Russia Kazan Fed Univ Inst Computat Math & Informat Technol 18 Kremlevskaya St Kazan 420008 Russia Univ Latvia Ctr Quantum Comp Scince Fac Comp 19 Raina Bulv LV-1586 Riga Latvia Univ Latvia Fac Comp 19 Raina Bulv LV-1586 Riga Latvia Yandex Technol LLC 16 Leo Tolstoy St Moscow 119021 Russia

We consider online algorithms. Typically, the model is investigated with respect to the competitive ratio. In this paper, we explore two-way automata and one-way automata as models for online algorithms. We focus on quantum and classical online algorithms. We show that there are problems that can be solved more efficiently by two-way automata with quantum and classical states than by classical two-way automata in the case of sublogarithmic memory (sublinear size), even if classical automata get advice bits. Additionally, we show that there are problems that can be solved more efficiently by oneway quantum automata than by classical one-way automata in the case of sublogarithmic memory (resp., sublinear size) and in the case of logarithmic memory (resp., linear size) even if classical automata get advice bits. (C) 2022 Elsevier B.V. All rights reserved.

关键词： Quantum computation online algorithms Streaming algorithms online minimization problems Two-way automata Automata

来源：评论

学校读者我要写书评

暂无评论

online total bipartite matching problem

引用

OPTIMIZATION LETTERS 2022年第5期16卷 1411-1426页

作者： Shanks, Meghan Jacobson, Sheldon H. Univ Illinois Dept Comp Sci Champaign IL 61820 USA

This paper analyzes a variant of online Bipartite Matching in which incoming jobs must be matched to some worker, even if there are no available edges. A reward is only gained for matchings that are made across some edge. This paper gives matching upper and lower bounds for the most general version of this variation. It then provides an optimal policy for this problem when the underlying bipartite graph meets certain conditions and then identifies the most general conditions under which this policy is guaranteed to be optimal.

关键词： Bipartite matching online algorithms Randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

The Power of Migrations in Dynamic Bin Packing

引用

PROCEEDINGS OF THE ACM ON MEASUREMENT AND ANALYSIS OF COMPUTING SYSTEMS 2024年第3期8卷 1-28页

作者： Mellou, Konstantina Molinaro, Marco Zhou, Rudy Microsoft Res Redmond WA 98052 USA Pontificia Univ Catolica Rio de Janeiro Rio de Janeiro Brazil Carnegie Mellon Univ Pittsburgh PA USA

In the Dynamic Bin Packing problem, n items arrive and depart the system in an online manner, and the goal is to maintain a good packing throughout. We consider the objective of minimizing the total active time, i.e., the sum of the number of open bins over all times. An important tool for maintaining an efficient packing in many applications is the use of migrations ; e.g., transferring computing jobs across different machines. However, there are large gaps in our understanding of the approximability of dynamic bin packing with migrations. Prior work has covered the power of no migrations and > n migrations, but we ask the question: What is the power of limited (≤ n) migrations?Our first result is a dichotomy between no migrations and linear migrations: Using a sublinear number of migrations is asymptotically equivalent to doing zero migrations, where the competitive ratio grows with μ, the ratio of the largest to smallest item duration. On the other hand, we prove that for every α ∈ (0,1], there is an algorithm that does ≈ α n migrations and achieves competitive ratio ≈ 1/α (in particular, independent of μ); we also show that this tradeoff is essentially best possible. This fills in the gap between zero migrations and > n migrations in Dynamic Bin ***, in light of the above impossibility results, we introduce a new model that more directly captures the impact of migrations. Instead of limiting the number of migrations, each migration adds a delay of C time units to the item's duration; this commonly appears in settings where a blackout or set-up time is required before the item can restart its execution in the new bin. In this new model, we prove a O(min(√C, μ))-approximation, and an almost matching lower bound. We also present preliminary experiments that indicate that our theoretical results are predictive of the practical performance of our algorithms.

关键词： bin packing online algorithms

来源：评论

学校读者我要写书评

暂无评论

Resource Augmentation Analysis of the Greedy Algorithm for the online Transportation Problem 12

Resource Augmentation Analysis of the Greedy Algorithm for t...

引用

12th Latin-American algorithms, Graphs and Optimization Symposium (LAGOS)

作者： Arndt, Stephen Ascher, Josh Pruhs, Kirk Univ Pittsburgh Comp Sci Dept Pittsburgh PA 15260 USA

We consider the online transportation problem set in a metric space containing parking garages of various capacities. Cars arrive over time, and must be assigned to an unfull parking garage upon their arrival. The objective is to minimize the aggregate distance that cars have to travel to their assigned parking garage. We show that the natural greedy algorithm, augmented with garages of k >= 3 times the capacity, is (1 + 2/k-2)-competitive.(C) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (https://***/licenses/by-nc-nd/4.0)

关键词： online algorithms Weighted Bipartite Matching Competitive Analysis

来源：评论

学校读者我要写书评

暂无评论

Breaking the 2-competitiveness barrier for two servers in a tree

引用

THEORETICAL COMPUTER SCIENCE 2023年 977卷

作者： Bein, Wolfgang Larmore, Lawrence L. Univ Nevada Dept Comp Sci Las Vegas NV 89154 USA

A randomized on-line algorithm is given for the 2-server problem on a tree, with competitiveness less than 1.94 against the oblivious adversary. This is the first algorithm for this problem with competitive ratio less than 2. The algorithm generalizes earlier work for the line using fractional analysis, and defines a potential in terms of isolation indices from T-theory. (c) 2023 Elsevier B.V. All rights reserved.

关键词： online algorithms Randomized algorithms Tree metric spaces Server problem T-theory Game theory

来源：评论

学校读者我要写书评

暂无评论

Towards Uniform online Spherical Tessellations

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2022年第4期67卷 1124-1146页

作者： Bell, Paul C. Potapov, Igor Liverpool John Moores Univ Sch Comp Sci & Math James Parsons BldgByrom StL3-3AF Liverpool Merseyside England Univ Liverpool Dept Comp Sci Ashton BldgAshton St Liverpool L69 3BX Merseyside England

The problem of uniformly placing N points onto a sphere finds applications in many areas. For example, points on the sphere correspond to unit quaternions as well as to the group of rotations SO(3) and the online version of generating uniform rotations (known as "incremental generation") plays a crucial role in a large number of engineering applications ranging from robotics and aeronautics to computer graphics. An online version of this problem was recently studied with respect to the gap ratio as a measure of uniformity. The first online algorithm of Chen et al. was upperbounded by 5.99 and later improved to 3.69, which is achieved by considering a circumscribed dodecahedron followed by a recursive decomposition of each face. In this paper we provide a more efficient tessellation technique based on the regular icosahedron, which improves the upper-bound for the online version of this problem, decreasing it to approximately 2.84. Moreover, we show that the lower bound for the gap ratio of placing at least three points is (1 + root 5)/2 approximate to 1.618 and for at least four points is no less than 1.726.

关键词： online algorithms Discrepancy theory Spherical trigonometry Uniform point placement Computational geometry

来源：评论

学校读者我要写书评

暂无评论

online Nonnegative CP-Dictionary Learning with Applications to Multimodal Data

Online Nonnegative CP-Dictionary Learning with Applications ...

引用

作者： Strohmeier, Christopher William University of California Los Angeles

学位级别：Ph.D., Doctor of Philosophy

In this thesis, we present a myriad of applications of online matrix and tensor dictionary learning algorithms to the analysis of time series and image data, as well as a theoretical analysis of our algorithm, online CP-Dictionary Learning (OCPDL). First, we present a method which applies online nonnegative matrix factorization (ONMF), an algorithm which learns a sparse, nonnegative representation of streaming data, to perform joint dictionary learning on multivariate COVID-19 time-series data, followed by a certain “restrict and predict" algorithm to tackle the future time regression problem. Next, we apply ONMF to meteorological time series data, as well as to video data, and demonstrate the particular utility of online as opposed to offline algorithms in dealing with said data. In the following section, we present our extension of ONMF, our OCPDL algorithm, as well as a proof of some convergence guarantees.

关键词： Dictionary learning online algorithms Tensor decompositions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：