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

Integrated optimization of material supplying, manufacturing, and product distribution: Models and fast algorithms

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2019年第1期277卷 100-111页

作者： Cheng, Bayi Leung, Joseph Y-T Li, Kai Yang, Shanlin Hefei Univ Technol Sch Management Hefei 230009 Anhui Peoples R China Minist Educ Key Lab Proc Optimizat & Intelligent Decis Making Hefei 230009 Anhui Peoples R China New Jersey Inst Technol Dept Comp Sci Newark NJ 07012 USA

Motivated by applications in electroplating industry, we study an integrated optimization problem of production and logistics for a manufacturer and a third-party logistics (3PL) provider. The objective is to minimize the total cost which includes costs in transportation and inventory of materials, manufacturing, and inventory and outbound distribution of products. The materials are semi-products supplied by a single supplier, and the transportation of materials are accomplished by a 3PL provider. Semi-products may have different sizes and processing times, and they are processed on a batch-processing facility by the manufacturer. Outbound distribution of final products are accomplished by the same 3PL provider. We consider three different models and propose fast algorithms to solve each model. In the first model, semi-products have identical sizes and an optimal algorithm is proposed. In the second model, semi-products have identical processing times and an approximation algorithm is proposed. The algorithm has absolute and asymptotic worst case ratios of 1.5 and 1.223, respectively. In the third model, semi-products have arbitrary sizes and processing times and an approximation algorithm is proposed. The absolute and asymptotic worst case ratios of the algorithm are 2.181 and 2, respectively. The running time of the optimal algorithm of the first model is O(nlogn), while that of the approximation algorithms are O(n(2)). (C) 2019 Elsevier B.V. All rights reserved.

关键词： Scheduling Material supplying Production Distribution approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On the performance guarantee of First Fit for sum coloring

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2019年 99卷 91-105页

作者： Epstein, Leah Levin, Asaf Univ Haifa Dept Math Haifa Israel Technion Fac Ind Engn & Management Haifa Israel

In sum coloring, it is required to find a proper coloring of the vertices of a graph using positive integers, such that the sum of colors of the vertices is minimized. First Fit is the natural coloring algorithm that processes vertices one by one (in some order), and colors the current vertex with the minimum color that was not used for any of its already considered neighbors. Here, we study the approximation ratio of First Fit for sum coloring for the class of claw-free graphs, its most natural subclasses, and its generalizations, and get tight bounds for it. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Graph coloring Chromatic sum number of graphs First Fit approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Single and Multi-Domain Adaptive Allocation algorithms for VNF Forwarding Graph Embedding

引用

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT 2019年第1期16卷 98-112页

作者： Pham Tran Anh Quang Bradai, Abbas Singh, Kamal Deep Picard, Gauthier Riggio, Roberto INRIA Rennes Bretagne Atlantique F-35042 Rennes France Univ Poitiers XLiM inst F-86130 Poitiers France Univ Jean Monnet Dept Comp Sci Telecom & Image Lab Hubert Curien F-42000 St Etienne France Univ Jean Monnet Comp Sci & Intelligent Syst Dept Mines St Etienne IOGSCNRSUMR 5516 LHCInst Henri FayolUniv Lyon F-42023 St Etienne France FBK CREATE NET Wireless & Networked Syst I-38123 Trento Italy

Network function virtualization (NFV) will simplify deployment and management of network and telecommunication services. NFV provides flexibility by virtualizing the network functions and moving them to a virtualization platform. In order to achieve its full potential, NFV is being extended to mobile or wireless networks by considering virtualization of radio functions. A typical network service setup requires the allocation of a virtual network function-forwarding graph (VNF-FG). A VNF-FG is allocated considering the resource constraints of the lower infrastructure. This topic has been well-studied in existing literature, however, the effects of variations of networks over time have not been addressed yet. In this paper, we provide a model of the adaptive and dynamic VNF allocation problem considering also VNF migration. Then we formulate the optimization problem as an integer linear programming (ILP) and provide a heuristic algorithm for allocating multiple VNF-FGs. The idea is that VNF-FGs can be reallocated dynamically to obtain the optimal solution over time. First, a centralized optimization approach is proposed to cope with the ILP-resource allocation problem. Next, a decentralized optimization approach is proposed to deal with cooperative multi-operator scenarios. We adopt AD(3), an alternating direction method of multipliers-based algorithm, to solve this problem in a distributed way. The results confirm that the proposed algorithms are able to optimize the network utilization, while limiting the number of reallocations of VNFs which could interrupt network services.

关键词： Network function virtualization VNF-FG embedding multi-domain orchestration approximation algorithm distributed optimization

来源：评论

学校读者我要写书评

暂无评论

Parametric monotone function maximization with matroid constraints

引用

JOURNAL OF GLOBAL OPTIMIZATION 2019年第3期75卷 833-849页

作者： Gong, Suning Nong, Qingqin Liu, Wenjing Fang, Qizhi Ocean Univ China Sch Math Sci Qingdao 266100 Shandong Peoples R China

We study the problem of maximizing an increasing function f : 2(N) -> R+ subject to matroid constraints. Gruia Calinescu, Chandra Chekuri, Martin Pal and Jan Vondrak have shown that, if f is nondecreasing and submodular, the continuous greedy algorithm and pipage rounding technique can be combined to find a solution with value at least 1 - 1/e of the optimal value. But pipage rounding technique have strong requirement for submodularity. Chandra Chekuri, Jan Vondrak and Rico Zenklusen proposed a rounding technique called contention resolution schemes. They showed that if f is submodular, the objective value of the integral solution rounding by the contention resolution schemes is at least 1- 1/e times of the value of the fractional solution. Let f : 2(N) -> R+ be an increasing function with generic submodularity ratio gamma is an element of (0, 1], and let (N, I) be a matroid. In this paper, we consider the problem max(S is an element of I) f (S) and provide a gamma(1-e(-1))(1-e(-gamma) - o(1))-approximation algorithm. Our main tools are the continuous greedy algorithm and contention resolution schemes which are the first time applied to nonsubmodular functions.

关键词： Increasing set function Matroid Generic submodularity ratio approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Two-machine flow-shop scheduling with equal processing time on the second machine for minimizing total weighted completion time

引用

OPERATIONS RESEARCH LETTERS 2019年第1期47卷 41-46页

作者： Wei, Hongjun Yuan, Jinjiang Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China

We consider the classical two-machine flow-shop scheduling for minimizing the total weighted completion time. For this problem, the computational complexity of a version in which the jobs have a common processing time on the second machine, has not been addressed. We show that the problem is unary NP-hard, answering an open problem posed in Zhu et al. (2016). Then we present an approximation algorithm for the problem with worst-case performance ratio at most 2. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Scheduling Flow shop Total weighted completion time NP-hard approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Scheduling maintenance jobs in networks

引用

THEORETICAL COMPUTER SCIENCE 2019年 754卷 107-121页

作者： Abed, Fidaa Chen, Lin Disser, Yann Gross, Martin Megow, Nicole Meissner, Julie Richter, Alexander T. Rischke, Roman Univ Jeddah Jeddah 23218 Saudi Arabia Univ Houston 4800 Calhoun Rd Houston TX 77004 USA Tech Univ Darmstadt Karolinenpl 5 D-64289 Darmstadt Germany Univ Waterloo 200 Univ Ave W Waterloo ON N2L 3G1 Canada Univ Bremen Bibliothekstr 1 D-28359 Bremen Germany TU Berlin Str 17 Juni 135 D-10623 Berlin Germany TU Braunschweig Univ Pl 2 D-38106 Braunschweig Germany Tech Univ Munich Arcisstr 21 D-80333 Munich Germany Rhein Westfal TH Aachen Templergraben 55 D-52062 Aachen Germany

We investigate the problem of scheduling the maintenance of edges in a network, motivated by the goal of minimizing outages in transportation or telecommunication networks. We focus on maintaining connectivity between two nodes over time;for the special case of path networks, this is related to the problem of minimizing the busy time of machines. We show that the problem can be solved in polynomial time in arbitrary networks if preemption is allowed. If preemption is restricted to integral time points, the problem is NP-hard and in the non-preemptive case we give strong non-approximability results. Furthermore, we give tight bounds on the power of preemption, that is, the maximum ratio of the values of non-preemptive and preemptive optimal solutions. Interestingly, the preemptive and the non-preemptive problem can be solved efficiently on paths, whereas we show that mixing both leads to a weakly NP-hard problem that allows for a simple 2-approximation. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Scheduling Maintenance Connectivity Complexity theory approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

The Minimum Feasible Tileset Problem

引用

algorithmICA 2019年第3期81卷 1126-1151页

作者： Disser, Yann Kratsch, Stefan Sorge, Manuel Tech Univ Darmstadt Grad Sch CE Inst Math Darmstadt Germany Humboldt Univ Inst Informat Berlin Germany TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Ben Gurion Univ Negev Dept Ind Engn & Management Beer Sheva Israel

We introduce and study the Minimum Feasible Tileset problem: given a set of symbols and subsets of these symbols (scenarios), find a smallest possible number of pairs of symbols (tiles) such that each scenario can be formed by selecting at most one symbol from each tile. We show that this problem is APX-hard and that it is NP-hard even if each scenario contains at most three symbols. Our main result is a 4/3-approximation algorithm for the general case. In addition, we show that the Minimum Feasible Tileset problem is fixed-parameter tractable both when parameterized with the number of scenarios and with the number of symbols.

关键词： Set packing approximation algorithm APX hardness Parameterized complexity Minimum feasible tileset

来源：评论

学校读者我要写书评

暂无评论

A Constant Factor approximation algorithm for Reordering Buffer Management 13

A Constant Factor Approximation Algorithm for Reordering Buf...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Noa Avigdor-Elgrabli Yuval Rabani Computer Science Department Technion-Israel Institute of Technology The Rachel and Selim Benin School of Computer Science and Engineering and the Center of Excellence on Algorithms The Hebrew University of Jerusalem

ISBN: (纸本)9781611972511

In the reordering buffer management problem (RBM) a sequence of n colored items enters a buffer with limited capacity k. When the buffer is full, one item is removed to the output sequence, making room for the next input item. This step is repeated until the input sequence is exhausted and the buffer is empty. The objective is to find a sequence of removals that minimizes the total number of color changes in the output sequence. The problem formalizes numerous applications in computer and production systems, and is known to be NP-hard. We give the first constant factor approximation guarantee for RBM. Our algorithm is based on an intricate "rounding" of the solution to an LP relaxation for RBM, so it also establishes a constant upper bound on the integrality gap of this relaxation. Our results improve upon the best previous bound of O({the square root of}log k) of Adamaszek et al. (STOC 2011) that used different methods and gave an online algorithm. Our constant factor approximation beats the super-constant lower bounds on the competitive ratio given by Adamaszek et al. This is the first demonstration of a polynomial time of-fine algorithm for RBM that is provably better than any online algorithm.

关键词： approximation algorithm Reordering Buffer Management first demonstration approximation algorithms buffers Input sequence Constants Sequences

来源：评论

学校读者我要写书评

暂无评论

Minimum Connected Dominating Set Under Routing Cost Constraint in Wireless Sensor Networks With Different Transmission Ranges

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2019年第2期27卷 546-559页

作者： Song, Liang Liu, Chunyan Huang, Hejiao Du, Hongwei Jia, Xiaohua Xiamen Univ Dept Software Engn Xiamen 361005 Peoples R China Nanjing Univ Aeronaut & Astronaut Dept Comp Sci & Technol Nanjing 211106 Jiangsu Peoples R China Harbin Inst Technol Dept Comp Sci & Technol Shenzhen 518055 Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China

Wireless sensor networks (WSNs) are used to cover destination areas for a lot of practical applications. To enhance the performance of the WSN, the virtual backbone based on the connected dominating set is an efficient way with respect to the routing cost between sensors, lifetime of entire network, and so on. In this paper, especially for the WSN with different transmission radii among different sensors, we study the problem of constructing the minimum rho-range connected dominating set under the constraint alpha-times of the minimum routing cost (alpha MOC-rho CDS), where alpha >= 5 and rho is the ratio of the maximum-to-minimum transmission radius. Our contributions are three folds. First, we propose a polynomial time approximation scheme which generates the alpha MOC-rho CDS with the size of at most (1 + epsilon) times of the optimum solution, where epsilon is the error parameter. Second, we propose a polynomial time algorithm and prove that it has two approximation ratios (6 rho + 1)(2)(2 rho + 1)(2) and 10 inverted right perpendicular (2 pi/theta)inverted left perpendicular right perpendicular (ln 3 rho/(ln(1/cos theta))) left perpendicular right perpendicular (ln rho/(ln(2 cos(pi/5)))) left perpendicular, where theta < arcsin(1/3 rho). Finally, we propose the distributed version of the constant approximation ratio algorithm which has both the time complexity and message complexity O(n(3)), where n is the number of sensor nodes. Besides, the simulation results demonstrate the efficiency of our algorithms.

关键词： WSN alpha MOC-rho CDS PTAS approximation algorithm distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Maximizing profit of multiple adoptions in social networks with a martingale approach

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第1期38卷 1-20页

作者： Liu, Bin Yan, Yuxia Fang, Qizhi Dong, Junyu Wu, Weili Wang, Huijuan Ocean Univ China Sch Math Sci Qingdao 266100 Shandong Peoples R China Ocean Univ China Coll Informat Sci & Engn Qingdao 266100 Shandong Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA Qingdao Univ Sch Math & Stat Qingdao 266071 Shandong Peoples R China

Information propagation plays an important role in social network, which helps shaping consumer's purchasing decisions. Most of existing works focus on maximizing the influence of one product. But in our reality life, the majority of the companies produce various products for meeting customer needs. So it is important to learn about how to distribute the limited budget to maximize the companies profits. In this paper, we use the martingale technique to handle the Profit Maximization with Multiple Adoptions (PM2A) problem, which aims to identify a seed set for each product with overall activation cost at most B such that the expected total profit is maximized. We design a PM2AM algorithm which returns a (-epsilon)-approximate solution and runs in O expected time.

关键词： Profit maximization Social network approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：