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

Online Learning and Optimization for Revenue Problems with Add-on Discounts

MANAGEMENT SCIENCE 2022年第10期68卷 7402-7421页

作者： Simchi-Levi, David Sun, Rui Zhang, Huanan 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 MIT Inst Data Syst & Soc 77 Massachusetts Ave Cambridge MA 02139 USA Univ Colorado Boulder Leeds Sch Business Boulder CO 80309 USA

We study in this paper a revenue-management problem with add-on discounts. The problem is motivated by the practice in the video game industry by which a retailer offers discounts on selected supportive products (e.g., video games) to customers who have also purchased the core products (e.g., video game consoles). We formulate this problem as an optimization problem to determine the prices of different products and the selection of products for add-on discounts. In the base model, we focus on an independent demand structure. To overcome the computational challenge of this optimization problem, we propose an efficient fully polynomial-time approximation scheme (FPTAS) algorithm that solves the problem approximately to any desired accuracy. Moreover, we consider the problem in the setting in which the retailer has no prior knowledge of the demand functions of different products. To solve this joint learning and optimization problem, we propose an upper confidence bound???based learning algorithm that uses the FPTAS optimization algorithm as a subroutine. We show that our learning algorithm can converge to the optimal algorithm that has access to the true demand functions, and the convergence rate is tight up to a certain logarithmic term. We further show that these results for the independent demand model can be extended to multinomial logit choice models. In addition, we conduct numerical experiments with the real-world transaction data we collect from a popular video gaming brand???s online store on ***. The experiment results illustrate our learning algorithm???s robust performance and fast conver

关键词： revenue management add-on discount online learning approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Dynamic planning with reusable healthcare resources: application to appointment scheduling

引用

FLEXIBLE SERVICES AND MANUFACTURING JOURNAL 2022年第4期34卷 859-878页

作者： Zhao, Jingtong Wen, Hanqi Columbia Univ Dept Ind Engn & Operat Res New York NY 10027 USA Peking Univ Dept Ind Engn & Management Beijing Peoples R China

In healthcare management, one important problem is how to efficiently allocate resources with limited capacities. From the point of view of a central decision maker with a long planning horizon, many healthcare resources such as appointment slots, operation rooms, and hospital beds can be regarded as reusable resources. Motivated by this observation, we study a new version of the assignment problem of reusable resources to sequentially arriving users. Different from previous works on reusable resources, we assume that each user will tell us the intended usage duration of each resource upfront before a decision needs to be made. In the setting where users arrive randomly according to a certain distribution, we propose an algorithm based on linear approximations of the optimal value functions, and show that it performs better than common methods developed for the case where usage times are known upon return in different simulations, as well as in a case study with real data. When users arrive in an adversarial order, we show by example that it is hard to design an algorithm with a lower-bounded competitive ratio. As users are much less likely to arrive in an adversarial order in reality, our proposed algorithm can be used to effectively schedule resources such as appointment slots and operation rooms in hospitals.

关键词： Online matching Reusable resources approximation algorithm Optimization

来源：评论

学校读者我要写书评

暂无评论

Gaussian downlink user selection subject to access limit, power budget, and rate demands

引用

THEORETICAL COMPUTER SCIENCE 2022年 931卷 78-92页

作者： Liu, Xiang Zou, Jinyu Chen, Pengpeng Wan, Peng-Jun Dongguan Univ Technol Dongguan Peoples R China IIT Chicago IL 60616 USA

Consider a Gaussian downlink between an access point with power budget P > 0, and a set of users specified by their effective noises and rate demands. In order to control the decoding complexity and error propagation, an integer-valued access limit M > 0 is imposed on the number of superimposed users. For each subset S of users, its (total) power demand p (S) is a strictly increasing and nonseparable function of the effective noises and rate demands of users in S. A subset S of users is feasible if |S| <= M and p (S) <= P. The goal is to select a feasible subset S of users whose total rate demand is maximized. In this paper, we show that this problem is NP-hard, and present a (1 -1/e)-approximation algorithm for this problem. In addition, we also give several other approximation algorithms with trade-offs between accuracy and efficiency. (C) 2022 Published by Elsevier B.V.

关键词： Successive interference cancellation Access limit User selection approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Multiple Cooperative Task Assignment on Reliability-Oriented Social Crowdsourcing

引用

IEEE TRANSACTIONS ON SERVICES COMPUTING 2022年第6期15卷 3402-3416页

作者： Zhao, Lu Tan, Wenan Li, Bo Xu, Lida Yang, Yun Nanjing Univ Aeronaut & Astronaut Coll Comp Sci & Technol Nanjing 210016 Peoples R China Shanghai Polytech Univ Sch Comp & Informat Engn Shanghai 201209 Peoples R China Old Dominion Univ Dept Informat Technol & Decis Sci Norfolk VA 23529 USA Swinburne Univ Technol Sch Software & Elect Engn Melbourne Vic 3122 Australia

With the rapid development of mobile devices, mobile social networks have drawn increasing attention from spatial crowdsourcing in which users sharing information via social networking applications can easily identify and participate in multiple cooperative tasks. Existing studies generally assume that all users are trustworthy and can reliably perform assigned tasks. However, such assumptions do not hold in real-world practices. In this article, we consider an essential crowdsourcing problem, namely Reliability-oriented Socially-Aware Crowdsourcing (R-SAC), which improves the reliability by recruiting users who are better matched to the tasks. Our R-SAC problem is to recruit reliable users for multiple cooperative tasks so that the overall reliability of task assignment is maximized. We prove that the R-SAC problem is NP-hard. Then, we propose an approximation algorithm with a factor of ln m + 1 to solve the R-SAC problem, where m is the number of tasks. Specifically, user reliability refers to the probability that a user can reliably perform assigned tasks. To achieve reliable user recruitment during task assignment, we formulate the reliability of a user by combining the matching between the user and tasks, and the reliability feedback from neighbors who share similar behaviors with the user in the social network. Besides, the distributed collaborative filtering technique is utilized to select the reliability feedback from the neighbors. We evaluate the performance of our proposed approach experimentally on two widely-used real-world datasets and the results demonstrate that our approach significantly outperforms five representative approaches.

关键词： Spatial crowdsourcing task assignment reliability-oriented influence propagation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On Performance of a Simple Multi-objective Evolutionary algorithm on the Constrained Minimum Spanning Tree Problem

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE SYSTEMS 2022年第1期15卷 1-11页

作者： Lai, Xinsheng Shaoxing Univ Dept Comp Sci & Engn Beihai St Shaoxing 312000 Zhejiang Peoples R China

The constrained optimization problems can be transformed into multi-objective optimization problems, and thus can be optimized by multi-objective evolutionary algorithms. This method has been successfully used to solve the constrained optimization problems. However, little theoretical work has been done on the performance of multi-objective evolutionary algorithms for the constrained optimization problems. In this paper, we theoretically analyze the performance of a multi-objective evolutionary algorithms on the constrained minimum spanning tree problem. First, we theoretically prove that the multi-objective evolutionary algorithm is capable of finding a (2,1)-approximation solution for the constrained minimum spanning tree problem in a pseudopolynomial runtime. Then, this simple multi-objective evolutionary algorithm is shown to be efficient on a constructed instance of the problem.

关键词： approximation algorithm Multi-objective evolutionary algorithm Constrained optimization Spanning tree problem Combinatorial problem

来源：评论

学校读者我要写书评

暂无评论

Toward Efficient Online Scheduling for Distributed Machine Learning Systems

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2022年第4期9卷 1951-1969页

作者： Yu, Menglu Liu, Jia Wu, Chuan Ji, Bo Bentley, Elizabeth S. Iowa State Univ Dept Comp Sci Ames IA 50011 USA Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA Virginia Tech Dept Comp Sci Blacksburg VA 24061 USA Univ Hong Kong Dept Comp Sci Hong Kong 999077 Peoples R China Air Force Res Lab Informat Directorate Rome NY 13441 USA

Recent years have witnessed a rapid growth of distributed machine learning (ML) frameworks, which exploit the massive parallelism of computing clusters to expedite ML training. However, the proliferation of distributed ML frameworks also introduces many unique technical challenges in computing system design and optimization. In a networked computing cluster that supports a large number of training jobs, a key question is how to design efficient scheduling algorithms to allocate workers and parameter servers across different machines to minimize the overall training time. Toward this end, in this paper, we develop an online scheduling algorithm that jointly optimizes resource allocation and locality decisions. Our main contributions are three-fold: i) We develop a new analytical model that considers both resource allocation and locality;ii) Based on an equivalent reformulation and observations on the worker-parameter server locality configurations, we transform the problem into a mixed packing and covering integer program, which enables approximation algorithm design;iii) We propose a meticulously designed approximation algorithm based on randomized rounding and rigorously analyze its performance. Collectively, our results contribute to the state of the art of distributed ML system optimization and algorithm design.

关键词： Servers Training Optimization Scheduling algorithms Resource management approximation algorithms Heuristic algorithms Online resource scheduling distributed machine learning approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximating activation edge-cover and facility location problems

引用

THEORETICAL COMPUTER SCIENCE 2022年 930卷 218-228页

作者： Kortsarz, Guy Nutov, Zeev Shalom, Eli Rutgers State Univ Camden NJ USA Open Univ Israel Raanana Israel

What approximation ratio can we achieve for the FACILITY LOCATION problem if whenever a client u connects to a facility v, the opening cost of v is at most theta times the service cost of u? We show that this and many other problems are a particular case of the ACTIVATION EDGE-COVER problem. Here we are given a multigraph G = (V, E), a set R & SUBE;V of terminals, and thresholds {teu, tev} for each uv-edge e & ISIN;E. The goal is to find an assignment a = {av : v & ISIN;V } to the nodes minimizing Ev & ISIN;V av, such that the edge set Ea = {e = uv : au & GE;teu, av & GE;tev } activated by a covers R. We obtain ratio 1 +max1+x/theta & AP;ln theta -ln ln theta lnx x & GE;1 for the problem, where theta & LE;max max{tu,te u,tev} is a problem parameter. This result is based on v} e & ISIN;E min{te a simple generic algorithm for the problem of minimizing a sum of a decreasing and a sub-additive set functions, which is of independent interest. As an application, we get the same ratio for the above variant of FACILITY LOCATION. If for each facility all service costs 1+k/theta , where Hk = ?k Hk-1 i=1 1/i. For the are identical then we show a better ratio 1 + max k & ISIN;N MIN-POWER EDGE-COVER problem we improve the ratio 1.406 of [4] (achieved by iterative randomized rounding) to 1.2785. For unit thresholds we improve the ratio 73/60 & AP;1.217 of [4] to 1555 1347 & AP;1.155.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Generalized min-covering problem Activation edge-cover Facility location Minimum power approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Percolation centrality via Rademacher Complexity

引用

DISCRETE APPLIED MATHEMATICS 2022年 323卷 201-216页

作者： De Lima, Alane M. Da Silva, Murilo V. G. Vignatti, Andre L. Univ Fed Parana Dept Comp Sci Curitiba PR Brazil

In this work we investigate the problem of estimating the percolation centrality of all vertices in a weighted graph. The percolation centrality measure quantifies the importance of a vertex in a graph that is going through a contagious process. The fastest exact algorithm for the computation of this measure in a graph G with n vertices and m edges runs in O(n3). Let DiamV (G) be the maximum number of vertices in a shortest path in G. In this paper we present an expected O(m log n log DiamV (G)) time approximation algorithm for the estimation of the percolation centrality for all vertices of G. We show in our experimental analysis that in the case of real-world complex networks, the output produced by our algorithm returns approximations that are even closer to the exact values than its guarantee in terms of theoretical worst case analysis. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Percolation centrality approximation algorithm Pseudo-dimension Rademacher averages

来源：评论

学校读者我要写书评

暂无评论

Rescheduling problems with allowing for the unexpected new jobs arrival

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第3期43卷 630-645页

作者： Zhang, Xingong Lin, Win-Chin Wu, Chin-Chia Chongqing Normal Univ Coll Math Sci Chongqing Peoples R China Feng Chia Univ Dept Stat Taichung Taiwan

In modern manufacturing and services, rescheduling frequently happens in manufacturing practice, which a disruptionmay happen. In this paper, the rescheduling problem with the unexpected new jobs arrival is studied, and the effect of time disruptions is taken into account on a previously planned optimal schedule. Reschedulingmeans that a set of original jobs has already given jobs sequence by minimizing some classical objective, then a set of new jobs arrived will create a time disruption for the original jobs. Our focus is to find a feasible rescheduling to minimize maximum weighted tardiness costs under a limit of time disruptions from the original schedule. Two time disruption problemswill be involved: under an upper restriction of the total time disruption and relaxing time disruption restriction. For the former case, the proof of strongly NP-hard by reducing 3-Partition problem is presented. For latter case, a strongly NPhard proof is also given,and then a two-approximation polynomial time algorithm is presented to confirm that the latter problem has not an approximation polynomial-time algorithm, which a performance ratio is less than 2 unless P = NP. Finally, one of the proposed algorithms is improved by three local searches, respectively, as three seeds used in simulated annealing for approximate solution. Furthermore, we also present some extensive numerical experiment to evaluate their performance.

关键词： Rescheduling Time disruption approximation algorithm Simulated annealing

来源：评论

学校读者我要写书评

暂无评论

Enhancing 3-D Land Seismic Data Using Nonlinear Beamforming Based on the Efficiency-Improved Genetic algorithm

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2022年第5期26卷 1192-1199页

作者： Sun, Yimin Silvestrov, Ilya Bakulin, Andrey Aramco Overseas Co Aramco Res Ctr Delft NL-2628 ZD Delft Netherlands Saudi Aramco EXPEC Adv Res Ctr Dhahran 31311 Saudi Arabia

Seismic data acquired in a desert environment often have a low signal-to-noise ratio, posing a significant challenge to seismic processing, imaging, and inversion. Nonlinear beamforming is one effective method that uses local second-order mathematical operators to describe seismic events and then enhance them. However, estimating the operator coefficients from input data is a nonlinear and compute-intensive optimization problem. We propose a new method for this estimation based on a recently developed efficiency-improved genetic algorithm. We demonstrate that it delivers an excellent balance between improved data quality and computational efficiency. We also introduce a "spatial consistency" feature to further speed up the algorithm by using available nonlinear-beamforming operators as initial trial solutions for the neighboring data ensembles. These findings are supported by applying the new approach to land seismic datasets from the desert environment.

关键词： Receivers Three-dimensional displays Genetic algorithms Array signal processing Signal to noise ratio Signal processing algorithms Apertures approximation algorithm geophysical signal processing genetic algorithm (GA) seismic wave signal restoration

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：