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

Technical Note-Near-Optimal Bayesian Online Assortment of Reusable Resources

OPERATIONS RESEARCH 2024年第5期72卷 iii-vii, 1751-2261, C2-C3页

作者： Feng, Yiding Niazadeh, Rad Saberi, Amin Univ Chicago Booth Sch Business Chicago IL 60637 USA Stanford Univ Management Sci & Engn Stanford CA 94305 USA

Motivated by the applications of rental services in e-commerce, we consider revenue maximization in online assortment of reusable resources for a stream of arriving consumers with different types. We design competitive online algorithms with respect to the optimum online policy in the Bayesian setting in which types are drawn independently from known heterogeneous distributions over time. In the regime where the minimum of initial inventories cmin is large, our main result is a near-optimal 1. min 12, root log(c(min))=c(min). p. competitive algorithm for the general case of reusable resources. Our algorithm relies on an expected LP benchmark for the problem, solves this LP, and simulates the solution through an independent randomized rounding. The main challenge is obtaining point-wise inventory feasibility in a computationally efficient fashion from these simulation-based algorithms. To this end, we use several technical ingredients to design discarding policies-one for each resource. These policies handle the trade-off between the inventory feasibility under reusability and the revenue loss of each of the resources. However, discarding a unit of a resource changes the future consumption of other resources. To handle this new challenge, we also introduce postprocessing assortment procedures that help with designing and analyzing our discarding policies as they run in parallel, which might be of independent interest. As a side result, by leveraging techniques from the literature on prophet inequality, we further show an improved near-optimal 1. 1= root c(min) + 3v competitive algorithm for the special case of nonreusable resources. We finally evaluate the performance of our algorithms using the numerical simulations on the synthetic data.

关键词： analysis of algorithms suboptimal algorithms inventory/production approximations/heuristics

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

ASYMPTOTIC analysis OF PERES' ALGORITHM FOR RANDOM NUMBER GENERATION

引用

PROBABILITY IN THE ENGINEERING AND INFORMATIONAL SCIENCES 2022年第2期36卷 341-356页

作者： Lim, Zhao Ging Liao, Chen-Tuo Yao, Yi-Ching Natl Taiwan Univ Div Biometry Inst Agron 1Sec 4Roosevelt Rd Taipei 106 Taiwan Acad Sinica Inst Stat Sci Taipei 115 Taiwan

von Neumann [(1951). Various techniques used in connection with random digits. National Bureau of Standards Applied Math Series 12: 36-38] introduced a simple algorithm for generating independent unbiased random bits by tossing a (possibly) biased coin with unknown bias. While his algorithm fails to attain the entropy bound, Peres [(1992). Iterating von Neumann's procedure for extracting random bits. The Annals of Statistics 20(1): 590-597] showed that the entropy bound can be attained asymptotically by iterating von Neumann's algorithm. Let b(n, p) denote the expected number of unbiased bits generated when Peres' algorithm is applied to an input sequence consisting of the outcomes of n tosses of the coin with bias p. With p =1/2, the coin is unbiased and the input sequence consists of n unbiased bits, so that n - b(n, 1/2) may be referred to as the cost incurred by Peres' algorithm when not knowing p = 1/2 We show that lim(n ->infinity) log[n - b(n, 1/2)]/log n = theta = log[1 +root 5)/2] (where log is the logarithm to base 2), which together with limited numerical results suggests that n - b(n,1/2) may be a regularly varying sequence of index theta. (A positive sequence {L(n)} is said to be regularly varying of index theta if lim(n ->infinity) L(left perpendicular lambda n right perpendicular)/L(n) = lambda(theta) for lambda > 0, where left perpendicular x right perpendicular denotes the largest integer not exceeding x.) Some open problems on the asymptotic behavior of nh(p) - b(n, p) are briefly discussed where h(p) = -p log p - (1 - p) log(1 - p) denotes the Shannon entropy of a random bit with bias p.

关键词： analysis of algorithms elias' extractor entropy peres' extractor regularly varying sequence superadditivity von neumann's extractor

来源：评论

学校读者我要写书评

暂无评论

AN ALGORITHM TO RECOVER SHREDDED RANDOM MATRICES

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2024年第3期38卷 2509-2529页

作者： Atamanchuk, Caelan Devroye, Luc Vicenzo, Massimo McGill Univ Math Montreal PQ H3A 0G4 Canada McGill Univ Comp Sci Montreal PQ H3A 2K6 Canada Univ Waterloo Combinator & Optimizat Waterloo ON N2L 3G1 Canada

Given some binary matrix M , suppose we are presented with the collection of its rows and columns in independent arbitrary orderings. From this information, can we recover the unique original orderings and matrix? We present an algorithm that identifies whether there is a unique ordering associated with a set of rows and columns, and outputs either the unique correct orderings for the rows and columns or the full collection of all valid orderings and valid matrices. We show that there is a constant c > 0 such that the algorithm terminates in O(n(2)) time with high probability and in expectation for random n \times n binary matrices with i.i.d. entries (m(ij))(ij =1)(n) such that P(m(ij) = 1) = p and c log(2) (n)/n (log log(n))(2) <= p <= 1/2 .

关键词： combinatorial probability matrix reconstruction graph reconstruction analysis of algorithms expected complexity

来源：评论

学校读者我要写书评

暂无评论

Statistical properties of a class of randomized binary search algorithms

引用

PERFORMANCE EVALUATION 2025年 168卷

作者： Xia, Ye Univ Florida Dept Comp & Informat Sci & Engn Gainesville FL 32611 USA

In this paper, we analyze the statistical properties of a randomized binary search algorithm and its variants. These algorithms have applications in caching and load balancing in distributed environments such as peer-to-peer networks, cloud storage, data centers, and content distribution networks. The basic discrete version of the problem is as follows. Suppose there are m servers, numbered 1, 2, ... , m, out of which the first k servers are marked as special, where k is unknown. These k servers may contain a particular file or service that clients want. The objective is to select one of the marked servers uniformly at random. Considering the intended applications, we impose the constraint that there is no central controller to facilitate the selection process. We start with a basic algorithm: In each step, the client requesting the service chooses a number y uniformly at random from 1, 2, ... , x, where x is the number chosen in the previous step, initially set to m in the first step. A query is then sent to server y asking whether y is marked. If the answer is yes, the algorithm returns y;otherwise, the process is repeated with x <- y. In this paper, we primarily consider two batch versions of this algorithm in which multiple numbers are chosen in each step and multiple queries are made in parallel. We derive the mean and variance (exact and/or asymptotic) for the number of search steps in each version of the algorithm, and when possible, we give its distribution. Additionally, we analyze the access pattern of queries across the entire search space.

关键词： analysis of algorithms Parallel and distributed algorithms Randomized binary search algorithm Distributed search Load balancing

来源：评论

学校读者我要写书评

暂无评论

Non-uniform birthday problem revisited: Refined analysis and applications to discrete logarithms

引用

INFORMATION PROCESSING LETTERS 2022年 175卷

作者： Wu, Haoxuan Zhuang, Jincheng Duan, Qianheng Zhu, Yuqing Shandong Univ Sch Cyber Sci & Technol Qingdao 266237 Peoples R China Henan Key Lab Network Cryptog Technol Zhengzhou 450001 Peoples R China Shandong Univ Minist Educ Key Lab Cryptol Technol & Informat Secur Qingdao 266237 Peoples R China Beijing Jiaotong Univ Beijing Key Lab Secur & Privacy Intelligent Trans Beijing 100044 Peoples R China Beijing Jiaotong Univ Sch Comp & Informat Technol Beijing 100044 Peoples R China

The result of birthday problem is of fundamental importance and has many applications in diverse areas, analyzing the discrete logarithm problem in particular. The birthday problem can be modeled as sampling balls with replacement until one is sampled twice. In the classical scenario, balls are sampled uniformly. Inspired by the analysis of algorithms solving certain discrete logarithms, Galbraith and Holmes considered the non-uniform birthday problem and gave an estimate on the number of sampling before having a collision up to the dominating term. In this paper, we give a refined analysis to the non-uniform birthday problem, and apply it to the analysis of an algorithm solving certain discrete logarithm problem. Experiment results suggest that parameter selection following this refined analysis performs better than related work. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Birthday problem Discrete logarithm problem Public key cryptography analysis of algorithms Parameter selection

来源：评论

学校读者我要写书评

暂无评论

Improved Online Contention Resolution for Matchings and Applications to the Gig Economy

引用

MATHEMATICS OF OPERATIONS RESEARCH 2024年第3期49卷 1582-1606页

作者： Pollner, Tristan Roghani, Mohammad Saberi, Amin Wajc, David Stanford Univ Management Sci & Engn Stanford CA 94305 USA Google Res Mountain View CA 94043 USA

Motivated by applications in the gig economy, we study approximation algorithms for a sequential pricing problem. The input is a bipartite graph G. (I, J, E) between individuals I and jobs J. The platform has a value of v(j) for matching job j to an individual worker. In order to find a matching, the platform can consider the edges (ij) is an element of E in any order and make a one-time take-it-or-leave-it offer of a price pi(ij) = w of its choosing to i for completing j. The worker accepts the offer with a known probability p(ijw) in this case, the job and the worker are irrevocably matched. What is the best way to make offers to maximize revenue and/or social welfare? The optimal algorithm is known to be NP-hard to compute (even if there is only a single job). With this in mind, we design efficient approximations to the optimal policy via a new random-order online contention resolution scheme (RO-OCRS) for matching. Our main result is a 0.456-balanced RO-OCRS in bipartite graphs and a 0.45-balanced RO-OCRS in general graphs. These algorithms improve on the recent bound of 1/2(1 - e(-2)) approximate to 0.432 and improve on the best-known lower bounds for the correlation gap of matching, despite applying to a significantly more restrictive setting. As a consequence of our online contention resolution scheme results, we obtain a 0.456-approximate algorithm for the sequential pricing problem. We further extend our results to settings where workers can only be contacted a limited number of times and show how to achieve improved results for this problem via improved algorithms for the well-studied stochastic probing problem.

关键词： analysis of algorithms matchings networks/graphs contention resolution schemes correlation gap online algorithms

来源：评论

学校读者我要写书评

暂无评论

There is no APTAS for 2-dimensional vector bin packing: Revisited

引用

INFORMATION PROCESSING LETTERS 2024年 183卷

作者： Ray, Arka Indian Inst Sci Bengaluru India

We study the Vector Bin Packing and the Vector Bin Covering problems, multidimensional generalizations of the Bin Packing and the Bin Covering problems, respectively. In the Vector Bin Packing, we are given a set of d-dimensional vectors from [0, 1](d) the aim is to partition the set into the minimum number of bins such that for each bin B, each component of the sum of the vectors in Bis at most 1. Woeginger [17] claimed that the problem has no APTAS for dimensions greater than or equal to 2. We note that there was a slight oversight in the original proof. In this work, we give a revised proof using some additional ideas from [3,8]. In fact, we show that it is NP-hard to get an asymptotic approximation ratio better than 600/599. An instance of Vector Bin Packing is called delta-skewed if every item has at most one dimension greater than delta. As a natural extension of our general d-Dimensional Vector Bin Packing result we show that for epsilon is an element of(0, 1/2500) it is NP-hard to obtain a (1 + epsilon)-approximation for d-Skewed Vector Bin Packing if delta> 20 root epsilon In the Vector Bin Covering problem given a set of d-dimensional vectors from [0, 1](d), the aim is to obtain a family of disjoint subsets (called bins) with the maximum cardinality such that for each bin B, each component of the sum of the vectors in Bis at least 1. Using ideas similar to our Vector Bin Packing result, we show that for Vector Bin Covering there is no APTAS for dimensions greater than or equal to 2. In fact, we show that it is NP-hard to get an asymptotic approximation ratio better than 998/997. (c) 2023 Elsevier B.V. All rights reserved.

关键词： analysis of algorithms Approximation algorithms Vector Bin Packing Hardness of Approximation Vector Bin Covering

来源：评论

学校读者我要写书评

暂无评论

Effect of global shrinkage parameter of horseshoe prior in compressed sensing

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2024年第5期2024卷 053402-053402页

作者： Nagano, Yasushi Hukushima, Koji Univ Tokyo Grad Sch Arts & Sci Meguro Ku Tokyo 1538902 Japan Univ Tokyo Komaba Inst Sci 3-8-1 KomabaMeguro Ku Tokyo 1538902 Japan

This study investigates the effect of the global shrinkage parameter tau of a horseshoe prior, one of the global-local shrinkage priors, on linear regression in sparse signal processing. Statistical mechanics methods are employed to examine the accuracy of signal estimation. The phase diagram of the success and failure of signal recovery in noiseless compressed sensing with varying tau is discussed from the viewpoint of dynamic characterization of approximate message passing (AMP) as a solving algorithm and static characterization of the free-energy landscape. It is found that there exists a parameter region where the AMP algorithm can hardly recover the true signal, even though the true signal is locally stable. The analysis of the free-energy landscape also provides important insight into the optimal choice of tau.

关键词： statistical inference analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Resolving degeneracies in Google search via quantum stochastic walks

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2024年第1期2024卷 013402-013402页

作者： Benjamin, Colin Dudhe, Naini Natl Inst Sci Educ & Res Bhubaneswar Sch Phys Sci Jatni 752050 India Homi Bhabha Natl Inst Training Sch Complex Mumbai 400094 India

The internet is one of the most valuable technologies invented to date. Among them, Google is the most widely used search engine. The PageRank algorithm is the backbone of Google search, ranking web pages according to relevance and recency. We employ quantum stochastic walks (QSWs) with the hope of bettering the classical PageRank (CPR) algorithm, which is based on classical continuous time random walks. We implement QSW via two schemes: only incoherence and dephasing with incoherence. PageRank using QSW with only incoherence or QSW with dephasing and incoherence best resolves degeneracies that are unresolvable via CPR and with a convergence time comparable to that for CPR, which is generally the minimum. For some networks, the two QSW schemes obtain a convergence time lower than CPR and an almost degeneracy-free ranking compared to CPR.

关键词： analysis of algorithms quantum computation quantum information random graphs networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：