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

International Conference on Measurement, Instrumentation and Automation (ICMIA 2012)

作者： Wu Wenbo Jia Yufu Sun Hongxing Univ Sci & Technol Liaoning Sch Elect & Informat Engn Anshan 114045 Peoples R China

ISBN: (纸本)9783037855454

The bottleneck assignment (BA) and the generalized assignment (GA) problems and their exact solutions are explored in this paper. Firstly, a determinant elimination (DE) method is proposed based on the discussion of the time and space complexity of the enumeration method for both BA and GA problems. The optimization algorithm to the pre-assignment problem is then discussed and the adjusting and transformation to the cost matrix is adopted to reduce the computational complexity of the DE method. Finally, a synthesis method for both BA and GA problems is presented. The numerical experiments are carried out and the results indicate that the proposed method is feasible and of high efficiency.

关键词： bottleneck assignment generalized assignment problems determinant elimination optimization algorithm pre-assignment problem

来源：评论

学校读者我要写书评

暂无评论

Exact Solution Methods for a generalized assignment Problem with Location/Allocation Considerations

引用

INFORMS JOURNAL ON COMPUTING 2016年第3期28卷 589-602页

作者： Ghoniem, Ahmed Flamand, Tulay Haouari, Mohamed Univ Massachusetts Isenberg Sch Management Operat & Informat Management Dept Amherst MA 01003 USA Qatar Univ Coll Engn Dept Mech & Ind Engn Doha 2713 Qatar

We investigate modeling approaches and exact solution methods for a generalized assignment problem with location/allocation (GAPLA) considerations. In contrast with classical generalized assignment problems, each knapsack in GAPLA is discretized into consecutive segments having different levels of attractiveness. To maximize a total reward function, the decision maker decides not only about item knapsack assignments, but also the specific location of items within their assigned knapsacks and their total space allocation within prespecified lower and upper bounds. Mathematical programming formulations are developed for single and multiple knapsack variants of this problem along with valid inequalities, preprocessing routines, and model enhancements. Further, a branch-and-price algorithm is devised for a set partitioning reformulation of GAPLA, and is demonstrated to yield substantial computational savings over solving the original formulation using branch-and-bound/cut solvers such as CPLEX over challenging problem instances.

关键词： generalized assignment problems column generation branch and price mixed-integer programming

来源：评论

学校读者我要写书评

暂无评论

Data Collection Maximization in Renewable Sensor Networks via Time-Slot Scheduling

引用

IEEE TRANSACTIONS ON COMPUTERS 2015年第7期64卷 1870-1883页

作者： Ren, Xiaojiang Liang, Weifa Xu, Wenzheng Australian Natl Univ Res Sch Comp Sci Canberra ACT 0200 Australia Sun Yat Sen Univ Sch Informat Sci & Technol Guangzhou 51006 Guangdong Peoples R China

In this paper we study data collection in an energy renewable sensor network for scenarios such as traffic monitoring on busy highways, where sensors are deployed along a predefined path (the highway) and a mobile sink travels along the path to collect data from one-hop sensors periodically. As sensors are powered by renewable energy sources, time-varying characteristics of ambient energy sources poses great challenges in the design of efficient routing protocols for data collection in such networks. In this paper we first formulate a novel data collection maximization problem by adopting multi-rate data transmissions and performing transmission time slot scheduling, and show that the problem is NP-hard. We then devise an offline algorithm with a provable approximation ratio for the problem by exploiting the combinatorial property of the problem, assuming that the harvested energy at each node is given and link communications in the network are reliable. We also extend the proposed algorithm by minor modifications to a general case of the problem where the harvested energy at each sensor is not known in advance and link communications are not reliable. We thirdly develop a fast, scalable online distributed algorithm for the problem in realistic sensor networks in which neither the global knowledge of the network topology nor sensor profiles such as sensor locations and their harvested energy profiles is given. Furthermore, we also consider a special case of the problem where each node has only a fixed transmission power, for which we propose an exact solution to the problem. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithms. Experimental results demonstrate that the proposed algorithms are efficient and the solutions obtained are fractional of the optimum.

关键词： Time-slot scheduling approximation algorithms online distributed algorithms energy renewable sensor networks mobile sinks data collection generalized assignment problems

来源：评论

学校读者我要写书评

暂无评论

Spectral projected subgradient with a momentum term for the Lagrangean dual approach

引用

COMPUTERS & OPERATIONS RESEARCH 2007年第10期34卷 3174-3186页

作者： Crema, Alejandro Loreto, Milagros Raydan, Marcos Cent Univ Venezuela Fac Ciencias Dept Computac Caracas 1041A Venezuela

The Lagrangean dual problem, with a non-differentiable convex objective function, is usually solved by using the subgradient method, whose convergence is guaranteed if the optimal value of the dual objective function is known. In practice, this optimal value is approximated by a previously computed bound. In this work, we combine the subgradient method with a different choice of steplength, based on the recently developed spectral projected gradient method, that does not require either exact or approximated estimates of the optimal value. We also add a momentum term to the subgradient direction that accelerates the convergence process towards global solutions. To illustrate the behavior of our new algorithm we solve Lagrangean dual problems associated with integer programming problems. In particular, we present and discuss encouraging numerical results for set covering problems and generalized assignment problems. (c) 2005 Elsevier Ltd. All rights reserved.

关键词： spectral projected gradient subgradient optimization set covering problems generalized assignment problems

来源：评论

学校读者我要写书评

暂无评论

A study of the mean field approach to knapsack problems

引用

NEURAL NETWORKS 1997年第2期10卷 263-271页

作者： Ohlsson, M Pi, H LUND UNIV S-22100 LUNDSWEDEN

The mean field theory approach to knapsack problems is extended to multiple knapsacks and generalized assignment problems with Potts mean field equations governing the dynamics. Numerical tests against ''state of the art'' conventional algorithms shows good performance for the mean field approach. The inherently parallelism of the mean field equations makes them suitable for direct implementations in microchips. It is demonstrated numerically that the performance is essentially not affected when only a limited number of bits is used in the mean field equations. Also, a hybrid algorithm with lineal programming and mean field components is showed to further improve the performance for the difficult homogeneous N X M knapsack problem. (C) 1997 Elsevier Science Ltd. All Rights Reserved.

关键词： knapsack problems generalized assignment problems mean field theory neural networks finite precision

来源：评论

学校读者我要写书评

暂无评论

Reliability-Aware Virtualized Network Function Services Provisioning in Mobile Edge Computing

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2020年第11期19卷 2699-2713页

作者： Huang, Meitian Liang, Weifa Shen, Xiaojun Ma, Yu Kan, Haibin Australian Natl Univ Res Sch Comp Sci Canberra ACT 2601 Australia Univ Missouri Sch Comp & Engn Kansas City MO 64110 USA Fudan Univ Sch Comp Sci Shanghai Key Lab Intelligent Informat Proc Shanghai 200433 Peoples R China Inst Adv Commun & Data Sci Fudan Zhongan Joint Lab Blockchain & Informat Sec Shanghai Peoples R China

Along with Network Function Virtualization (NFV), Mobile Edge Computing (MEC) is becoming a new computing paradigm that enables accommodating innovative applications and services with stringent response delay and resource requirements, including autonomous vehicles and augmented reality. Provisioning reliable network services for users is the top priority of most network service providers, as unreliable services or severe service failures can result in tremendous losses of users, particularly for their mission-critical applications. In this paper, we study reliability-aware VNF instances provisioning in an MEC, where different users request different network services with different reliability requirements through paying their requested services with the aim to maximize the network throughput. To this end, we first formulate a novel reliability-aware VNF instance placement problem by provisioning primary and secondary VNF instances at different cloudlets in MEC for each user while meeting the specified reliability requirement of the user request. We then show that the problem is NP-hard and formulate an Integer Linear Programming (ILP) solution. Due to the NP-hardness of the problem, we instead devise an approximation algorithm with a logarithmic approximation ratio for the problem. Moreover, we also consider two special cases of the problem. For one special case where each request only requests one primary and one secondary VNF instances, the problem is still NP-hard, and we devise a constant approximation algorithm for it. For another special case where different VNFs have the same amounts of computing resource demands, we show that it is polynomial-time solvable by developing a dynamic programming solution for it. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising, and the empirical results of the algorithms outperform their analytical counter

关键词： Reliability Cloud computing Approximation algorithms Heuristic algorithms Mobile computing Edge computing Network function virtualization Reliability-aware VNF instances provisioning VNF instance placements virtualized network function implementation approximation algorithms generalized assignment problems dynamic programming mobile edge computing combinatorial optimization problems

来源：评论

学校读者我要写书评

暂无评论

Repulsive assignment Problem

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2010年第2期144卷 255-273页

作者： Gaudioso, M. Moccia, L. Monaco, M. F. Univ Calabria Dipartimento Elettron Informat & Sistemist I-87036 Arcavacata Di Rende CS Italy CNR Ist Calcolo & Reti Ad Alte Prestaz I-87036 Arcavacata Di Rende CS Italy

Standard assignment is the problem of obtaining a matching between two sets of respectively persons and positions so that each person is assigned exactly one position and each position receives exactly one person, while a linear decision maker utility function is maximized. We introduce a variant of the problem where the persons individual utilities are taken into account in a way that a feasible solution must satisfy not only the standard assignment constraints, but also an equilibrium constraint of the complementarity type, which we call repulsive. The equilibrium constraint can be, in turn, transformed into a typically large set of linear constraints. Our problem is NP-hard and it is a special case of the assignment problem with side constraints. We study an exact penalty function approach which motivates a heuristic algorithm. We provide computational experiments that show the usefulness of a heuristic mechanism inspired by the exact approach. The heuristics outperforms a state-of-the-art integer linear programming solver.

关键词： generalized assignment problems Quadratic assignment problems Memetic algorithms Equilibrium constraints

来源：评论

学校读者我要写书评

暂无评论

Maximizing the Quality of User Experience of Using Services in Edge Computing for Delay-Sensitive IoT Applications 20

Maximizing the Quality of User Experience of Using Services ...

引用

23rd International Conference on Modeling Analysis and Simulation of Wireless and Mobile Systems

作者： Li, Jing Liang, Weifa Xu, Wenzheng Xu, Zichuan Zhao, Jin Australian Natl Univ Canberra ACT Australia Sichuan Univ Chengdu Peoples R China Dalian Univ Technol Dalian Peoples R China Fudan Univ Shanghai Peoples R China

ISBN: (纸本)9781450381178

The Internet of Things (IoT) technology offers unprecedented opportunities to interconnect human beings. However, the latency brought by unstable wireless networks and computation failures caused by limited resources on IoT devices prevents users from experiencing high efficiency and seamless user experience. To address these shortcomings, the integrated MEC with remote clouds is a promising platform, where edge-clouds (cloudlet) are co-located with wireless access points in the proximity of IoT devices, thus intensive-computation and sensing data from IoT devices can be offloaded to the MEC network for processing, and the service response latency can be significantly reduced. In this paper, we study delay-sensitive service provisioning in an MEC network for IoT applications. We first formulate two novel optimization problems, i.e., the total utility maximization problems under both static and dynamic offloading task request settings, with the aim to maximize the accumulative user satisfaction of using the services provided by the MEC. We then show that the defined problems are NP-hard. We instead devise efficient approximation and online algorithms with provable performance guarantees for the problems. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising.

关键词： Cost modeling heterogeneous MEC networks service provisioning delay-sensitive services generalized assignment problems user service experience approximation algorithms online algorithms the average service delay the user experience of using services edge computing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：