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

Critical objective function values in linear sum assignment problems

JOURNAL OF COMBINATORIAL OPTIMIZATION 2018年第3期35卷 842-852页

作者： Belik, Ivan Jornsten, Kurt Norwegian Sch Econ Helleveien 30 N-5045 Bergen Norway

The linear sum assignment problem has been well studied in combinatorial optimization. Because of the integrality property, it is a linear programming problem with a variety of efficient algorithms to solve it. In the given research, we present a reformulation of the linear sum assignment problem and a Lagrangian relaxation algorithm for its reformulation. An important characteristic of the new Lagrangian relaxation method is that the optimal Lagrangian multiplier yields a critical bottleneck value. Lagrangian relaxation has only one Lagrangian multiplier, which can only take on a limited number of values, making the search for the optimal multiplier easy. The interpretation of the optimal Lagrangian parameter is that its value is equal to the price that must be paid for all objects in the problem to be assigned.

关键词： linear sum assignment problem Lagrangian relaxation optimal multiplier

来源：评论

学校读者我要写书评

暂无评论

Deep Neural Networks for linear sum assignment problems

引用

IEEE WIRELESS COMMUNICATIONS LETTERS 2018年第6期7卷 962-965页

作者： Lee, Mengyuan Xiong, Yuanhao Yu, Guanding Li, Geoffrey Ye Zhejiang Univ Coll Informat Sci & Elect Engn Hangzhou 310027 Zhejiang Peoples R China Georgia Inst Technol Sch Elect & Comp Engn Atlanta GA 30332 USA

Many resource allocation issues in wireless communications can he modeled as assignment problems and can be solved online with global information. However, traditional methods for assignment problems take a lot of time to find the optimal solutions. In this letter, we solve the assignment problem using machine learning approach. Specifically, the linear sum assignment problems (LSAPs) are solved by the deep neural networks (DNNs). Since LSAP is a combinatorial optimization problem, it is first decomposed into several sub-assignment problems. Each of them is a classification problem and can be solved effectively with DNNs. Two kinds of DNNs, feed-forward neural network and convolutional neural network, are implemented to deal with the sub-assignment problems, respectively. Based on computer simulation, DNNs can effectively solve LSAPs with great time efficiency and only slight loss of accuracy.

关键词： linear sum assignment problem deep neural network machine learning resource allocation

来源：评论

学校读者我要写书评

暂无评论

Security-Aware Max-Min Resource Allocation in Multiuser OFDMA Downlink

引用

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY 2015年第3期10卷 529-542页

作者： Karachontzitis, Sotiris Timotheou, Stelios Krikidis, Ioannis Berberidis, Kostas Univ Patras Dept Comp Engn & Informat Patras 26504 Greece Univ Cyprus KIOS Res Ctr Intelligent Syst & Networks CY-1678 Nicosia Cyprus Univ Cyprus Dept Elect & Comp Engn CY-1678 Nicosia Cyprus

In this paper, we study the problem of resource allocation for a multiuser orthogonal frequency-division multiple access (OFDMA) downlink with eavesdropping. The considered setup consists of a base station, several users, and a single eavesdropper that intends to wiretap the transmitted message within each OFDMA subchannel. By taking into consideration the existence of the eavesdropper, the base station aims to assign subchannels and allocate the available power in order to optimize the max-min fairness criterion over the users' secrecy rate. The considered problem is a mixed integer nonlinear program. For a fixed subchannel assignment, the optimal power allocation is obtained by developing an algorithm of polynomial computational complexity. In the general case, the problem is investigated from two different perspectives due to its combinatorial nature. In the first, the number of users is equal or higher than the number of subchannels, whereas in the second, the number of users is less than the number of subchannels. In the first case, we provide the optimal solution in polynomial time by transforming the original problem into an assignment one for which there are polynomial time algorithms. In the second case, the secrecy rate formula is linearly approximated and the problem is transformed to a mixed integer linear program, which is solved by a branch-and-bound algorithm. Moreover, optimality is discussed for two particular cases where the available power tends to infinity and zero, respectively. Based on the resulting insights, three heuristic schemes of polynomial complexity are proposed, offering a better balance between performance and complexity. Simulation results demonstrate that each one of these schemes achieves its highest performance at a different power regime of the system.

关键词： Resource allocation physical layer security linear sum assignment problem linear approximation mixed linear integer programming

来源：评论

学校读者我要写书评

暂无评论

Towards auction algorithms for large dense assignment problems

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2009年第3期43卷 411-436页

作者： Bus, Libor Tvrdik, Pavel Czech Tech Univ Dept Comp Sci & Engn CR-16635 Prague Czech Republic

In this paper, we focus on the problem of solving large-scale instances of the linear sum assignment problem by auction algorithms. We introduce a modified auction algorithm, called look-back auction algorithm, which extends the forward auction algorithm by the ability of reusing information from previous bids. We show that it is able to reuse information from the previous bids with high efficiency for all tested types of input instances. We discuss then the design and implementation of a suite of sequential and distributed memory auction algorithms on a Linux cluster with the evaluation on several types of input instances of the linear sum assignment problem. Our results show that the look-back auction algorithm solves sequentially nearly all types of dense instances faster than other evaluated algorithms and it is more stable than the forward-reverse auction algorithm for sparse instances. Our distributed memory auction algorithms are fully memory scalable.

关键词： linear sum assignment problem Auction algorithm linear optimization Distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Joint Subcarrier and Power Allocation in OFDMA Systems for Outage Minimization

引用

IEEE COMMUNICATIONS LETTERS 2016年第10期20卷 2007-2010页

作者： Basaran, Semiha Tedik Kurt, Gunes Karabulut Istanbul Tech Univ Dept Elect & Commun Engn TR-34469 Istanbul Turkey

The joint assignment of subcarriers and limited transmission power is addressed as a combinatorial optimization problem in orthogonal frequency division multiple access networks. To ensure fairness among users while jointly minimizing the total transmit power, the minimization of the number of outage subcarriers is considered as the objective function. The proposed scheme enables distinct rate requirement for each user. Optimal and reduced complexity algorithms, based on the application of Hungarian method to randomly weighted complete bipartite graphs, that reduce the outage probability according to the benchmark works while providing considerable power savings are proposed.

关键词： OFDMA joint subcarrier and power allocation linear sum assignment problem generalized assignment problem

来源：评论

学校读者我要写书评

暂无评论

Design of turbo-code interleaver using Hungarian method

引用

ELECTRONICS LETTERS 1998年第1期34卷 63-65页

作者： Khandani, AK Univ Waterloo Dept Elect & Comp Engn Waterloo ON N2L 3G1 Canada

A method is presented for optimising the structure of the turbo-code interleaver using the Hungarian method (linear sum assignment problem). Numerical results are presented which show a substantial improvement with re... 详细信息

关键词： turbo-code interleaver transfer functions interleaved codes Codes Hungarian method linear sum assignment problem convolutional codes

来源：评论

学校读者我要写书评

暂无评论

An algorithm to approximate the optimal expected inner product of two vectors with given marginals

引用

JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS 2017年第1期451卷 132-145页

作者： Puccetti, Giovanni Univ Milan Dept Econ Management & Quantitat Methods I-20122 Milan Italy

We introduce a new algorithm, called the swapping algorithm, to approximate numerically the minimal and maximal expected inner product of two random vectors with given marginal distributions. As a direct application, the algorithm computes an approximation of the L2-Wasserstein distance between two multivariate measures. The algorithm is simple to implement, accurate and less computationally expensive than the algorithms generally used in the literature for this problem. The algorithm also provides a discretized image of optimal measures and can be extended to more general cost functionals. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Swapping algorithm p-Wasserstein distance Earth Mover's Distance linear sum assignment problem Optimal transportations

来源：评论

学校读者我要写书评

暂无评论

Inference Attacks on Encrypted Databases Based on Order Preserving assignment problem 13th

Inference Attacks on Encrypted Databases Based on Order Pres...

引用

13th International Workshop on Security (IWSEC)

作者： Onozawa, Sota Kunihiro, Noboru Yoshino, Masayuki Naganuma, Ken Univ Tokyo Tokyo Japan Hitachi Ltd Tokyo Japan

ISBN: (纸本)9783319979168;9783319979151

In ACM CCS 2015, Naveed et al. proposed attacks using plaintext auxiliary data for databases encrypted by ordered preserving encryption or more general property preserving encryptions. Their attacks are based on the Hungarian algorithm for solving the linear sum assignment problem (LSAP). In this work, we define a new assignment optimization problem with an additional condition of order structure and propose a search algorithm for finding its exact solution. We apply the new algorithm to attack an encrypted database in the same situation as Naveed et al. and found that our proposed method improves the success probability of the attacks compared with the attacks of Naveed et al.

关键词： linear sum assignment problem Order-preserving encryption Inference attacks Encrypted databases

来源：评论

学校读者我要写书评

暂无评论

Fair Resource Allocation in Multiuser OFDMA Downlink with Passive Eavesdropping 10

Fair Resource Allocation in Multiuser OFDMA Downlink with Pa...

引用

10th IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob)

作者： Karachontzitis, Sotiris Timotheou, Stelios Krikidis, Ioannis Berberidis, Kostas Univ Patras Comp Engn & Informat Dept Patras Greece Univ Patras RACTU RU 8 Patras Greece Univ Cyprus Dept Elect & Comp Engn Nicosia Cyprus Univ Cyprus KIOS Res Ctr Intelligent Syst & Networks Nicosia Cyprus

ISBN: (纸本)9781479950416

关键词： Resource allocation physical layer security mixed integer linear programming linear sum assignment problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：