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

Capacitated assortment and price optimization under the nested logit model

JOURNAL OF GLOBAL OPTIMIZATION 2020年第4期77卷 895-918页

作者： Chen, Rui Jiang, Hai Tsinghua Univ Dept Ind Engn Beijing 100084 Peoples R China

We study the capacitated assortment and price optimization problem, where a retailer sells categories of substitutable products subject to a capacity constraint. The goal of the retailer is to determine the subset of products as well as their selling prices so as to maximize the expected revenue. We model the customer purchase behavior using the nested logit model and formulate this problem as a non-linear binary integer program. For this NP-complete problem, we show that there exists a pseudo polynomial time approximation scheme that finds its epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon $$\end{document}-approximate solution. We first convert the original problem into an equivalent fixed point problem. We then show that finding an epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon $$\end{document}-approximate solution to the fixed point problem can be achieved by binary search, where a non-linear auxiliary problem is repeatedly approximated by a dynamic programing based algorithm involving an approximation to a series of multiple-choice parametric knapsack problems. For the special case when the capacity constraints are cardinal and nest-specific, we develop an algorithm that finds the optimal solution in strongly polynomial time. Moreover, our algorithm can be directly applied to find an epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon $$\end{document}-approximate solution to the ca

关键词： Assortment optimization Nested logit model approximate algorithm Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Addressing the Most Reliable Edge-Disjoint Paths With a Delay Constraint

引用

IEEE TRANSACTIONS ON RELIABILITY 2011年第1期60卷 88-93页

作者： Loh, Ruen Chze Soh, Sieteng Lazarescu, Mihai Curtin Univ Technol Dept Comp Perth WA 6845 Australia

Recently, multipath solutions have been proposed to improve the quality-of-service of the source to destination (s, t)-path in communication networks (CNs). This paper describes the lambda DP/DR problem to obtain lambda >= 1 edge-disjoint (s, t)-paths (lambda DP) such that its reliability is maximized while keeping its delay no longer than a delay constraint D >= 1. This problem is NP-hard, and thus this paper proposes an approximate solution using Lagrange-relaxation. Our algorithm generates lambda DP with delta(lambda DP) <= D, and reliability bounded by vertical bar Log(R(min))vertical bar <= vertical bar log(rho(lambda DP))vertical bar <= (1 + k)*vertical bar log(R(min))vertical bar, where R(min) is the minimum reliability of any (s, t)-path in the CN, and k >= 1. Our simulations on forty random CNs and large grid networks show that our solution produces lambda DP with delay and reliability comparable to those obtained by the optimal but exponential time algorithm.

关键词： approximate algorithm lagrange-relaxation multi-constrained edge-disjoint paths network delay network reliability

来源：评论

学校读者我要写书评

暂无评论

Simulated annealing for higher dimensional projection depth

引用

COMPUTATIONAL STATISTICS & DATA ANALYSIS 2012年第12期56卷 4026-4036页

作者： Shao, Wei Zuo, Yijun Michigan State Univ Dept Stat & Probabil E Lansing MI 48824 USA Shandong Univ Sch Math Jinan 250100 Peoples R China

Data depth for multivariate data has received considerable attention in multivariate nonparametric analysis and robust statistics. Nevertheless, the computation of data depth such as projection depth has remained as a very challenging problem which hinders the development of the projection depth and its wide use in practice. Especially in high dimension, there is no efficient algorithm for the computation of the projection depth and its induced estimators (including the Stahel-Donoho estimator as a special case). In this paper, we employ simulated annealing algorithm by invoking Markov Chain Monte Carlo technique to compute the projection depth. Simulation results show that this new approximate method performs significantly better than its competitors. In lower dimension, we are able to show that the approximate results from this algorithm are very close to the exact ones. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Projection depth approximate algorithm Simulated annealing Markov Chain Monte Carlo

来源：评论

学校读者我要写书评

暂无评论

Stock cutting of complicated designs by computing minimal nested polygons

引用

ENGINEERING OPTIMIZATION 1995年第3期25卷 165-178页

作者： Bhadury, J Chandrasekaran, R UNIV TEXAS SCH MANAGEMENTMS JO 47RICHARDSONTX 75083

This paper studies the following problem in stock cutting: when it is required to cut out complicated designs from parent material, it is cumbersome to cut out the exact design or shape, especially if the cutting process involves optimization. In such cases, it is desired that, as a first step, the machine cut out a relatively simpler approximation of the original design, in order to facilitate the optimization techniques that are then used to cut out the actual design. This paper studies this problem of approximating complicated designs or shapes. The problem is defined formally first and then it is shown that this problem is equivalent to the Minimal Nested Polygon problem in geometry. Some properties of the problem are then shown and it is demonstrated that the problem is related to the Minimal Turns Path problem in geometry. With these results, an efficient approximate algorithm is obtained for the original stock cutting problem. Numerical examples are provided to illustrate the working of the algorithm in different cases.

关键词： stock cutting design approximation minimal nested polygon approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Influential facilities placement over moving objects

引用

DISTRIBUTED AND PARALLEL DATABASES 2021年第3期39卷 607-636页

作者： Zhou, Ying Li, Hui Li, Dan Wang, Meng Cui, Jiangtao Xidian Univ State Key Lab Integrated Serv Networks Xian Peoples R China Xidian Univ Sch Cyber Engn Xian Peoples R China Xian Polytech Univ Sch Comp Sci Xian Peoples R China Xidian Univ Sch Comp Sci & Technol Xian Peoples R China

In this paper we propose and study the problem ofk-Collective influential facility placement over moving object. Specifically, given a set of candidate locations, a group of moving objects, each of which is associated with a collection of reference points, as well as a budgetk, we aim to mine a group ofklocations, the combination of whom can influence the most number of moving objects. We show that this problem is NP-hard and present a basic hill-climb algorithm, namely GreedyP. We prove this method with(1-1/e) approximation ratio. One core challenge is to identify and reduce the overlap of the influence from different selected locations to maximize the marginal benefits. Therefore, the GreedyP approach may be very costly when the number of moving objects is large. In order to address the problem, we also propose another GreedyPS algorithm based on FM-sketch technique, which maps the moving objects to bitmaps such that the marginal benefit can be easily observed through bit-wise operations. Through this way, we are able to save more than a half running time while preserving the result quality. We further present a pair of extensions to the problem, namelyk-Additional andk-Eliminative Influential Facility Placement problems. We also present corresponding approximate solutions towards both extensions and theoretically show that results of both algorithms are guaranteed. Experiments on real datasets verify the efficiency and effectiveness for all these algorithms comparing with baselines.

关键词： Moving objects Location selection Submodular approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Vehicle scheduling on a tree with release and handling times

引用

ANNALS OF OPERATIONS RESEARCH 1997年第s期69卷 193-207页

作者： Karuno, Y Nagamochi, H Ibaraki, T KYOTO INST TECHNOL DEPT MECH & SYST ENGNSAKYO KUFAC ENGN & DESIGNKYOTO 606JAPAN KYOTO UNIV DEPT APPL MATH & PHYSGRAD SCH ENGNSAKYO KUKYOTO 606JAPAN

In this paper, we consider a single-vehicle scheduling problem on a tree-shaped road network. Let T = (V, E) be a tree, where V is a set of n vertices and E is a set of edges. A task is located at each vertex v, which is also denoted as v. Each task v has release time r(v) and handling time h(v). The travel times c(u, v) and c(v, u) are associated with each edge (u, v) is an element of E. The vehicle starts from an initial vertex v(0) is an element of V, visits all tasks v is an element of V for their processing, and returns to v(0). The objective is to find a routing schedule of the vehicle that minimizes the completion time, denoted as C (i.e., the time to return to v(0) after processing all tasks). We call this problem TREE-VSP(C). We first prove that TREE-VSP(C) is NP-hard. However, we then show that TREE-VSP(C) with a depth-first routing constraint can be exactly solved in O(n log n) time. Moreover, we show that, if this exact algorithm is used as an approximate algorithm for the original TREE-VSP(C), its worst-case performance ratio is at most two.

关键词： vehicle scheduling tree-shaped network NP-hard approximate algorithm worst-case analysis

来源：评论

学校读者我要写书评

暂无评论

Quadratic Matrix Inequality Approach to Robust Adaptive Beamforming for General-Rank Signal Model

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2020年 68卷 2244-2255页

作者： Huang, Yongwei Vorobyov, Sergiy A. Luo, Zhi-Quan Guangdong Univ Technol Sch Informat Engn Guangzhou 510006 Guangdong Peoples R China Aalto Univ Sch Elect Engn Dept Signal Proc & Acoust Espoo 02150 Finland Chinese Univ Hong Kong Shenzhen Res Inst Big Data Shenzhen Peoples R China

The worst-case robust adaptive beamforming problem for general-rank signal model is considered. This is a nonconvex problem, and an approximate version of it (obtained by introducing a matrix decomposition on the presumed covariance matrix of the desired signal) has been well studied in the literature. Different from the existing literature, herein however the original beamforming problem is tackled. Resorting to the strong duality of linear conic programming, the robust adaptive beamforming problem for general-rank signal model is reformulated into an equivalent quadratic matrix inequality (QMI) problem. By employing a linear matrix inequality (LMI) relaxation technique, the QMI problem is turned into a convex semidefinite programming problem. Using the fact that there is often a positive gap between the QMI problem and its LMI relaxation, an approximation algorithm is proposed to solve the robust adaptive beamforming in the QMI form. Besides, several sufficient optimality conditions for the nonconvex QMI problem are developed To validate our results, simulation examples are presented, which demonstrate the improved performance of the new robust beamformer in terms of the output signal-to-interference-plus-noise ratio.

关键词： Robust adaptive beamforming general-rank signal model quadratic matrix inequality (QMI) problem linear matrix inequality (LMI) relaxation approximate algorithm global optimality condition

来源：评论

学校读者我要写书评

暂无评论

Optimal and Greedy algorithms for the One-Dimensional RSU Deployment Problem With New Model

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2018年第8期67卷 7643-7657页

作者： Gao, Zhenguo Chen, Danjie Cai, Shaobin Wu, Hsiao-Chun Huaqiao Univ Coll Comp Sci & Technol Xiamen 361021 Peoples R China Huaqiao Univ Coll Civil Engn Xiamen 361021 Peoples R China Louisiana State Univ Sch Elect Engn & Comp Sci Baton Rouge LA 70803 USA

Optimal road side unit (RSU) deployment is of crucial importance to vehicular ad hoc networks. The RSU deployment (RD) problem models in the literature usually lack the ability to describe curve-shaped roads and roads nonuniform statistics. We had proposed a more realistic RD problem model taking these features into consideration. However, our understanding of the RD problem with the new model is still seriously limited. In this paper, we try to deepen our understanding of the one-dimensional RD (D1RD) problem with the new model by analyzing its properties and designing optimal and efficient approximate algorithms for it. We first analyze the properties of optimal solutions of the D1RD problem. Next, suspecting that the D1RD problem with n RSUs of different coverage radii is intractable, we propose two greedy-based algorithms (named as Greedy2P3 and Greedy2P3E) and show that Greedy2P3E's approximation ratio is at least 1 - (n-1/n)(2). Then, by exploiting the properties of the D1RD problem, we propose an optimal algorithm named OptGreDyn by combining greedy idea and dynamic programming, and prove its optimality. At last, we proved that, if applied to the RD problem with n RSUs of identical radii, the approximation ratios of Greedy2P3 and Greedy2P3E are at least 2 3, and it is tight for Greedy2P3 when n = 3i, where i is a positive integer. Simulation results verify the optimality of OptGreDyn, meanwhile show that Greedy2P3 and Greedy2P3E usually return near-optimal solutions with profit more than 98% of the optimal solutions, and they are preferable than the existing approximate algorithms.

关键词： One-dimensional road side unit (RSU) deployment problem optimal algorithm approximate algorithm approximation ratio vehicular ad hoc networks (VANETs)

来源：评论

学校读者我要写书评

暂无评论

Circular shortest path in images

引用

PATTERN RECOGNITION 2003年第3期36卷 709-719页

作者： Sun, CM Pallottino, S CSIRO Math & Informat Sci N Ryde NSW 1670 Australia Univ Pisa Dipartimento Informat I-56125 Pisa Italy

Shortest path algorithms have been used in a number of applications such as crack detection, road or linear feature extraction in images. There are applications where the starting and ending positions of the shortest path need to be constrained. In this paper, we present several new algorithms for the extraction of a circular shortest path in an image such that the starting and ending positions coincide. The new algorithms we developed include multiple search algorithm, image patching algorithm, multiple backtracking algorithm, the combination of image patching and multiple back-tracking algorithm, and approximate algorithm. The typical running time of our circular shortest path extraction algorithm on a 256 x 256 image is about 0.3 s on a rather slow 85 MHz Sun SPARC computer. A variety of real images for crack detection in borehole data and object boundary extraction have been tested and good results have been obtained. (C) 2002 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.

关键词： circular shortest path dynamic programming multiple search algorithm image patching algorithm multiple backtracking algorithm combination algorithm approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast density clustering strategies based on the k-means algorithm

引用

PATTERN RECOGNITION 2017年 71卷 375-386页

作者： Bai, Liang Cheng, Xueqi Liang, Jiye Shen, Huawei Guo, Yike Shanxi Univ Sch Comp & Informat Technol Taiyuan 030006 Shanxi Peoples R China Chinese Acad Sci Inst Comp Technol Beijing 100190 Peoples R China Imperial Coll London Dept Comp SW7 London England

Clustering by fast search and find of density peaks (CFSFDP) is a state-of-the-art density-based clustering algorithm that can effectively find clusters with arbitrary shapes. However, it requires to calculate the distances between all the points in a data set to determine the density and separation of each point. Consequently, its computational cost is extremely high in the case of large-scale data sets. In this study, we investigate the application of the k-means algorithm, which is a fast clustering technique, to enhance the scalability of the CFSFDP algorithm while maintaining its clustering results as far as possible. Toward this end, we propose two strategies. First, based on concept approximation, an acceleration algorithm (CFSFDP+A) involving fewer distance calculations is proposed to obtain the same clustering results as those of the original algorithm. Second, to further expand the scalability of the original algorithm, an approximate algorithm (CFSFDP+DE) based on exemplar clustering is proposed to rapidly obtain approximate clustering results of the original algorithm. Finally, experiments are conducted to illustrate the effectiveness and scalability of the proposed algorithms on several synthetic and real data sets. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Cluster analysis Density-based clustering Acceleration mechanism approximate algorithm k-means

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：