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

A common due-date assignment problem with job rejection on parallel uniform machines

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2024年第6期62卷 2083-2092页

作者： Mosheiov, Gur Sarig, Assaf Hebrew Univ Jerusalem Sch Business Adm Jerusalem Israel Hebrew Univ Jerusalem Dept Stat Jerusalem Israel Coll Law & Business Ramat Gan Israel Hebrew Univ Jerusalem Sch Business Adm IL-91905 Jerusalem Israel Hebrew Univ Jerusalem Dept Stat IL-91905 Jerusalem Israel

We study a common due-date assignment problem on two parallel uniform machines. The jobs are assumed to have identical processing times, and job-dependent and asymmetric earliness and tardiness unit costs. The scheduler may process only a subset of the jobs, i.e. the option of job-rejection is allowed. The objective function consists of three cost components: the total earliness-tardiness cost of all scheduled jobs, the cost of the common due-date, and total rejection cost. For a given number of rejected jobs and a given due-date, the problem is reduced to a non-standard linear assignment problem. Consequently, the optimal solution is shown to be obtained in polynomial time in the number of jobs. The case of a given (possibly restrictive) due-date, the extension to a setting of more than two machines, and a number of special cases, are also discussed.

关键词： Scheduling due-date assignment uniform machines linear assignment problem job-rejection

来源：评论

学校读者我要写书评

暂无评论

A SHORTEST AUGMENTING PATH ALGORITHM FOR DENSE AND SPARSE linear assignment problemS

引用

COMPUTING 1987年第4期38卷 325-340页

作者： JONKER, R VOLGENANT, A UNIV AMSTERDAM FAC ACTUARIAL SCI & ECONOMETR1011 NH AMSTERDAMNETHERLANDS

We develop a shortest augmenting path algorithm for the linear assignment problem. It contains new initialization routines and a special implementation of Dijkstra's shortest path method. For both dense and sparse problems computational experiments show this algorithm to be uniformly faster than the best algorithms from the literature. A Pascal implementation is presented.

关键词： 90 C 08 68 E 10 linear assignment problem shortest path methods Pascal implementation

来源：评论

学校读者我要写书评

暂无评论

RL-ISLAP: A Reinforcement Learning Framework for Industrial-Scale linear assignment problems at Alipay 24

RL-ISLAP: A Reinforcement Learning Framework for Industrial-...

引用

33rd ACM International Conference on Information and Knowledge Management (CIKM)

作者： Li, Hanjie Ning, Yue Bao, Yang Li, Changsheng Chen, Boxiao Lu, Xingyu Yuan, Ye Wang, Guoren Beijing Inst Technol Beijing Peoples R China

ISBN: (纸本)9798400704369

Industrial-scale linear assignment problems (LAPs) are frequently encountered in various industrial scenarios, e.g., asset allocation within the domain of credit management. However, optimization algorithms for such problems (e.g., PJ-ADMM) are highly sensitive to hyper-parameters. Existing solving systems rely on empirical parameter selection, which is challenging to achieve convergence and extremely time-consuming. Additionally, the resulting parameter rules are often inefficient. To alleviate this issue, we propose RL-ISLAP, an efficient and lightweight Reinforcement Learning framework for Industrial-Scale linear assignment problems. We formulate the hyper-parameter selection for PJ-ADMM as a sequential decision problem and leverage reinforcement learning to enhance its convergence. Addressing the sparse reward challenge inherent in learning policies for such problems, we devise auxiliary rewards to provide dense signals for policy optimization, and present a rollback mechanism to prevent divergence in the solving process. Experiments on OR-Library benchmark demonstrate that our method is competitive to SOTA stand-alone solvers. Furthermore, the scale-independent design of observations enables us to transfer the acquired hyper-parameter policy to a scenario of LAPs in varying scales. On two real-world industrial-scale LAPs with up to 10 millions of decision variables, our proposed RL-ISLAP achieves solutions of comparable quality in 2/3 of the time when compared to the SOTA distributed solving system employing finetuned empirical parameter rules.

关键词： linear assignment problem Large-Scale Optimization PJ-ADMM Reinforcement Learning

来源：评论

学校读者我要写书评

暂无评论

Optimising LTE Uplink Scheduling by Solving the Multidimensional assignment problem 6

Optimising LTE Uplink Scheduling by Solving the Multidimensi...

引用

6th International ICST Conference on Mobile Networks and Management (MONAMI)

作者： Elsner, Raphael Muehleisen, Maciej Timm-Giel, Andreas Hamburg Univ Technol Inst Commun Networks Hamburg Germany

ISBN: (纸本)9783319162928;9783319162911

Inter-cell interference mitigation in LTE networks is important to improve the system throughput. Upcoming Cloud Radio Access Networks (C-RANs) allow controlling multiple cells at a single location enabling novel inter-cell coordination algorithms. Coordinated recourse allocation can be used to achieve optimal spectral efficiency through reduced inter-cell interference. In this paper the uplink resource allocation is optimised by deciding which user terminals served by different base stations should transmit on the same resources. A central meta-scheduler situated in the cloud is responsible for the optimisation. The optimisation is performed using heuristic algorithms to solve the underlying multidimensional assignment problem. The complexity is further reduced to a feasible size by only coordinating a subset of base stations. This way the problem can be solved for real world cellular deployments. The performance for different groupings of cooperatively managed base stations is investigated. Results show that coordinating resource assignment of multiple base stations improves the cell spectral efficiency in general and coordinating three sectors at the same site outperforms coordinating three base stations of different sites.

关键词： LTE Radio resource management Inter-cell interference coordination Base station grouping Interference mitigation linear assignment problem Multidimensional assignment problem IMT-Advanced C-RAN

来源：评论

学校读者我要写书评

暂无评论

A spectral assignment approach for the graph isomorphism problem

引用

INFORMATION AND INFERENCE-A JOURNAL OF THE IMA 2018年第4期7卷 689-706页

作者： Klus, Stefan Sahai, Tuhin Freie Univ Dept Math & Comp Sci D-14195 Berlin Germany United Technol Res Ctr Berkeley CA 94705 USA

In this paper, we propose algorithms for the graph isomorphism (GI) problem that are based on the eigendecompositions of the adjacency matrices. The eigenvalues of isomorphic graphs are identical. However, two graphs G(A) and G(B) can be isospectral but non-isomorphic. We first construct a GI testing algorithm for friendly graphs and then extend it to unambiguous graphs. We show that isomorphisms can be detected by solving a linear assignment problem (LAP). If the graphs possess repeated eigenvalues, which typically correspond to graph symmetries, finding isomorphisms is much harder. By repeatedly perturbing the adjacency matrices and by using properties of eigenpolytopes, it is possible to break symmetries of the graphs and iteratively assign vertices of G(A) to vertices of G(B), provided that an admissible assignment exists. This heuristic approach can be used to construct a permutation which transforms G(A) into G(B) if the graphs are isomorphic. The methods will be illustrated with several guiding examples.

关键词： graph isomorphism problem friendly graphs linear assignment problem

来源：评论

学校读者我要写书评

暂无评论

Zero Element Row Augmenting Path Algorithm for linear assignment problems 28

Zero Element Row Augmenting Path Algorithm for Linear Assign...

引用

28th Chinese Control and Decision Conference

作者： Xu, Wang-Bao Rong, Gen-Xi Chen, Xue-Bo Liaoning Univ Sci & Technol Sch Elect & Informat Engn Anshan 114051 Peoples R China

ISBN: (纸本)9781467397148

A zero element row augmenting path algorithm is proposed for linear assignment problems. Under the algorithm, the maximum element in an assignment y is picked firstly, where y is calculated according to the reduced matrix of a given cost matrix at the initial stage. According to each row's zero element record and starting from the row containing the picked element, a zero element row augmenting path is computed while the cost matrix is further reduced and the zero element record of each row is updated. Finally, y is adjusted according to the augmenting path so that the number of the zero elements in y can increase strictly. The above process is repeated until y is an optimal assignment. Extensive computational experiments are carried out and indicate that the proposed algorithm is even faster than the shortest augmenting algorithm.

关键词： linear assignment problem Hungarian Method and Shortest Augmenting Path Algorithm

来源：评论

学校读者我要写书评

暂无评论

New auction algorithms for the assignment problem and extensions

引用

RESULTS IN CONTROL AND OPTIMIZATION 2024年 14卷

作者： Bertsekas, Dimitri Arizona State Univ Sch Comp & Augmented Intelligence Computat Decis Making Tempe AZ 85281 USA

We consider the classical linear assignment problem, and we introduce new auction algorithms for its optimal and suboptimal solution. The algorithms are founded on duality theory, and are related to ideas of competitive bidding by persons for objects and the attendant market equilibrium, which underlie real-life auction processes. We distinguish between two fundamentally different types of bidding mechanisms: aggressive and cooperative. Mathematically, aggressive bidding relies on a notion of approximate coordinate descent in dual space, an epsilon-complementary slackness condition to regulate the amount of descent approximation, and the idea of epsilon-scaling to resolve efficiently the price wars that occur naturally as multiple bidders compete for a smaller number of valuable objects. Cooperative bidding avoids price wars through detection and cooperative resolution of any competitive impasse that involves a group of persons. We discuss the relations between the aggressive and the cooperative bidding approaches, we derive new algorithms and variations that combine ideas from both of them, and we also make connections with other primal-dual methods, including the Hungarian method. Furthermore, our discussion points the way to algorithmic extensions that apply more broadly to network optimization, including shortest path, max-flow, transportation, and minimum cost flow problems with both linear and convex cost functions.

关键词： linear assignment problem Auction algorithm Optimal solution Duality theory

来源：评论

学校读者我要写书评

暂无评论

ANATOMICALLY-INFORMED MULTIPLE linear assignment problemS FOR WHITE MATTER BUNDLE SEGMENTATION 16

ANATOMICALLY-INFORMED MULTIPLE LINEAR ASSIGNMENT PROBLEMS FO...

引用

16th IEEE International Symposium on Biomedical Imaging (ISBI)

作者： Berto, Giulia Avesani, Paolo Pestilli, Franco Bullock, Daniel Carona, Bradley Olivetti, Emanuele Bruno Kessler Fdn Neurolnformat Lab NILab Trento Italy Univ Trento Ctr Mind & Brain Sci CIMeC Trento Italy Indiana Univ Bloomington IN 47405 USA

ISBN: (纸本)9781538636411

Segmenting white matter bundles from human tractograms is a task of interest for several applications. Current methods for bundle segmentation consider either only prior knowledge about the relative anatomical position of a bundle, or only its geometrical properties. Our aim is to improve the results of segmentation by proposing a method that takes into account information about both the underlying anatomy and the geometry of bundles at the same time. To achieve this goal, we extend a state-of-the-art example-based method based on the linear assignment problem (LAP) by including prior anatomical information within the optimization process. The proposed method shows a significant improvement with respect to the original method, in particular on small bundles.

关键词： diffusion MRI bundle segmentation linear assignment problem

来源：评论

学校读者我要写书评

暂无评论

Incremental assignment problem (vol 177, pg 1523, 2007)

引用

INFORMATION SCIENCES 2008年第23期178卷 4583-4583页

作者： Volgenant, A. Univ Amsterdam Fac Econ & Econometr Operat Res Grp NL-1018 WB Amsterdam Netherlands

In Toroslu and Ucoluk [I.H. Toroslu, G. Ucoluk, Incremental assignment problem, Information Sciences 177 (2007) 1523-1529] the incremental assignment problem is defined as follows. A new pair of vertices and their incident edges are added to a weighted bipartite graph whose maximum-weighted matching is already known, and the maximum-weighted matching of the extended graph is sought. An O(n(2)) algorithm for the problem has been derived, with n the size of a partition in the bipartite graph. We point out that such a result can be found in literature. (C) 2008 Elsevier Inc. All rights reserved.

关键词： linear assignment problem Weighted bipartite graph Hungarian algorithm

来源：评论

学校读者我要写书评

暂无评论

Matching based ground-truth annotation for online handwritten mathematical expressions

引用

PATTERN RECOGNITION 2015年第3期48卷 837-848页

作者： Hirata, Nina S. T. Julca-Aguilar, Frank D. Univ Sao Paulo Inst Math & Stat Dept Comp Sci BR-1010 Sao Paulo Brazil

Assessment of mathematical expression recognition at expression level only is not sufficient to diagnose strengths and weaknesses of different recognition systems. In order to make assessment at different levels possible, large datasets annotated with ground-truth data at different levels, such as at symbol segmentation, symbol classification, symbol/sub-expression spatial relationships, baselines or whole expression levels, are needed. Creation of ground-truthed datasets of handwritten mathematical expressions is a challenging task due to the need to cope with a large variability of symbol classes, expression layouts, writing styles, among other issues including the fact that manual annotation is an error-prone procedure. We propose an expression matching approach where symbols in a transcribed expression are assigned to the corresponding symbols in the respective model expression. Matching is formulated as a simple linear assignment problem where matching cost is defined as a weighted linear combination of local (symbol) and global (structural) characteristics. Once a symbol-to-symbol assignment is computed, not only symbol labels but all other ground-truth data attached to the model expression can be automatically transferred to the transcribed expression. We use two independent large test sets to empirically evaluate the influence of the cost function terms on matching performance. Results show mean symbol assignment rates above 99% on both sets, suggesting the potential of the method as an useful tool for helping the creation of ground-truthed online mathematical expression datasets. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Structural pattern analysis Shape information Handwriting recognition linear assignment problem Ground-truth annotation Mathematical expression dataset

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：