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

approximation algorithms for k-level stochastic facility location problems

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第1期34卷 266-278页

作者： Melo, Lucas P. Miyazawa, Flavio K. Pedrosa, Lehilton L. C. Schouery, Rafael C. S. Univ Estadual Campinas Inst Comp Campinas SP Brazil

In the k-level facility location problem (FLP), we are given a set of facilities, each associated with one of k levels, and a set of clients. We have to connect each client to a chain of opened facilities spanning all levels, minimizing the sum of opening and connection costs. This paper considers the k-level stochastic FLP, with two stages, when the set of clients is only known in the second stage. There is a set of scenarios, each occurring with a given probability. A facility may be opened in any stage, however, the cost of opening a facility in the second stage depends on the realized scenario. The objective is to minimize the expected total cost. For the stage-constrained variant, when clients must be served by facilities opened in the same stage, we present a -approximation, improving on the 4-approximation by Wang et al. (Oper Res Lett 39(2):160-161, 2011) for each k. In the case with , the algorithm achieves factors 2.56 and 2.78, resp., which improves the -approximation for by Wu et al. (Theor Comput Sci 562:213-226, 2015). For the non-stage-constrained version, we give the first approximation for the problem, achieving a factor of 3.495 for the case with , and in general.

关键词： approximation algorithm Multilevel facility location problem Stochastic problem

来源：评论

学校读者我要写书评

暂无评论

On approximability of minimum color-spanning ball in high dimensions

引用

DISCRETE APPLIED MATHEMATICS 2020年 279卷 188-191页

作者： Kazemi, Mohammad Reza Mohades, Ali Khanteimouri, Payam Amirkabir Univ Technol Tehran Polytech Tehran Iran Alzahra Univ Fac Math Sci Dept Comp Sci Tehran Iran

This paper presents a lower bound on the running time of any approximation scheme for Minimum Color-Spanning Ball (MCSB) problem in high dimensional spaces. This bound is based on the Exponential Time Hypothesis (ETH)... 详细信息

关键词： approximation algorithm Approximability Color-spanning set High dimensional spaces Exponential Time Hypothesis (ETH)

来源：评论

学校读者我要写书评

暂无评论

Influence Maximization with Priority in Online Social Networks

引用

algorithmS 2020年第8期13卷 183页

作者： Pham, Canh V. Ha, Dung K. T. Vu, Quang C. Su, Anh N. Hoang, Huan X. Peoples Secur Acad Fac Informat & Secur Technol Hanoi 100000 Vietnam Vietnam Natl Univ Hanoi 100000 Vietnam

The Influence Maximization (IM) problem, which finds a set ofknodes (calledseedset) in a social network to initiate the influence spread so that the number of influenced nodes after propagation process is maximized, is an important problem in information propagation and social network analysis. However, previous studies ignored the constraint of priority that led to inefficient seed collections. In some real situations, companies or organizations often prioritize influencing potential users during their influence diffusion campaigns. With a new approach to these existing works, we propose a new problem calledInfluence Maximization with Priority(IMP) which finds out a set seed ofknodes in a social network to be able to influence the largest number of nodes subject to the influence spread to a specific set of nodesU(calledpriority set) at least a given thresholdTin this paper. We show that the problem is NP-hard under well-knownICmodel. To find the solution, we propose two efficient algorithms, calledIntegrated Greedy(IG) andIntegrated Greedy Sampling(IGS) with provable theoretical guarantees. IG provides a(1 - (1 - 1/k)(t))-approximation solution with t is an outcome of algorithm and t >= 1. The worst-case approximation ratio is obtained when t = 1 and it is equal to 1/k. In addition, IGS is an efficient randomized approximation algorithm based on sampling method that provides a(1 - (1 - 1/k)(t) - epsilon)-approximation solution with probability at least 1 - delta with epsilon > 0, delta is an element of(0,1) as input parameters of the problem. We conduct extensive experiments on various real networks to compare our IGS algorithm to the state-of-the-art algorithms in IM problem. The results indicate that our algorithm provides better solutions interns of influence on the priority sets when approximately give twice to ten times higher than threshold T while running time, memory usage and the influence spread also give considerable results compared to the others.

关键词： social networks influence maximization with priority optimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for nonnegative polynomial optimization problems over unit spheres

引用

Frontiers of Mathematics in China 2017年第6期12卷 1409-1426页

作者： Xinzhen ZHANG Guanglu ZHOU Louis CACCETTA Mohammed ALQAHTANI School of Mathematics Tianjin University Tianjin 300072 China Department of Mathematics and Statistics Curtin University Perth Australia

We consider approximation algorithms for nonnegative polynomial optimization problems over unit spheres. These optimization problems have wide applications e.g., in signal and image processing, high order statistics, and computer vision. Since these problems are NP-hard, we are interested in studying on approximation algorithms. In particular, we propose some polynomial-time approximation algorithms with new approximation bounds. In addition, based on these approximation algorithms, some efficient algorithms are presented and numerical results are reported to show the efficiency of our proposed algorithms.

关键词： approximation algorithm polynomial optimization approximationbound

来源：评论

学校读者我要写书评

暂无评论

Constrained k-Center Problem on a Convex Polygon

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2020年第2期31卷 275-291页

作者： Basappa, Manjanna Jallu, Ramesh K. Das, Gautam K. Indian Inst Informat Technol Dharwad Comp Sci & Engn IT PkOpp Glass House Hubli 580029 Karnataka India Indian Stat Inst Adv Comp & Microelect Unit Kolkata 700108 W Bengal India Indian Inst Technol Guwahati Dept Math Gauhati 781039 India IIT Guwahati Gauhati India

In this paper, we consider a restricted covering problem, in which a convex polygon P with n vertices and an integer k are given, the objective is to cover the entire region of P using k congruent disks of minimum radius r(opt), centered on the boundary of P. For k >= 7 and any epsilon > 0, we propose an (1 + 7/k + 7 epsilon/k + epsilon)-factor approximation algorithm for this problem, which runs in O((n + k)(vertical bar log r(opt)vertical bar + log inverted right perpendicular 1/epsilon inverted left perpendicular)) time. The best known approximation factor of the algorithm for the problem in the literature is 1.8841 [H. Du and Y. Xu: An approximation algorithm for k-center problem on a convex polygon, J. Comb. Optim. 27(3) (2014) 504-518].

关键词： approximation algorithm convex polygon cover geometric disk cover

来源：评论

学校读者我要写书评

暂无评论

Tractable Compensation Plan under Asymmetric Information

引用

PRODUCTION AND OPERATIONS MANAGEMENT 2020年第5期29卷 1212-1218页

作者： Yang, Ruina Mai, Yinhua Lee, Chung-Yee Teo, Chung-Piaw Xi An Jiao Tong Univ Sch Management Xian 710049 Peoples R China Tsinghua Univ Grad Sch Shenzhen Shenzhen Logist Engn & Simulat Lab Beijing 518055 Peoples R China Hong Kong Univ Sci & Technol Clear Water Bay Hong Kong Peoples R China Natl Univ Singapore Inst Operat Res & Analyt Singapore 119077 Singapore

In an elegant study on salesforce incentive design, Steenburgh and Ahearne (2012) have argued that a multi-faceted portfolio approach, based on the classification of workers into laggards, core, and star performers, can induce better result from the salesforce, compared to traditional approaches used in companies. In this paper, we construct a portfolio of incentive contracts with a three-piece "linear-quadratic-linear" structure and study their incentive effects. It is well known that such contracts can extract 100% of the incremental benefits (i.e., optimal) when the performance levels of the agents are exponentially or uniformly distributed, but its effect is still unknown in the more natural case when performance levels are normally distributed. We show that the proposed three-piece contract can capture more than 95.32% of the incremental benefits, obtained from the optimal incentive contract over fixed salary contract, when the cost functions of efforts are quadratic, and the performance levels are normally distributed. In this case, the more traditional three-piece linear contract has a corresponding tight lower bound of 82.64%. Interestingly this is the same as the tight lower bound from a two-piece linear contract, and thus adding more linear pieces to the contract does not help to improve the lower bound when the performance levels follow the normal distributions. This provides a partial theoretical explanation for the superiority of the portfolio approach advocated by Steenburgh and Ahearne (2012).

关键词： incentive contract approximation algorithm salesforce management principal-agent model

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Cell Planning in Heterogeneous Networks

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2017年第2期66卷 1561-1572页

作者： Zhao, Wentao Wang, Shaowei Wang, Chonggang Wu, Xiaobing Nanjing Univ Sch Elect Sci & Engn Nanjing 210023 Jiangsu Peoples R China Southeast Univ Natl Mobile Commun Res Lab Nanjing 210096 Jiangsu Peoples R China InterDigital Commun King Of Prussia PA 19406 USA Univ Canterbury Wireless Res Ctr Christchurch 8140 New Zealand

Small cells are introduced to cellular systems to enhance coverage and improve capacity. Densely deploying small cells can not only offload the traffic of macrocells but also provide an energy-and cost-efficient way to meet the sharp increase in traffic demands in mobile networks. However, such a cell deployment paradigm also leads to heterogeneous network (HetNet) infrastructure and raises new challenges for cell planning. In this paper, we study the cell planning issue in the HetNet. Our optimization task is to select a subset of candidate sites to deploymacro or small cells to minimize the total cost of ownership (TCO) or the energy consumption of the cellular system while satisfying practical constraints. We introduce approximation algorithms to cope with two different cell-planning cases, which are both NP-hard. First, we discuss the macrocell-only case. Our proposed algorithm achieves an approximation ratio of O(log R) in this scenario, where R is the maximum achievable capacity of macrocells. Then, we introduce an O(log (R) over tilde)-approximation algorithm to the small-cell scenario, where (R) over tilde is the maximum achievable capacity of a macrocell with small cells overlaid on it. Numerical results indicate that the HetNet can significantly reduce the TCO and the energy consumption of the cellular system.

关键词： approximation algorithm cell planning heterogeneous network (HetNet)

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions

引用

DISCRETE APPLIED MATHEMATICS 2017年 230卷 56-70页

作者： Elbassioni, Khaled Trung Thanh Nguyen Khalifa Univ Sci & Technol Masdar Inst POB 54224 Abu Dhabi U Arab Emirates New York Univ Abu Dhabi POB 129188 Abu Dhabi U Arab Emirates

The aim of this paper is to study approximation algorithms for a class of binary packing problems with quadratic constraints, where the constraint matrices are completely positive and have low cp-rank. We show that limiting the cp-rank makes the quadratic optimization problem exhibit similar approximability behavior as the linear case, assuming a constant number of quadratic constrains. We first show a convex programming-based method that yields a polynomial-time approximation scheme (PTAS) for the problem with linear objective functions. For non-linear objective functions, we follow a geometry-based approach to design approximation algorithms for a class of functions fulfilling certain conditions. Particularly, we obtain a (1/e - is an element of)-approximation algorithm for submodular objective functions, for any is an element of > 0, and a PTAS for quadratic objective functions where the underlying matrix has fixed nonnegative rank. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Binary packing Quadratic constraint approximation algorithm Completely positive rank Nonnegative rank Submodular

来源：评论

学校读者我要写书评

暂无评论

A 2-approximation Scheme for Sorting Signed Permutations by Reversals, Transpositions, Transreversals, and Block-Interchanges

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2019年第5期16卷 1702-1711页

作者： Hao, FanChang Zhang, Melvin Leong, Hon Wai Shandong Univ Polit Sci & Law Sch Informat & Evidence Forens Lab Univ Shandong Jinan 250014 Shandong Peoples R China Cosmiqo Int Pte Ltd Singapore 139951 Singapore Natl Univ Singapore Dept Comp Sci Singapore 117417 Singapore

We consider the problem of sorting signed permutations by reversals, transpositions, transreversals, and block-interchanges and give a 2-approximation scheme, called the GSB (Genome Sorting by Bridges) scheme. Our result extends 2-approximation algorithm of He and Chen [12] that allowed only reversals and block-interchanges, and also the 1.5 approximation algorithm of Hartman and Sharan [11] that allowed only transreversals and transpositions. We prove this result by introducing three bridge structures in the breakpoint graph, namely, the L-bridge, T-bridge, and X-bridge and show that they model "proper" reversals, transpositions, transreversals, and block-interchanges, respectively. We show that we can always find at least one of these three bridges in any breakpoint graph, thus giving an upper bound on the number of operations needed. We prove a lower bound on the distance and use it to show that GSB has a 2-approximation ratio. An ${\text{O(n}}<^>approximation)$O(n3) algorithm called GSB-I that is based on the GSB approximation scheme presented in this paper has recently been published by Yu, Hao, and Leong in [17] . We note that our 2-approximation scheme admits many possible implementations by varying the order we search for proper rearrangement operations.

关键词： Genomics Bioinformatics Sorting approximation algorithms Bridges Transforms Electronic mail Genome rearrangement genome sorting approximation algorithm reversal transreversal transposition block-interchange breakpoint graph bridge structures

来源：评论

学校读者我要写书评

暂无评论

Semidefinite approximation bound for a class of nonhomogeneous nonconvex quadratically constrained quadratic programming problem

引用

OPTIMIZATION LETTERS 2019年第4期13卷 837-845页

作者： Xu, Zi Tao, Siqi Lou, Kaiyao Shanghai Univ Dept Math Shanghai 200444 Peoples R China

In this paper, we consider a class of nonconvex nonhomogeneous quadratically constrained quadratic optimization problem. We derive some sufficient condition for the input data, and then establish a semi-definite approximation bound based on a randomization algorithm. The approximation bound is optimal in the order of m in general under the given restriction on the input data.

关键词： Quadratically constrained quadratic programming Semidefinite programming relaxation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：