Assignment problem and its variations

Download

index.pdf

Date

2007

Author

Gülek, Mehmet

Metadata

Show full item record

Item Usage Stats

211
views

79
downloads

We investigate the assignment problem, which is the problem of matching two sets with each other, optimizing a given function on the possible matchings. Among different definitions, a graph theoretical definition of the linear sum assignment problem is as follows: Given a weighted complete bipartite graph, find a maximum (or minimum) one-to-one matching between the two equal-size sets of the graph, where the score of a matching is the total weight of the matched edges. We investigate extensions and variations like the incremental assignment problem, maximum subset matching problem, maximum-weighted tree matching problem. We present a genetic algorithm scheme for maximum-weighted tree matching problem, and experimental results of our implementation.

Subject Keywords

Computer enginnering., Electronic computers.

URI

http://etd.lib.metu.edu.tr/upload/12609145/index.pdf
https://hdl.handle.net/11511/17352

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Genetic algorithm for personnel assignment problem with multiple objectives Arslanoğlu, Yılmaz; Toroslu, İsmail Hakkı; Department of Computer Engineering (2006) This thesis introduces a multi-objective variation of the personnel assignment problem, by including additional hierarchical and team constraints, which put restrictions on possible matchings of the bipartite graph. Besides maximization of summation of weights that are assigned to the edges of the graph, these additional constraints are also treated as objectives which are subject to minimization. In this work, different genetic algorithm approaches to multi-objective optimization are considered to solve th...
Personnel assignment problem with hierarchical ordering constraints Toroslu, İsmail Hakkı (Elsevier BV, 2003-10-01) In the standard assignment problem, there is no constraint on the partitions of the bipartite graph. The only objective is to maximize the summation of the weights of the matched edges. Any node in one partition can be matched with any node in the other partition without any restriction. In this paper, we study a variation of the standard assignment problem, having some ordering constraints on the partitions of the bipartite graph. We call this problem as 'assignment problem with hierarchical ordering const...
Sphere-packing bound for block-codes with feedback and finite memory Giacomo, Como; Nakiboğlu, Barış (2010-07-23) A lower bound bound is established on the error probability of fixed-length block-coding systems with finite memory feedback, which can be described in terms of a time dependent finite state machine. It is shown that the reliability function of such coding systems over discrete memoryless channels is upper-bounded by the sphere-packing exponent.
On an architecture for a parallel finite field multiplier with low complexity based on composite fields Kındap, Nihal; Özbudak, Ferruh; Department of Cryptography (2004) In this thesis, a bit parallel architecture for a parallel finite field multiplier with low complexity in composite fields GF((2n)m) with k = n · m (k 32) is investigated. The architecture has lower complexity when the Karatsuba-Ofman algorithm is applied for certain k. Using particular primitive polynomials for composite fields improves the complexities. We demonstrated for the values m = 2, 4, 8 in details. This thesis is based on the paper أA New Architecture for a Parallel Finite Field Multiplier with ...
Cyclic codes and reducible additive equations Guneri, Cem; Özbudak, Ferruh (Institute of Electrical and Electronics Engineers (IEEE), 2007-02-01) We prove a Weil-Serre type bound on the number of solutions of a class of reducible additive equations over finite fields. Using the trace representation of cyclic codes, this enables us to write a general estimate for the weights of cyclic codes. We extend Woffmann's weight bound to a larger classes of cyclic codes. In particular, our result is applicable to any cyclic code over F-p and F-p2, where p is an arbitrary prime. Examples indicate that our bound performs very well against the Bose-Chaudhuri-Hocqu...

Citation Formats

M. Gülek, “Assignment problem and its variations,” M.S. - Master of Science, Middle East Technical University, 2007.