Incremental assignment problem

Download

index.pdf

Date

2007-03-15

Author

Toroslu, İsmail Hakkı
Üçoluk, Göktürk

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

253
views

0
downloads

In this paper we introduce the incremental assignment problem. In this problem, 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. We propose an O(vertical bar V vertical bar(2)) algorithm for the problem. (c) 2006 Elsevier Inc. All rights reserved.

Subject Keywords

Assignment Problem, Weighted Bipartite Graph, Hungarian Algorithm

URI

https://hdl.handle.net/11511/42414

Journal

INFORMATION SCIENCES

DOI

https://doi.org/10.1016/j.ins.2006.05.004

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

An algorithm for finding core in assignment games Küçükşenel, Serkan (Orta Doğu Teknik Üniversitesi (Ankara, Turkey), 2019-6) This paper presents an algorithm that finds all core payoffs in the assignment games with money. Our algorithm provides an easy way to reach all core outcomes using the similar fixed point construction arguments from the two-sided matching literature.
Application of Project-Based Learning in a Theoretical Course: Process, Difficulties and Recommendations CODUR, K. Burak; Karatas, Sercin; Doğru, Ali Hikmet (2012-01-01) This paper presents a case study about the application of a project-based learning approach. In this case study, software development projects are performed by the students, using historical software development methods in order to demonstrate evolution of the subject. The presented case study differs from others reported in the literature in its utilization of historical methods for project execution. Getting feedback and reaction of students and assessing the success of the project-based learning implemen...
Students Conceptions of fractions A study of 5th grade students Haser, Çiğdem; Ubuz, Behiye (2003-05-01) This paper investigates students’ conception of fractions in solving word-problems. An essay type test including 10 word-problems was administered to 5th grade students in a private elementary school (N=122). An analysis of the difficulties met by the students was given through examples; evidence was given about the crucial role of the meanings of a part and a quantity, and the units in the operations.
Genetic algorithm for the personnel assignment problem with multiple objectives Toroslu, İsmail Hakkı (2007-02-01) The assignment problem is a well-known graph optimization problem defined on weighted-bipartite graphs. The objective of the standard assignment problem is to maximize the summation of the weights of the matched edges of the bipartite graph. In the standard assignment problem, any node in one partition can be matched with any node in the other partition without any restriction. In this paper, variations of the standard assignment problem are defined with matching constraints by introducing structures in the...
Cascaded Multilevel Converter-Based Transmission STATCOM: System Design Methodology and Development of a 12 kV +/- 12 MVAr Power Stage Gultekin, Burhan; Ermiş, Muammer (2013-11-01) This paper deals with the design methodology for cascaded multilevel converter (CMC)-based transmission-type STATCOM(T-STATCOM) and the development of a +/- 12MVAR, 12 kV line-to-line wye-connected, 11-level CMC. Sizing of the CMC module, the number of H-bridges (HBs) in each phase of the CMC, ac voltage rating of the CMC, the number of paralleled CMC modules in the T-STATCOM system, the optimum value of series filter reactors, and the determination of busbar in the power grid to which the T-STATCOM system ...

Citation Formats

İ. H. Toroslu and G. Üçoluk, “Incremental assignment problem,” INFORMATION SCIENCES, pp. 1523–1529, 2007, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/42414.