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

Approximate and exact algorithms for an energy minimization traveling salesman problem

JOURNAL OF CLEANER PRODUCTION 2020年 249卷 119433-000页

作者： Wang, Shijin Liu, Ming Chu, Feng Tongji Univ Sch Econ & Management Shanghai 200092 Peoples R China Univ Paris Saclay Univ Evry Lab IBISC F-91025 Evry France Fuzhou Univ Sch Econ & Management Fuzhou 350116 Peoples R China

Energy saving is a great challenge for clean transportation. In this paper, we study the Energy Minimization Traveling Salesman Problem (EMTSP), which is a generation of the classical Traveling Salesman Problem (TSP), and an important theoretical basis and a special case of the Energy Minimization Vehicle Routing Problem ( EMVRP). The objective of the studied problem is to minimize the sum of the product of load (including curb weight of the vehicle) and traveled distances. An approximation algorithm based on the Christofides's Heuristic is proposed and its worst-case ratio bound is proven. A branch and bound (B&B) algorithm integrated with a fast 1-tree based lower bound is developed to obtain optimal solutions. The results of computational experiments show the efficiency and the effectiveness of the B&B algorithm, as well as the heuristic methods. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Energy minimization Branch and bound approximation algorithm Christofides's heuristic Traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

algorithmic aspects of secure domination in unit disk graphs

引用

INFORMATION AND COMPUTATION 2023年第PartB期295卷

作者： Wang, Cai-Xia Yang, Yu Xu, Shou-Jun Lanzhou Univ Gansu Ctr Appl Math Sch Math & Stat Lanzhou 730000 Gansu Peoples R China

Given a graph G with vertex set V, a set S subset of V is a secure dominating set of G if S is a dominating set of G and if for every vertex u is an element of V \ S, there exists a vertex v is an element of S adjacent to u such that (S boolean OR {u}) \ {v} is a dominating set of *** minimum secure dominating set (or, for short, MSDS) problem asks to find an MSDS in a given graph. In this paper, we first show that the decision version of the MSDS problem is NP-complete in unit disk graphs, even in grid graphs. Secondly, we give an O(n + m) time t-approximation algorithm for the MSDS problem in several geometric intersection graphs which are K1,t-free for some integer t >= 3. Finally, we propose a PTAS for the MSDS problem in unit disk graphs.(c) 2023 Elsevier Inc. All rights reserved.

关键词： Secure domination Unit disk graph NP-complete approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

2-node-connectivity network design

引用

THEORETICAL COMPUTER SCIENCE 2024年 987卷

作者： Nutov, Zeev Open Univ Israel Raanana Israel

We consider 2-connectivity network design problems in which we are given a graph and seek a min-size 2-connected subgraph that satisfies a prescribed property. center dot In the 1-CONNECTIVITY AUGMENTATION problem the goal is to augment a connected graph by a minimum size edge subset of a specified edge set such that the augmented graph is 2-connected. We breach the natural approximation ratio 2 for this problem, and also for the more general CROSSING FAMILY COVER problem. center dot In the 2-CONNECTED DOMINATING SET problem, we seek a minimum size 2-connected subgraph that dominates all nodes. We give the first non-trivial approximation algorithm with expected approximation ratio ()(sigma(n) center dot log3 n), where sigma(n) = ()(logn center dot log log n center dot (log log log n)3). The unifying technique of both results is a reduction to the SUBSET STEINER CONNECTED DOMINATING SET problem. Such a reduction was known for edge-connectivity, and we extend it to 2-node connectivity problems. We show that the same method can be used to obtain easily polylogarithmic approximation ratios that are not too far from the best known ones for several other problems.

关键词： 2-connectivity Dominating set approximation algorithm Symmetric crossing family

来源：评论

学校读者我要写书评

暂无评论

Submodular Maximization Subject to a Knapsack Constraint Under Noise Models

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2022年第6期39卷 2250013-2250013页

作者： Ha, Dung T. K. Pham, Canh, V Hoang, Huan X. Univ Engn & Technol Vietnam Natl Univ Fac Informat Technol 144 Xuan Thuy St Hanoi 10000 Vietnam Phenikaa Univ Fac Comp Sci ORLab Yen Nghia Ward Hanoi 12116 Vietnam

The field of Submodular Maximization subject to a Knapsack constraint has recently expanded to a variety of application domains, which is facing some challenges such as data explosions or additional conditions. There exist plenty of objective functions that cannot be evaluated exactly in many real cases unless they are estimated with errors. It leads to solving the problem under noise models. Somewhat surprisingly, Submodular Maximization subject to a Knapsack constraint under Noise models (SMKN) has never been discussed a lot before. Hence, in this paper, we consider the problem with two kinds of noise models which are addition and multiplication. Inspired by the traditional Greedy algorithm, we first propose a Greedy algorithm under Noises with provable theoretical bounds. In order to find the solution when input data are extremely large, we then devise an efficient streaming algorithm that scans only a single pass over the data and guarantees theoretical approximations. Finally, we conduct some experiments on Influence Maximization problem under knapsack constraint, an instance of SMKN to show the performances of the proposed algorithms.

关键词： Submodular knapsack constraint approximation algorithm noises

来源：评论

学校读者我要写书评

暂无评论

Optimizing incremental SDN upgrades for load balancing in ISP networks

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期962卷

作者： Cheng, Yunlong Zhou, Hao Gao, Xiaofeng Zheng, Jiaqi Chen, Guihai Shanghai Jiao Tong Univ Dept Comp Sci & Engn MoE Key Lab Artificial Intelligence Shanghai 200240 Peoples R China Meituan Beijing 100102 Peoples R China Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Peoples R China

Software defined network (SDN) can dynamically and timely reply to the changes of network states, thus enabling advance traffic engineering mechanisms. To enhance the management ability of the network, Internet Service Providers (ISPs) are upgrading traditional network devices to SDN devices incrementally. In this paper, we study the k-LB problem, i.e., upgrading at most k legacy switches to SDN switches to achieve load balance. We prove that k-LB problem is NP-hard and there is no polynomial time (N + M)(1-epsilon) - approximation algorithm for any constant epsilon > 0 unless P = NP, where N(M) is the number of switches (links) in the network. Nevertheless, we propose an effective greedy algorithm and prove that it reaches an approximation guarantee of c(avg)/c(min) M, where c(avg)(c(min)) is the average (minimum) link capacity. Furthermore, we show that the greedy algorithm touches the tight lower bound of approximation ratio by extending the inapproximability result. The simulation results from large-scale ISP network topologies illustrate the effectiveness of our algorithm and show that the maximum link utilization can be decreased by 30% on average compared with the SOTA. (c) 2023 Elsevier B.V. All rights reserved.

关键词： SDN Incremental deployment Load balance approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Static Pricing: Universal Guarantees for Reusable Resources

引用

OPERATIONS RESEARCH 2022年第2期70卷 1143-1152页

作者： Besbes, Omar Elmachtoub, N. Adam Sun, Yunjie Columbia Business Sch New York NY 10027 USA Columbia Univ Department Ind Engn & Operat Res New York NY 10027 USA Columbia Univ Data Sci Inst New York NY 10027 USA Columbia Univ Dept Ind Engn & Operat Res New York NY 10027 USA

We consider a fundamental pricing model in which a fixed number of units of a reusable resource are used to serve customers. Customers arrive to the system according to a stochastic process and, upon arrival, decide whether to purchase the service, depending on their willingness to pay and the current price. The service time during which the resource is used by the customer is stochastic, and the firm may incur a service cost. This model represents various markets for reusable resources, such as cloud computing, shared vehicles, rotable parts, and hotel rooms. In the present paper, we analyze this pricing problem when the firm attempts to maximize a weighted combination of three central metrics: profit, market share, and service level. Under Poisson arrivals, exponential service times, and standard assumptions on the willingness-to-pay distribution, we establish a series of results that characterize the performance of static pricing in such environments. In particular, although an optimal policy is fully dynamic in such a context, we prove that a static pricing policy simultaneously guarantees 78.9% of the profit, market share, and service level from the optimal policy. Notably, this result holds for any service rate and number of units the firm operates. Our proof technique relies on a judicious construction of a static price that is derived directly from the optimal dynamic pricing policy. In the special case in which there are two units and the induced demand is linear, we also prove that the static policy guarantees 95.5% of the profit from the optimal policy. Our numerical findings on a large test bed of instances suggest that the latter result is quite indicative of the profit obtained by the static pricing policy across all parameters.

关键词： reusable resources dynamic pricing static pricing approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On the Minimum Common Integer Partition Problem

引用

ACM TRANSACTIONS ON algorithmS 2008年第1期5卷 1-18页

作者： Chen, Xin Liu, Lan Liu, Zheng Jiang, Tao Google Inc Search Qual Dept Mountain View CA USA Nanyang Technol Univ Sch Phys & Math Sci Singapore Singapore Univ Calif Riverside Dept Comp Sci & Engn Riverside CA 92521 USA

We introduce a new combinatorial optimization problem in this article, called the minimum common integer partition (MCIP) problem, which was inspired by computational biology applications including ortholog assignment and DNA fingerprint assembly. A partition of a positive integer n is a multiset of positive integers that add up to exactly n, and an integer partition of a multiset S of integers is defined as the multiset union of partitions of integers in S. Given a sequence of multisets S-1, S-2, ... , S-k of integers, where k >= 2, we say that a multiset is a common integer partition if it is an integer partition of every multiset S-i, 1 <= i <= k. The MCIP problem is thus defined as to find a common integer partition of S-1, S-2, ... , S-k with the minimum cardinality, denoted as MCIP(S-1, S-2, ... , S-k). It is easy to see that the MCIP problem is NP-hard, since it generalizes the well-known subset sum problem. We can in fact show that it is APX-hard. We will also present a 5/4-approximation algorithm for the MCIP problem when k = 2, and a 3k(k-1)/3k-2-approximation algorithm for k >= 3.

关键词： Subset sum integer partition NP-hard approximation algorithm computational biology combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Approximated vertex cover for graphs with perfect matchings

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2006年第8期E89D卷 2405-2410页

作者： Imamura, Tomokazu Iwama, Kazuo Tsukiji, Tatsuie Kyoto Univ Sch Informat Kyoto 6068501 Japan Tokyo Denki Univ Dept Informat Sci Saitama 3500394 Japan

Chen and Kanj considered the VERTEX COVER problem for graphs with perfect matchings (VC-PM). They showed that: (i) There is a reduction from general VERTEX COVER to VC-PM, which guarantees that if one can achieve an approximation factor of less than two for VC-PM, then one can do so for general VERTEX COVER as well. (ii) There is an algorithm for VC-PM whose approximation factor is given as 1.069 + 0.069d where (d)over bar is the average degree of the given graph. In this paper we improve (ii). Namely we give a new VC-PM algorithm which greatly outperforms the above one and its approximation factor is roughly 2-6.74/d+6.28. Our algorithm also works for graphs with "large" matchings, although its approximation factor is degenerated.

关键词： approximation algorithm vertex cover perfect matching MAX-2SAT

来源：评论

学校读者我要写书评

暂无评论

A Faster FPTAS for a Supply Chain Scheduling Problem to Minimize Holding Costs with Outsourcing

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2016年第5期33卷 1650039-1650039页

作者： Liu, Shang-Chia Wu, Chin-Chia Fu Jen Catholic Univ Dept Business Adm New Taipei Taiwan Feng Chia Univ Dept Stat Taichung Taiwan

This paper addresses a scheduling problem in a flexible supply chain where the jobs can be either processed in house, or outsourced to a third-party supplier with the goal of minimizing the sum of holding and delivery costs subject to an upper bound on the outsourcing cost. The problem with identical job processing times has been proved as binary NP-hard one and a fully polynomial time approximation scheme (FPTAS) that runs in O(n(8)/epsilon(2)) time has also been given. The aim of this paper is to derive a more effective FPTAS running in O(n(4) log n log max{n, 1/epsilon}/epsilon(2)) time for this problem.

关键词： Supply chain scheduling outsourcing inventory control FPTAS approximation algorithm shortest path problem

来源：评论

学校读者我要写书评

暂无评论

On scheduling multiple parallel two-stage flowshops with Johnson's Rule

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2024年第2期47卷 12-12页

作者： Wu, Guangwei Zuo, Fu Shi, Feng Wang, Jianxin Cent South Univ Forestry & Technol Coll Comp & Informat Engn Changsha 410004 Peoples R China Cent South Univ Sch Comp Sci & Engn Changsha 410083 Peoples R China Xiangjiang Lab Changsha 410205 Peoples R China

It is well-known that the classical Johnson's Rule leads to optimal schedules on a two-stage flowshop. However, it is still unclear how Johnson's Rule would help in approximation algorithms for scheduling an arbitrary number of parallel two-stage flowshops with the objective of minimizing the makespan. Thus within the paper, we study the problem and propose a new efficient algorithm that incorporates Johnson's Rule applied on each individual flowshop with a carefully designed job assignment process to flowshops. The algorithm is successfully shown to have a runtime O(nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n \log n)$$\end{document} and an approximation ratio 7/3, where n is the number of jobs. Compared with the recent PTAS result for the problem (Dong et al. in Eur J Oper Res 218(1):16-24, 2020), our algorithm has a larger approximation ratio, but it is more efficient in practice from the perspective of runtime.

关键词： Scheduling Two-stage flowshop approximation algorithm Cloud computing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：