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

Assortment Optimization with Multi-Item Basket Purchase Under Multivariate MNL Model

M&SOM-MANUFACTURING & SERVICE OPERATIONS MANAGEMENT 2024年第1期26卷 1-406, C2页

作者： Jasin, Stefanus Lyu, Chengyi Najafi, Sajjad Zhang, Huanan Univ Michigan Stephen M Ross Sch Business Ann Arbor MI 48109 USA Univ Colorado Boulder Leeds Sch Business Boulder CO 80309 USA HEC Paris Dept Informat Syst & Operat Management F-78350 Jouy En Josas France

Problem definition: Assortment selection is one of the most important decisions faced by retailers. Most existing papers in the literature assume that customers select at most one item out of the offered assortment. Although this is valid in some cases, it contradicts practical observations in many shopping experiences, both in online and brick-and mortar retail, where customers may buy a basket of products instead of a single item. In this paper, we incorporate customers' multi-item purchase behavior into the assortment optimization problem. We consider both the uncapacitated and capacitated assortment problems under the so-called Multivariate MNL (MVMNL) model, which is one of the most popular multivariate choice models used in the marketing and empirical literature. Methodology/results: We first show that the traditional revenue-ordered assortment may not be optimal. Nonetheless, we show that under some mild conditions, a certain variant of this property holds (in the uncapacitated assortment problem) under the MVMNL model;that is, the optimal assortment consists of revenue-ordered local assortments in each product category. Finding the optimal assortment even when there is no interaction among product categories is still computationally expensive because the revenue thresholds for different categories cannot be computed separately. To tackle the computational complexity, we develop FPTAS for several variants of (capacitated and uncapacitated) assortment problems under MVMNL. Managerial implications: Our analysis reveals that disregarding customers' multi-item purchase behavior in assortment decisions can indeed have a significant negative impact on profitability, demonstrating its practical importance in retail. We numerically show that our proposed algorithm can improve a retailer's expected total revenues (compared with a benchmark policy that does not properly take into account the impact of customers' multi-item choice behavior in assortment decision) by up

关键词： assortment optimization multi-item choice model dynamic programming approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Caching With Personalized and Incumbent-Aware Recommendation: Modeling and Optimization

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2024年第10期23卷 9595-9613页

作者： Zhao, Yi Yu, Zhanwei Yuan, Di Uppsala Univ Dept Informat Technol S-75105 Uppsala Sweden

Caching popular contents at cell edge has been recognized as a promising way to facilitate rapid content delivery and alleviate backhaul burden. The content popularity is greatly influenced by recommendations by content providers. In this paper, we leverage this fact to jointly optimize caching and recommendation towards higher caching efficiency. We focus on both personalized and incumbent-aware recommendation. The incumbent content refers to the content that a user is currently browsing, resulted by the user's short-term interest. We model and formulate the resulting cache efficiency maximization problem subject to user satisfaction requirements. We prove the NP-hardness of the problem, and reformulate it using integer linear programming, enabling to solve optimally small-scale instances. Based on problem analysis with a graph representation, we derive three polynomial-time algorithms, where the recommendation sub-problem is solved to global optimum. Among these algorithms, the first two are based on sub-modularity, with 1-e(-1) approximation guarantee under mild conditions, while the last one is an alternation-based algorithm with fast convergence. Numerical results show the close-to-optimal performance of the proposed algorithms.

关键词： Optimization approximation algorithms Mobile computing Capacity planning Web sites Videos Video on demand Recommendation caching content delivery network (CDN) approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Joint Optimization of Mobility and Reliability-Guaranteed Air-to-Ground Communication for UAVs

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2024年第1期23卷 566-580页

作者： Zhou, Jianshan Tian, Daxin Yan, Yaqing Duan, Xuting Shen, Xuemin Beihang Univ Beijing Adv Innovat Ctr Big Data & Brain Comp Sch Transportat Sci & Engn Beijing Key Lab Cooperat Vehicle Infrastruct Syst Beijing 100191 Peoples R China Zhongguancun Lab Beijing 100094 Peoples R China Univ Waterloo Elect & Comp Engn Dept Waterloo ON N2L 3G1 Canada

Aerial unmanned vehicles (UAVs) play a significant role in improving the connectivity and coverage of terrestrial communication networks. However, UAV-assisted air-to-ground (A2G) data transmissions usually encounter several fundamental challenges, such as terminal mobility, random nature in channel fading and contention, resource constraints, and application-specific transmission requirements. To tackle these challenges, we formulate a bi-level optimization problem that jointly considers the control of the UAV mobility and transmission power and the scheduling of A2G data transmissions. The objective is to optimize energy consumption and maximize A2G transmission reliability. Particularly, we first theoretically characterize the A2G transmission reliability from a probabilistic perspective concerning the effects of channel fading, channel access contention, and application requirements. We then derive a closed-form expression for the optimal expected transmission reliability. Using the closed-form reliability, we transform the bi-level optimization into a mathematically-tractable optimal control problem and propose an efficient iterative algorithm to solve it. Simulation results show that our approach provides a comprehensive improvement in terms of both energy utilization and A2G transmission reliability, in particular, with a reduction of more than 12.1% in energy consumption and an increase of 7.53% in reliability on average, compared to several baselines.

关键词： Optimization Reliability Data communication Trajectory Autonomous aerial vehicles Reliability theory approximation algorithms Air-to-ground communication data transmission scheduling trajectory design unmanned aerial vehicle

来源：评论

学校读者我要写书评

暂无评论

The Near Exact Bin Covering Problem

引用

ALGORITHMICA 2024年第6期86卷 2041-2066页

作者： Levin, Asaf Technion Fac Data & Decis Sci Haifa 32000 Israel

We present a new generalization of the bin covering problem that is known to be a strongly NP-hard problem. In our generalization there is a positive constant Delta, and we are given a set of items each of which has a positive size. We would like to find a partition of the items into bins. We say that a bin is near exact covered if the total size of items packed into the bin is between 1 and 1+Delta. Our goal is to maximize the number of near exact covered bins. If Delta=0 or Delta>0 is given as part of the input, our problem is shown here to have no approximation algorithm with a bounded asymptotic approximation ratio (assuming that P not equal NP). However, for the case where Delta>0 is seen as a constant, we present an asymptotic fully polynomial time approximation scheme (AFPTAS) that is our main contribution.

关键词： Bin covering Asymptotic approximation ratio approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Affine Automorphism Group of Polar Codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第9期70卷 6280-6296页

作者： Ye, Zicheng Li, Yuan Zhang, Huazi Wang, Jun Yan, Guiying Ma, Zhiming Huawei Technol Co Ltd Hangzhou 310051 Peoples R China Univ Chinese Acad Sci Sch Math Sci Beijing 100190 Peoples R China Chinese Acad Sci Acad Math & Syst Sci Beijing 100190 Peoples R China

The automorphism ensemble (AE) decoding framework for polar codes attracts much attention recently. It decodes multiple permuted codewords with successive cancellation (SC) decoders in parallel and hence has lower latency compared to successive cancellation list (SCL) decoding. However, the AE decoding framework is ineffective for permutations falling into the lower-triangular affine (LTA) automorphism group, as they are invariant under SC decoding. Therefore, the block lower-triangular affine (BLTA) group was discovered to achieve better AE decoding performance. However, the equivalence of the BLTA group and the complete affine automorphism group was unresolved. Additionally, some automorphisms in BLTA group are also SC-invariant, thus are redundant in AE decoding. In this paper, we prove that BLTA group coincides with the complete automorphisms of decreasing polar codes that can be formulated as affine transformations. Also, we find a necessary and sufficient condition related to the block lower-triangular structure of transformation matrices to identify SC-invariant automorphisms. Furthermore, We present an algorithm that efficiently identifies all SC-invariant affine automorphisms under specific constructions.

关键词： Decoding Polar codes Codes Vectors Complexity theory approximation algorithms Timing automorphism decoding affine automorphism groups successive cancellation (SC)-invariant affine automorphism groups

来源：评论

学校读者我要写书评

暂无评论

Earliest Deadline First Is a 2-approximation for DARP with Time Windows 16th

Earliest Deadline First Is a 2-Approximation for DARP with...

引用

16th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2023

作者： Anthony, Barbara M. Chung, Christine Das, Ananya Yuen, David Southwestern University GeorgetownTX78626 United States Connecticut College New LondonCT06320 United States Middlebury College MiddleburyVT05753 United States Kapolei HI96707 United States

ISBN: (纸本)9783031496134

Dial-a-Ride problems (DARP) require determining a schedule to efficiently serve transportation requests in various scenarios. We consider a variant of offline DARP in a uniform metric space where requests have release times and deadlines, and are all of equal duration and value. The goal is for a single unit-speed, unit-capacity server to serve as many requests as possible by an overall time limit, and this problem is NP-hard. We show that a natural greedy algorithm, Earliest Deadline First, is a 2-approximation, and this is tight. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Fully polynomial time (Sigma, Pi)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs

引用

MATHEMATICAL PROGRAMMING 2022年第1-2期195卷 183-242页

作者： Halman, Nir Nannicini, Giacomo Bar Ilan Univ Ramat Gan Israel IBM TJ Watson Res Ctr IBM Quantum Yorktown Hts NY USA

We study the nonlinear newsvendor problem concerning goods of a non-discrete nature, and a class of stochastic dynamic programs with several application areas such as supply chain management and economics. The class is characterized by continuous state and action spaces, either convex or monotone cost functions that are accessed via value oracles, and affine transition functions. We establish that these problems cannot be approximated to any degree of either relative or additive error, regardless of the scheme used. To circumvent these hardness results, we generalize the concept of fully polynomial-time approximation scheme allowing arbitrarily small additive and multiplicative error at the same time, while requiring a polynomial running time in the input size and the error parameters. We develop approximation schemes of this type for the classes of problems mentioned above. In light of our hardness results, such approximation schemes are "best possible". A computational evaluation shows the promise of this approach.

关键词： Newsvendor problem Stochastic inventory control Hardness of approximation approximation algorithms Stochastic dynamic programming K -approximation sets and functions

来源：评论

学校读者我要写书评

暂无评论

Near-optimal distributed dominating set in bounded arboricity graphs

引用

DISTRIBUTED COMPUTING 2024年第4期37卷 387-398页

作者： Dory, Michal Ghaffari, Mohsen Ilchi, Saeed Univ Haifa Dept Comp Sci Haifa Israel MIT Dept Elect Engn & Comp Sci Cambridge MA USA Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland

We describe a simple deterministic O(e-1 log A) round distributed algorithm for (2a + 1)(1 + e) approximation of minimum weighted dominating set on graphs with arboricity at most a. Here A denotes the maximum degree. We also show a lower bound proving that this round complexity is nearly optimal even for the unweighted case, via a reduction from the celebrated KMW lower bound on distributed vertex cover approximation (Kuhn et al. in JACM 63:116, 2016). Our algorithm improves on all the previous results (that work only for unweighted graphs) including a randomized O(a(2)) approximation in O(log n) rounds (Lenzen et al. in International symposium on distributed computing, Springer, 2010), a deterministic O(a log ?) approximation in O(log A) rounds (Lenzen et al. in international symposium on distributed computing, Springer, 2010), a deterministic O(a) approximation in O(log(2)?) rounds (implicit in Bansal et al. in Inform Process Lett 122:21-24, 2017;Proceeding 17th symposium on discrete algorithms (SODA), 2006), and a randomized O(a) approximation in O(a log n) rounds (Morgan et al. in 35th International symposiumon distributed computing, 2021). We also provide a randomized O(a log ?) round distributed algorithm that sharpens the approximation factor to a (1 + o(1)). If each node is restricted to do polynomial-time computations, our approximation factor is tight in the first order as it is NP-hard to achieve a - 1 - e approximation (Bansal et al. in Inform Process Lett 122:21-24, 2017).

关键词： Distributed computing Dominating set Arboricity approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Model-Free Optimal Tracking Control of Nonlinear Input-Affine Discrete-Time Systems via an Iterative Deterministic Q-Learning Algorithm

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2024年第1期35卷 999-1012页

作者： Song, Shijie Zhu, Minglei Dai, Xiaolin Gong, Dawei Univ Elect Sci & Technol China Sch Mech & Elect Engn Chengdu 611731 Peoples R China

In this article, a novel model-free dynamic inversion-based Q-learning (DIQL) algorithm is proposed to solve the optimal tracking control (OTC) problem of unknown nonlinear input-affine discrete-time (DT) systems. Compared with the existing DIQL algorithm and the discount factor-based Q-learning (DFQL) algorithm, the proposed algorithm can eliminate the tracking error while ensuring that it is model-free and off-policy. First, a new deterministic Q-learning iterative scheme is presented, and based on this scheme, a model-based off-policy DIQL algorithm is designed. The advantage of this new scheme is that it can avoid the training of unusual data and improve data utilization, thereby saving computing resources. Simultaneously, the convergence and stability of the designed algorithm are analyzed, and the proof that adding probing noise into the behavior policy does not affect the convergence is presented. Then, by introducing neural networks (NNs), the model-free version of the designed algorithm is further proposed so that the OTC problem can be solved without any knowledge about the system dynamics. Finally, three simulation examples are given to demonstrate the effectiveness of the proposed algorithm.

关键词： Heuristic algorithms Q-learning Nonlinear dynamical systems approximation algorithms Iterative algorithms Convergence Artificial neural networks Adaptive dynamic programming (ADP) neural network (NN) off-policy technique optimal tracking control (OTC) Q-learning

来源：评论

学校读者我要写书评

暂无评论

Cubic Polishing Spline-Based algorithms for Industrial Image Processing

引用

IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS 2024年第1期20卷 314-326页

作者： Sun, Fangli Cai, Zhanchuan Macau Univ Sci & Technol Sch Comp Sci & Engn Macau 999078 Peoples R China

Industrial image processing is a major technology in the fourth industrial revolution. In recent years, the spline method has gained more and more attention in image processing. To explore an efficient industrial image processing algorithm, this article proposes novel cubic polishing spline algorithms. The cubic polishing spline is a high precision spline algorithm that brings more degrees of freedom by adding nodes to better balance the local and global aspects. First, the direct and indirect cubic polishing spline transforms are used for the image interpolation filter. Then, we construct the least squares cubic polishing spline and pyramid approximation method with application to the image reconstruction and image scaling (image upscaling or downscaling). Next, the frequency domain cubic polishing spline lowpass filter and highpass filter are proposed, and the proposed schemes are applied to image smoothing and image sharpening, respectively. Finally, the peak signal-to-noise ratio (PSNR) and structural similarity index (SSIM) and root mean square error (RMSE) evaluation metrics are used to illustrate the reconstruction effects, and experiments show that the algorithms proposed in this article can achieve better reconstruction results with better fidelity and competitiveness compared with other schemes.

关键词： Splines (mathematics) Image reconstruction Image processing Interpolation Signal processing algorithms approximation algorithms Filtering algorithms approximation method image reconstruction image scaling interpolation polishing spline

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：