assignment problem konig 1916

www.springer.com The European Mathematical Society

• StatProb Collection
• Recent changes
• Current events
• Random page
• Project talk
• Request account
• What links here
• Related changes
• Special pages
• Printable version
• Permanent link
• Page information
• View source

König theorem

If the entries of a rectangular matrix are zeros and ones, then the minimum number of lines containing all ones is equal to the maximum number of ones that can be chosen so that no two of them lie on the same line. (Here the term "line" denotes either a row or a column in the matrix.) The theorem was formulated and proved by D. König [1] . It is one of the basic theorems in combinatorics and is the matrix analogue of Hall's criterion for the existence of a system of distinct representatives of a family of subsets of a finite set (see Selection theorems ). There is also a widespread statement of König's theorem in terms of graphs: In a bipartite graph (cf. Graph, bipartite ) the number of edges in a maximal matching is equal to the number of elements of a minimal vertex covering.

König's theorem is often used in various combinatorial questions relating to selection and extremal problems. A generalization to the case of infinite matrices is known [3] .

A vertex covering or disconnecting set of a graph $G$ is a collection of vertices $C$ such that every edge $G$ is incident with a vertex from $C$ (i.e. the edges incident with a vertex from $C$ cover $G$). A minimal vertex covering is a cut set.

The term rank of a matrix of zeros and ones is defined as the largest number of ones such that no two lie in the same row or column. Thus, König's theorem, also known as the König–Egerváry theorem, can also be formulated as: The term rank of a $(0,1)$-matrix $A$ is equal to the minimum number of rows and columns which together cover all the 1's of $A$.

• Combinatorics
• This page was last edited on 26 October 2014, at 22:37.
• Privacy policy
• About Encyclopedia of Mathematics
• Disclaimers
• Impressum-Legal

Some good characterization results relating to the Kőnig–Egerváry theorem

• Original Paper
• Published: 20 December 2009
• Volume 18 , pages 37–45, ( 2010 )

Cite this article

• Mihály Hujter 1  

92 Accesses

Explore all metrics

We survey some combinatorial results which are all related to some former results of ours, and, at the same time, they are all related to the famous Kőnig–Egerváry theorem from 1931.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

Generalizations of Stanley’s Theorem: Combinatorial Proofs and Related Inequalities

Introduction

An effective bombieri–vinogradov theorem and its applications.

Arkin EM, Hassin R, Rubinstein S, Svidirenko M (2002) Approximations for maximum transportation with permutable supply vector and other capacitated star packing problems. In: Penttonen M, Meineche E Schmidt (eds) SWAT2002, LNCS2368, pp 280–287

Arkin EM, Hassin R, Rubinstein S, Svidirenko M (2004) Approximations for maximum transportation with permutable supply vector and other capacitated star packing problems. Algorithmica 39: 175–187

Article   Google Scholar  

Biró M, Hujter M, Tuza Z (1992) Precoloring extension I. Interval graphs. Discrete Math 100: 267–279

Blázsik Z, Hujter M, Pluhár A, Tuza Z (1993) Graphs with no induced C 4 and 2 K 2 . Discrete Math 115: 51–55

Egerváry J (1931) Matrixok kombinatorius tulajdonságairól [in Magyar with German summary] Matematikai és Fizikai Lapok, 38, pp 16–28 [English trans. by Kuhn HW]: On combinatorial properties of matrices, Logistics Papers, George Washington University, 11, pp 1–11 (1955)

Egerváry E (1958) Bemerkungen zum transport problem. MTW Mitt 5: 278–284

Google Scholar  

Egerváry E (1958) Kombinatorikus módszer a szállítási probléma megoldására. A Matematikai Kutató Intézet közleményei 4(1): 15–28

Földes S, Hammer PL (1977) Split graphs. In: Hoffmann F, et al (eds) Proceedings of the 8th southeastern conference on combinatorics, graph theory and computing, Lousiana State University, Baton Rouge, Louisiana, pp 311–315

Frankl P (1987) The shifting technique in extremal set theory. In: Whitehead C (ed) Surveys in combinatorics 1987, invited papers for the 11th British combinatorial conference, London Math Soc Lect Note Series 123, Cambridge University Press, pp 81–110

Frankl P, Füredi Z (1986) Extremal problems concerning Kneser graphs. J Combin Theory B 40: 270–284

Frankl P, Füredi Z (1991) Beyond the Erdős–Ko–Rado theorem. J Combin Theory A 56: 182–194

Frobenius G (1968) Über zerlegbare Determinanten, Sitzungsb erichte der Königlich Preußischen Akademie der Wissenschaften zu Berlin, pp 274–277 (1917) [reprinted in: Ferdinand Georg Frobenius, Gesammelte Abhandlungen, Band III Serre J-P (ed) Springer, Berlin, pp 701–704]

Golumbic MC (1980) Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York

Guruswami V (1999) Enumerative aspects of certain subclasses of perfect graphs. Discrete Math 205: 97–117

Gyárfás A, Lehel J (1970) On a Helly type problem in trees. Colloq Math Societatis János Bolyai 4: 571–584

Hujter M (1981) A combinatorial optimization problem: classical and computerized methods. Translation of M.S. Thesis from Magyar, Eötvös University, Budapest available at http://picasaweb.google.hu/Hujter.Misi/1981

Hujter M (1992) Hungarian method [in Magyar]. Iskolakultúra Math–Inf–Tech 2: 15–20

Hujter M (1999) Simplified and strengthened methods for the transportation problem with a permuted demand vector (unpublished)

Hujter M, Tuza Z (1993) Precoloring extension II. Graphs classes related to bipartite graphs. Acta Math Univ Comeniane LXII: 1–11

Hujter M, Tuza Z (1996) Precoloring extension III. Classes of perfect graphs. Combin Probab Comput 5: 35–56

Hujter M, Klinz B, Woeginger G (1999) Transportation problem with permuted demand vector. Math Methods Oper Res 50: 9–16

König D (1916) Über graphen und iher anwendung auf determinantentheorie und mengenlehre. Math Ann 77: 453–465

Kőnig D (1931) Graphok és matrixok [in Magyar]. Math és Fizikai Lapok 38: 116–119

Kőnig D (2005) A letter to Kalmár L [in Magyar]. October 3, 1945; published in P.G.Szabó, Kalmárium I, Polygon, Szeged

Kuhn HW (1955) The Hungarian method for the assignment problem. Naval Res Logistic Q 2: 83–97

Lubell D (1966) A short proof of Sperner theorem. J Combin Theory 1: 299

Meusel SG (1998) Minimizing the placement time on circuit boards. Ph.D.Thesis, Techn. Univ. Bergakademie Freiberg

Meusel SG, Burkard RE (1999) A transportation problem with a permuted demand vector. Math Methods Oper Res 50: 1–7

Rényi A (1945) A letter to F. Riesz [in Magyar], July 5, 1945. Eötvös University, Mathematics Inst., Budapest

Sperner E (1928) Ein Satz über Untermengen einer endlichen Menge. Math Z 27: 544–548

Steinbrecher B (1997) Ein Transport problem mit permutiertem Bedarfsvektor [in German], Master’s thesis, TU Bergakademe Freiberg

Download references

Author information

Authors and affiliations.

Budapest University of Technology and Economics, Budapest, Hungary

Mihály Hujter

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Mihály Hujter .

Rights and permissions

Reprints and permissions

About this article

Hujter, M. Some good characterization results relating to the Kőnig–Egerváry theorem. Cent Eur J Oper Res 18 , 37–45 (2010). https://doi.org/10.1007/s10100-009-0126-y

Download citation

Published : 20 December 2009

Issue Date : March 2010

DOI : https://doi.org/10.1007/s10100-009-0126-y

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Good characterization
• Kőnig–Egerváry theorem
• Find a journal
• Publish with us
• Track your research

We apologize for the inconvenience...

To ensure we keep this website safe, please can you confirm you are a human by ticking the box below.

If you are unable to complete the above request please contact us using the below link, providing a screenshot of your experience.

https://ioppublishing.org/contacts/

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Did Jacobi invent the Hungarian algorithm for the assignment problem over a century before Kőnig and Egerváry?

Wikipedia says:

In 2006, it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin.

The provided reference gives no support to the statement. Do you know the story? Is it true? Who discovered it?

• discoveries
• combinatorics
• optimization

• 1 $\begingroup$ In that reference you click in the left top corner on "Presentation". I suppose it answers your question. Translations of Jacobi papers in question are also there. $\endgroup$ –  Alexandre Eremenko Commented Nov 7, 2019 at 22:56

It is true. Wikipedia links to the website of Ollivier, which hosts both the original posthumous publication in Latin, De investigando ordine systematis aequationum differentialum vulgarium cujuscunque , and its English translation, About the Research of the Order of a System of Arbitrary Ordinary Differential Equations, by Ollivier himself. Unfortunately, navigation within the site is not reflected in the urls, so you have to click on Translations on the top left to see them. Ollivier is the one who "found" it, and he describes the full story of the problem in Jacobi's bound. Transmission and oblivion of a mathematical notion :

" Jacobi himself is possibly the first to have forgotten his own work. According to Koenigsberger ([13]), his manuscripts on this subject were written around 1836 and were intended to be a part of a forsaken project of long paper on differential equations. Part of this work was incorporated in his great paper on the last multiplier, but the bound himself was never published in his lifetime. [...] Jacobi's widow gave the manuscripts he left to Dirichlet who began to work for their publication with his friends Borchardt and Joachimsthal. Very few documents remain from that work and the best source seems to be Koenigsberger ([13]). It seems that the paper were in great disorder... Borchardt entrusted Sigismund Cohn, who worked on the publication of some others manuscripts of Jacobi, with the documents related to the bound... After his death, the work was continued by Borchardt who published the 1st paper [8] in his journal in 1865. The second [9] was published by Clebsch in the volume Vorlesungen uber Dynamik ([FD]) in 1866. This one was quoted by Sofya Kovalevskaya in one of her most famous papers ([16]) in 1875. "

For details on the assignment problem itself and the "Hungarian" algortihm for solving it, known already to Jacobi, see Jeno Egervary: from the origins of the Hungarian algorithm to satellite communication :

" Jacobi introduces a bound on the order of a system of $m$ ordinary differential equations in $m$ unknowns, and observes that its computation can be reduced to the following problem... in which however the assignment problem is easily recognized: Arrange $nn$ arbitrary numbers $h^{(i)}_k$ in a square table so that there are n horizontal series and n vertical series, each having n numbers. Among these numbers, we want to select $n$ transversals, i.e., all placed in different horizontal and vertical series, which may be done in $1\cdot2\cdots n$ ways; among all these ways, we want to find one that gives the maximum sum of the $n$ selected numbers.)

Not only Jacobi defined the AP, but, more importantly, he gave a polynomial- time algorithm to solve it. Although a thorough analysis of this method has not been provided yet, Ollivier and Sadik [29] recently observed that it is essentially identical to the Hungarian algorithm, thus anticipating by many decades the results we have examined in the previous sections. As wittily observed by Kuhn [24], this makes another application of Stigler's law of eponymy": No scientific discovery is named after its original discoverer (Stigler [34], see also Kuhn [23]). "

Your Answer

Sign up or log in, post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged discoveries combinatorics algorithm optimization or ask your own question .

• Featured on Meta
• Preventing unauthorized automated access to the network
• User activation: Learnings and opportunities
• Join Stack Overflow’s CEO and me for the first Stack IRL Community Event in...

Hot Network Questions

• What is an ellipse in infinite-dimensional spaces?
• Is there any language which distinguishes between “un” as in “not” and “un” as in “inverse”?
• Why is China not mentioned in the Fallout TV series despite its significant role in the games' lore?
• Could a civilisation develop spaceflight by artillery before developing orbit-capable rockets?
• What are these Ports on Multimeter PCB & What Protocol are they Using?
• Does legislation on transgender healthcare affect medical researchers?
• How is the universe able to run physics so smoothly?
• Does the old type of rubber hose Dunlop valves haves any pros compared to the modern ones without rubber?
• Pulling myself up with a pulley attached to myself
• Print 4 billion if statements
• Did Gauss really call Archimedes an idiot?
• Why did the Apollo 13 tank #2 have a heater and a vacuum?
• The meaning(s) of 'She couldn't buy a car yesterday.'
• In the absence of an agreement addressing the issue, is there any law giving a university copyright in an undergraduate student's class paper?
• How do I link a heading containing spaces in Markdown?
• Could you compress chocolate such that it has the same density and shape as a real copper coin?
• How to push 10-ft long 4" PVC pipe into 90-deg Elbow Hub?
• Is a private third party allowed to take things to court?
• How was the year spoken in late 1800s England?
• If I distribute GPLv2-licensed software as a bundle that uses a virtual machine to run it, do I need to open-source the virtual machine too?
• Is “No Time To Die” the first Bond film to feature children?
• 2000s creepy independant film with a voice-over of a radio host giving bad self-help advice
• What is the mechanical equivalent of an electronic AND gate?
• How long has given package been deferred due to phasing?

• DOI: 10.1007/978-3-540-68279-0_2
• Corpus ID: 9426884

The Hungarian method for the assignment problem

• Published in 50 Years of Integer… 1 March 1955

Mathematics

• Naval Research Logistics (NRL)

11,819 Citations

A note on hungarian method for solving assignment problem, the optimal assignment problem: an investigation into current solutions, new approaches and the doubly stochastic polytope, an effective algorithm to solve assignment problems : opportunity cost approach, optimal assignment problem on record linkage, an application of the hungarian algorithm to solve traveling salesman problem.

• Highly Influenced

Heuristic algorithms and learning techniques: applications to the graph coloring problem

A simulation of the faculty-assignment problem: an integer programming approach, computational studies of randomized multidimensional assignment problems, optimal solution of an assignment problem as a special case of transportation problem, assignment problems by, 17 references, a combinatorial algorithm, solution of the personnel classification problem with the method of optimal regions, the problem of classification of personnel, history of mathematical programming : a collection of personal reminiscences, on representatives of subsets, on a personnel assignment problem, on the hitchcock distribution problem, 1. a certain zero-sum two-person game equivalent to the optimal assignment problem, über graphen und ihre anwendung auf determinantentheorie und mengenlehre, related papers.

Showing 1 through 3 of 0 Related Papers

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to  upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

• We're Hiring!
• Help Center

Download Free PDF

TRO - Masalah Penugasan (Metode Hungarian)

Related papers

JITMI (Jurnal Ilmiah Teknik dan Manajemen Industri)

Dengan meningkatnya kebutuhan hidup manusia, jenis-jenis pekerjaan pun mulai bermunculan. Namun variasi pekerjaan ini tidak selamanya cocok dengan setiap individu yang mengerjakannya. Hal inilah yang berpotensi memunculkan kesalahan-kesalahan dalam pekerjaan tersebut. Salah satu cara umum yang biasa digunakan untuk meminimalkan kesalahan dalam pekerjaan adalah dengan penugasan atau assignment. PT Duaroda Saranatama merupakan perusahaan yang bergerak di bidang industri Rotational Moulding. Sebagai upaya untuk menyusun penugasan yang optimal di PT Duaroda Saranatama, digunakanlah metode Hungarian. Hungarian method merupakan metode untuk menentukan alokasi sumber daya ke suatu tugas terterntu secara satu persatu (one by one). Penelitian ini dilakukan untuk mengetahui lamanya pengerjaan penyelesaian produk cooler box di PT Duaroda Saranatama tepatnya dibagian finishing, mengetahui penempatan pekerja dengan mesin ...

E-Jurnal Matematika

Assignment problem is one of the cases that found in linear programming. Assignment problem is related to the allocation of workers for available jobs. From several sources, Hungarian method is more often used to solve the assignment problem. In the Hungarian method, if an unbalanced problem is found, the lack of the source or destination will be added to the dummy variable so that the case becomes balanced. The jobs that executed on the dummy machine will be ignored. In real-life situations, it is impossible for companies to ignore existing work because of a lack of workers. Therefore, the Hungarian method is modified to resolve this condition, so that the total assignment cost can still be optimized.

UMKM XYZ is a business that is engaged in snacks. This business is very famous, not only among young people, even parents and children also like this snack. The high demand creates new problems for these small businesses. Employees who are in charge of sending ready-to-process raw materials have different delivery times using the same facility. This causes a lack of time efficiency in the delivery of ready-to-process raw materials to outlets, not keeping pace with the growing demand. The purpose of this research is to find out the optimal time to distribute products to the destination and provide solutions using the Hungarian method and POM-QM software for Windows. Based on research that has been done on employee assignment analysis using the Hungarian method manually and POM QM software, the total delivery time of ready-to-process raw materials to each outlet before using the Hungarian method is 84 minutes or 1 hour 24 minutes. While the total delivery time of ready-to-process raw ...

Pandemi COVID-19 telah memperluas penerapan praktik remote working oleh karena itu manajemen penugasan yang efisien dalam lingkungan remote working sangat penting untuk menjaga produktivitas dan mendukung kesejahteraan karyawan. Tujuan penelitian ini adalah meninjau dan menganalisis literatur yang ada mengenai penerapan Metode Hungarian dalam konteks remote working agar dapat mengetahui kelebihan dan tantangannya. Penelitian ini menggunakan studi literatur dengan mengkaji jurnal ilmiah dalam kurun waktu 10 tahun terakhir terkait tentang remote working dan penggunaan metode Hungarian. Metode Hungarian menyajikan pendekatan yang berharga untuk mengoptimalkan penetapan tugas di lingkungan remote working. Meskipun tantangan teknis seperti hambatan komunikasi, keterbatasan ruang, isolasi sosial, risiko keamanan siber, dan masalah integrasi digital mungkin muncul.

Bulletin of Applied Industrial Engineering Theory, 2020

Masalah umum penugasan meliputi n tugas yang harus ditetapkan kepada m pekerja dimana setiap pekerja mempunyai kompetensi yang berbeda dalam menyelesaikan setiap tugas. Banyak penelitian telah dikembangkan untuk memecahkan masalah penugasan. Akan tetapi sebagian besar dari metode dikembangkan untuk masalah penugasan yang hanya mempertimbangkan satu tujuan. Masalah penugasan multi-objective adalah suatu masalah penugasan yang mempunyai beberapa tujuan pengoptimalan terhadap beberapa jenis sumber daya yang dimiliki oleh setiap pekerja untuk menyelesaikan setiap tugas. Penelitian ini bertujuan untuk mencari pendekatan dalam memecahkan masalah penugasan multi-objective dengan metode Hungaria guna memperoleh hasil penugasan yang optimal maupun penugasan dengan arah ideal, yaitu menetapkan setiap tugas sehingga setiap pekerja memiliki rata-rata loading atau dapat menyelesaikan tugas dengan besar sumber daya yang hampir sama . Contoh kasus pada penelitian ini menggunakan data primer yang d...

Jurnal Pendidikan Matematika

Pemrograman linier merupakan salah satu ilmu matematika terapan yang bertujuan untuk mencari nilai optimum dari suatu permasalahan, yang dirumuskan dalam model matematika. Salah satu aplikasinya adalah adalahmencari nilai optimum masalah penugasan (memaksimalkan penempatan tenaga kerja yang sesuai dengan kemampuannyaatau meminimalkan biaya penempatan tenaga kerja). Penyelesaian masalah penugasan bisa dilakukan denganMetode Hungarian. Selain Metode Hungarian, sudah banyak shoftware yang dapat digunakan untuk mengeksekusi masalahpenugasan, salah satu shoftware tersebut adalah LINGO. Kata kunci: metode penugasan, Hungarian, LINGO.

Pemrograman Linier disingkat PL merupakan metode matematik dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimumkan keuntungan dan meminimumkan biaya. PL banyak diterapkan dalam masalah ekonomi, industri, militer, social dan lain-lain. PL berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematik yang terdiri dari sebuah fungsi tujuan linier dengan beberapa kendala linier. Masalah transportasi berkaitan dengan keterbatasan sumber daya atau kapasitas perusahaan yang harus didistribusikan ke berbagai tujuan, kebutuhan atau aktivitas. Dengan demikian manfaat utama dari mempelajari masalah transportasi ini adalah mengoptimalkan distribusi sumberdaya tersebut sehingga mendapatkan hasil atau biaya yang optimal. Masalah penugasan (assignment problem), seperti juga masalah transportasi merupakan suatu kasus khusus yang ditemui dalam pemrograman linear. Permasalahan penugasan atau assignment problem adalah suatu persoalan dimana harus melakukan penugasan terhadap sekumpulan orang yang kepada sekumpulan job yang ada, sehingga tepat satu orang yang bersesuaian dengan tepat satu job yang ada. Misalkan setiap 4 orang dengan 4 job yang ada menghasilkan 4! yaitu 24 kemungkinan yang ada. Namun yang dicari disini atau fungsi objektifnya adalah mencari biaya seminimum mungkin sehingga dalam penugasan ini bagi orang yang melakukan penugasan dapat mengeluarkan biaya seminimum mungkin. Walaupun untuk menyelesaikan masalah penugasan ini dapat digunakan metode numeratif ataupun metode transportasi, tetapi lebih disarankan untuk digunakan metode Hungarian. Metode Hungarian dikembangkan oleh seorang ahli matematika berkebangsaan Hungaria yang bernama D Konig pada tahun 1916. B. Permasalahan Dalam masalah penugasan, kita akan mendelegasikan sejumlah tugas (assignment) kepada sejumlah penerima tugas (assignee) dalam basis satu-satu sehingga mendapatkan keuntungan yang maksimal atau kerugian yang minimal. C. Tujuan Tujuan yang akan dicapai dengan menyelesaikan masalah ini adalah berusaha untuk menjadwalkan setiap assignee pada suatu assigment sedemikian rupa sehingga kerugian yang ditimbulkan minimal atau keuntungan yang didapat maksimal. Yang dimaksud dengan kerugian dalam masalah ini adalah biaya dan waktu, sedangkan yang termasuk keuntungan adalah pendapatan,laba, dan nilai kemenangan.

Loading Preview

Sorry, preview is currently unavailable. You can download the paper by clicking the button above.

vanillavans, 2021

JURNAL ILMIAH SAINS, 2011

LAPRAK ADDER, 2019

JURNAL MATEMATIKA MURNI DAN TERAPAN EPSILON

Jurnal Serambi Engineering

Jurnal Matematika Integratif, 2016

Related topics

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Computer Science
• Academia ©2024