Combinatorial Optimization: Algorithms, Structures, Applications, II.  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
60802
Type K
Principal investigator Frank, András
Title in Hungarian Kombinatorikus Optimalizálás: Algoritmusok, Struktúrák, Alkalmazások, II.
Title in English Combinatorial Optimization: Algorithms, Structures, Applications, II.
Keywords in Hungarian Polinomiális algoritmusok, Gráfok összefüggősége, Matroidok és szubmoduláris függvények, Paritás, Poliéderes módszerek
Keywords in English Polynomial algorithms, Connectivity of graphs, Matroids and submodular functions, Parity, Polyhedral methods
Discipline
Mathematics (Council of Physical Sciences)100 %
Panel Mathematics and Computing Science
Department or equivalent Department of Operations Research (Eötvös Loránd University)
Participants Bárász, Mihály
Bernáth, Attila
Fekete, Zsolt
Fleiner, Balázs
Fleiner, Tamás
Jordán, Tibor
Jüttner, Alpár
Király, Tamás
Király, Zoltán
Kovácsné Becker, Johanna Cecília
Lovász, László
Makai, Márton
Pap, Gyula
Pap, Júlia
Recski, András
Szabadka, Zoltán
Szabó, Jácint
Szegő, László
Vaik, Zsuzsanna
Végh, László
Starting date 2006-02-01
Closing date 2010-08-31
Funding (in million HUF) 18.760
FTE (full time equivalent) 23.42
state closed project
Summary in Hungarian
A kombinatorikus optimalizálás fő célja olyan eljárások kidolgozása, amelyekkel egy véges, bár jellemzően igen nagy halmazból annak előírt tulajdonságú vagy legjobb elemét lehet kiválasztani. A méretek nagysága miatt az esetek teljeskörű számbavétele szóba se jöhet. A kialakult két irányzat egyike a heurisztikus eljárásoké, míg a másik vonulat olyan hatékony algoritmusok kifejlesztését célozza, melyek bizonyíthatóan a legjobb megoldást adják. E megközelítés prototípusa az 1955-ben H.W. Kuhn által kidolgozott és Magyar Módszernek elnevezett eljárás, amely Kőnig D. és Egerváry J. eredményein alapul. A területről széleskörű áttekintést ad A. Schrijver Combinatorial Optimization című háromkötetes, enciklopédikus igényű könyve (Springer, 2003). Az Egerváry Kutatócsoport (EGRES) ennek szellemében a problémák strukturális és algoritmikus elemzésére törekszik, különös tekintettel polinomiális futásidejű algoritmusok kifejlesztésére. Dolgozunk például Lovász matroid-paritás elméletének széleskörű alkalmazhatóságán. Algoritmust fejlesztünk Mader A-utas tételére, az útpárosítási problémára, Nebesky max-génusz tételére. Bekapcsolódunk szubmoduláris függvényekre támaszkodó approximációs algoritmusok kifejlesztésébe. Központi feladat változós mátrixok rangjának meghatározása determinisztikusan, hiszen számos nehéz kombinatorikus probléma ilyen alakba önthető (pl. duál-kritikus gráfok, egzakt párosítások, 3-dimenziós merevség).
Summary
The main goal of combinatorial optimization is to develop procedures to find an element of prescribed property or the best one in a finite but typically very large set. Due to the enormous sizes, a complete enumeration is out of question. One of the two main directions investigates heuristic algorithms while the other one concentrates on developing efficient algorithms for finding the provably best solution. A prototype of this approach was developed, and called the Hungarian Method, by H. Kuhn in 1955. This is based on results of D. Kőnig and J. Egerváry. The encyclopedic book Combinatorial Optimization by A. Schrijver (Springer, 2003) gives an in-depth overview of this type of results. The Egerváry Research Group (EGRES) by working in the spirit of Schrijver's book intends to attack the structural and algorithmic aspects of the problems, with special emphasis on developing polynomial time algorithms. For example, we are working on the wider applicability of the matroid parity theory of Lovász. Algorithms are under construction for the A-path theorem of Mader, for the path-matching problem, for the max genus theorem of Nebesky. We plan to join researches in approximation algorithms based on submodular functions. A central task is determining deterministically the rank of a matrix with indeterminates: several difficult combinatorial problems may be cast into this form (e.g. dual-critical graphs, exact matchings, 3-dimensional rigidity).




 

Final report

  
Results in Hungarian
Az Egerváry Jenő Kutatócsoport (EGRES) a szóbanforgó kutatási periódusban több, mint 60 folyóiratcikket publikált, további 40 dolgozat jelent meg konferenciakötetben illetve technical reportként. Egy 600 oldalas könyv is elkészült, amely az Oxford University Pressnél jelenik meg 2011 márciusában. Kutatóink számos díjban részesültek (Szent-Györgyi, Erdős, Prima Junior, 2 Akadémiai Ifjúsági, 2 Grünwald, Farkas). Két jelentős konferencián egy-egy kutatónk legjobb cikk díjban részesült. A kutatási tervben megfogalmazott irányokban több áttörés történt. Ezek közül az egyik legfontosabb az irányítatlan gráfok pontösszefüggőségének eggyel való optimális növelésének megoldása. Tisztán kombinatorikus algoritmus született az irányított változatra. Konstruktív karakterizációt bizonyítottunk (k,l)-összefüggő digráfokra. Kidolgoztuk a diszjunkt fenyő tétel egy igen általános kiterjesztését. Jelentős a Mader féle A-utak hatékony megkeresésére kidolgozott algoritmus. Nem kevésbé fontosak a gráfok párosítás-elméletének klasszikus tételeit nagymértékben általánosító eredmények részgráfok pakolásáról. Gráfok merevségével kapcsolatos kutatásaink különösen eredményesnek bizonyultak. Új felső korlát született a 3-dimenziós merevségi matroid rangjára, két dimenzióban jellemzés született a globális merevségre, és sikerült Lovász és Yemini egy korábbi eredményét is kiterjeszteni. Stabil párosítások területén a meglévőknél sokkal hatékonyabb és egyúttal egyszerűbb közelítő algoritmust adtunk.
Results in English
In the given period, the Egerváry Research Group (EGRES) published more than 60 papers in journals, and 40 further works in conference proceedings or technical reports. A book of more than 600 pages will appear at Oxford University Press in March 2011. Our researchers obtained several prizes (Szent-Györgyi, Erdős, Prima Junior, 2 Akadémiai Ifjúsági, 2 Grünwald, Farkas). They obtained best paper awards at two relevant conferences. We achieved breakthroughs in several areas outlined in the research plan. One of the most important is a solution to the problem of increasing optimally the connectivity of an undirected graph by one. A similarly important result is a combinatorial algorithm for directed connectivity augmentation. We gave a constructive characterization of (k,l)-connected digraphs, and worked out a generalization of the arborescence packing theorem. Another significant development is an efficient algorithm for Mader's disjoint A-paths. No less important are the new results on subgraph packing that generalize classical theorems of matching theory. Our research on rigidity proved particularly fruitful. New upper bounds were found for the rank of the 3-dimensional rigidity matroid, a characterization for 2-dimensional global rigidity was derived, and an earlier result of Lovász and Yemini has been extended. In the area of stable matchings, we developed an approximation algorithm which is simpler and much more efficient than the earlier ones.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=60802
Decision
Yes





 

List of publications

  
Fekete Zs: Gráfok és rúdszerkezetek merevsége, Ph.D. disszertáció, ELTE Matematika Doktori Iskola, 2007
Jüttner A: Parametric problems in combinatorial optimization and their applications in telecommunications, Ph.D. thesis, ELTE Mathematics Doctoral School, 2007
Pap Gy: A constructive approach to matching and its generalizations, Ph.D. thesis, ELTE Mathematics Doctoral School, 2007
Szabó J: Graph packings and the degree prescribed subgraph problem, Ph.D. thesis, ELTE Mathematics Doctoral School, 2007
Fleiner T: On stable matchings and flows, EGRES Technical Report No. 2009-11, 2010
Király T: Oriented matroids from set-pairs, EGRES Quick Proof No. 2006-02, 2006
Király T: Applications of Eulerian splitting-off, EGRES Technical Report No. 2007-01, 2007
Király T: Minimal feedback sets in binary oriented matroids, EGRES Quick Proof No. 2006-01, 2006
Szabó J: Matroid parity and the local augmentation property of jump systems, EGRES Technical Report No. 2006-09, 2006
Bernáth A: Hardness results for well-balanced orientations, EGRES Technical Report No. 2006-05, 2006
Bernáth A; Iwata S; Király T; Király Z; Szigeti Z: Recent results on well-balanced orientations, Discrete Optimization 5 (2008), 663-676, 2008
Fekete Zs; Jordán T: Uniquely localizable networks with few anchors, S. Nikoletseas and J.D.P. Rolim (Eds.): ALGOSENSORS 2006, Springer LNCS 4240, 176-183, 2006
Király Z; Szigeti Z: Simultaneous well-balanced orientations of graphs, Journal of Combinatorial Theory Ser. B 96, 684-692, 2006
Frank A; Király Z; Kotnyek B: An Algorithm for Node-Capacitated Ring Routing, Operations Research Letters 35, Issue 3, 385-391, 2007
Király Z; Szigeti Z: Reliable Orientations of Eulerian Graphs, EGRES Technical Report No. 2006-01, 2006
Frank A; Lau LC; Szabó J: A note on degree-constrained subgraphs, Discrete Math, 308, 2647-2648, 2008
Frank A: Rooted k-connections in digraphs, Discrete Appl. Math 157, 1242-1254, 2009
Biró P; Cechlárová K; Fleiner T: The dynamics of stable matchings and half-matchings for the stable marriage and roommates problems, International Journal of Game Theory 36, 333-352, 2008
Jackson B, Jordán T: Rigid components in molecular graphs, Algorithmica Volume 48, Number 4, 399-412, 2007
Jackson B, Jordán T: Rank and independence in the rigidity matroid of molecular graphs, EGRES Technical Report No. 2006-02, 2006
Pap Gy: Mader matroids are gammoids, EGRES Quick Proof No. 2006-17, 2006
Pap Gy: Some New Results on Node-Capacitated Packing of A-paths, Proceedings of STOC 2007, June 11-13, San Diego, 2007
Makai M, Pap Gy, Szabó J: Matching Problems in Polymatroids without Double Circuits, Proceedings of IPCO 2007, LNCS 4513, 167-181., 2007
Pap Gy: Combinatorial algorithms for matchings, even factors and square-free 2-factors, Mathematical Programming Ser. B, Volume 110, Issue 1, 57-69., 2007
Pap Gy: Packing non-returning A-paths, Combinatorica, Volume 27, Issue 2 (2007), 247-251., 2007
Pap Gy, Szegő L: Matchings of Cycles and Paths in Directed Graphs, Combinatorica, Vol 27, Issue 3, 2007, 383-398., 2007
Makai M, Szabó J: The parity problem of polymatroids without double circuits, Combinatorica 28, 679-692, 2008
Makai M: On maximum cost K_{T,T}-free T-matchings of bipartite graphs, SIAM J. Discrete Math. 21 No. 2, 349-360., 2007
Bernáth A, Gerbner D: Chain intersecting families, Graphs and Combinatorics 23, No. 4, 353-366, 2007
Bernáth A: A representation for intersecting families, Matematikai Lapok New Series 13, 6-12, 2007
Bernáth A: Source location in undirected and directed hypergraphs, Operation Research Letters 36, No 3, 355-360, 2008
Bernáth A, Joret G: Well-balanced orientations of mixed graphs, Information Processing Letters 106 No 4, 149-151, 2008
Király Z: $\lambda$-supermodular functions and dual packing theory, Proc. 5th Hungarian-Japanese Symposium on Discrete Mathematics, 2007
Becker J, Csizmadia Zs, Laugier A, Szabó J, Szegő L: Balancing congestion for unsplittable routing on a bidirected ring, beküldve, 2007
Szabó J: Éldiszjunkt útrendszer kiterjesztése, Alk. Mat. Lapok 25, 119--129., 2008
Szabó J: Upgrading edge-disjoint paths in a ring, beküldve, 2007
Szabó J: Packing a graph with leaf-degree constrained trees, Graphs and Combin. 24, 485-494, 2008
Király T; Lau LC: Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs, Journal of Combinatoral Theory B, 98 (2008), 1233-1252, 2008
Király T, Pap J: Total dual integrality of Rothblum's description of the stable marriage polyhedron, Mathematics of Operations Research, 33(2) (2008), 283-290, 2008
Király T: A result on crossing families of odd sets, EGRES Technical Report no. 2007-10, 2007
Király T, Lau LC: Degree constrained submodular flows, EGRES Technical Report no. 2007-09, 2007
Király T, Pap J: A note on kernels in h-perfect graphs, EGRES Technical Report no. 2007-03, 2007
Király T: Élösszefüggőség-növelés hiperélek összevonásával, Matematikai Lapok 13, 28-31, 2007
Király T, Makai M: Irányított hipergráfok élösszefüggőség-növelése, Matematikai Lapok 13, 32-39, 2007
Király T, Szabó J: Szupermoduláris függvényt fedő adott befok-paritású irányítások, Matematikai Lapok 13, 40-48., 2007
Fekete Zs, Szabó J: Fák egyenletes színezése, Matematikai Lapok 13, 13-22., 2007
Jüttner A: Az Egerváry algoritmus hatékonysága, Matematikai Lapok 13, 23-27., 2007
Pap Gy: Négyzetmentes 2-párosítások páros gráfokban, Matematikai Lapok 13, 49-56, 2007
Frank A, Végh AL: Kombinatorikus algoritmus pontösszefüggőség eggyel való növelésére, Matematikai Lapok 13, 57-67, 2007
Fleiner T: The stable roommates problem with choice functions, Algorithmica 58, 82-101, 2010
Bernáth A, Király T: Covering skew-supermodular functions with hyperedges of minimum total size, Operations Research Letters, Volume 37, Issue 5, 345-350, 2009
Király T, Pap J: Kernels, stable matchings, and Scarf's Lemma, RIMS Kokyuroku Bessatsu (beküldve), 2008
Frank A, Király T: A survey on covering supermodular functions, Research Trends in Combinatorial Optimization, W.J. Cook, L. Lovász, J. Vygen, eds., Springer (2009), pp. 87-126., 2009
Király T, Lau LC, Singh M: Degree bounded matroids and submodular flows, Proceedings of 13th International Conference IPCO 2008, LNCS 5035, 259-272., 2008
Bernáth A, Király T: A new approach to splitting-off, Proceedings of 13th International Conference IPCO 2008, LNCS 5035, 401-415., 2008
Jackson B, Jordán T: On the rigidity of molecular graphs, Combinatorica 28 (6), 645-658, 2008
Jackson B, Jordán T: Pin-collinear body-and-pin frameworks and the molecular conjecture, Discrete and Computational Geometry 40: 258-278, 2008
Bang-Jensen J, Jordán T: On persistent directed graphs, Networks, Vol. 52, Issue 4, 271-276, December 2008., 2008
Pap J: Recognizing conic TDI systems is hard, Math Programming, available Online, 2009
Szabó J: Good characterizations for some degree constrained subgraphs, Journal of Combinatorial Theory Ser B 99 (2009) 436-446, 2009
Király T, Szabó J: A note on parity constrained orientations, Combinatorica Volume 29, Number 5, 619-628, 2009
Szabó J: Matroid parity and jump systems: a solution to a conjecture of Recski, SIAM J. of Disc. Math 22, 854-860, 2008
Bernáth A, Bruhn H: Degree constrained orientations in countable graphs, Electronic J. Comb, Vol 15, No 1., 2008
Frank A: Összefüggések a kombinatorikus optimalizálásban, I. Optimalizálás gráfokon, Matematikai Lapok, Vol 1 (2008), 20-76, 2008
Frank A: Összefüggések a kombinatorikus optimalizálásban, II. Szubmoduláris optimalizálás és poliéderes kombinatorika, Matematikai Lapok, megjelenés alatt, 2008
Frank A, Végh L: An algorithm to increase the node-connectivity of a digraph by one, Discrete Optimization, Vol 5 (2008), 677-684, 2008
Bérczi K, Frank A: Variations for Lovász' submodular ideas, Building Bridges Between Mathematics and Computer Science, Bolyai Soc., Ser Math Studies, 19, 137-164, 2008
Bérczi K, Frank A: Packing Arborescences, beküldve, 2008
Pap Gy: Strongly polynomial time solvability of integral and half-integral node-capacitated multiflow problems, EGRES Technical Report No. 2008-12, 2008
Gijswijt D, Pap Gy: An algorithm for weighted fractional matroid matching, EGRES Technical Report No. 2008-11, 2008
Pap Gy: A matroid intersection algorithm, EGRES Technical Report No. 2008-10, 2008
Pap Gy: Weighted Restricted 2-Matching, Mathematical Programming, Ser. B, (2008), 2008
Pap Gy: Packing non-returning A-paths algorithmically, Discrete Mathematics, Volume 308, Issue 8, (April 2008) 1472-1488, 2008
Kovács E R, Végh L: The constructive characterization of (k,l)-edge-connected digraphs, EGRES Technical Report No. 2008-14, 2008
Király, Z: Better and Simpler Approximation Algorithms for the Stable Marriage Problem, ESA 2008, Lecture Notes in Computer Science 5193, (2008), pp. 623-634, 2008
Dvorak Z , Jendrol S, Kral D, Pap Gy: Matchings and Nonrainbow Colorings, SIAM Journal on Discrete Mathematics, (2009), 23/1, 344-348, 2009
Végh L, Benczúr A: Primal-dual approach for directed vertex connectivity augmentation and generalizations, ACM Transactions on Algorithms, 4(2), Article no. 20, 2008
Kovács E R, Végh L: Constructive Characterization Theorems in Combinatorial Optimization, RIMS Kokyuroku Bessatsu (beküldve), 2008
Bérczi K, Fujishige S, Kamiyama N: A Linear-Time Algorithm to Find a Pair of Arc-disjoint Spanning In-arborescence and Out-arborescence in a Directed Acyclic Graph, RIMS Kokyuroku Bessatsu (beküldve), 2008
Fleiner T, Irwing RW, Manlove DF: An algorithm for a super-stable roommates problem, EGRES Technical Report No. 2008-06, 2008
Kano M, Katona GY, Szabó J: Elementary Graphs with Respect to f Parity Factors, Graphs and Combinatorics 25, 717-726, 2009
Janata M, Szabó J: The superstar packing problem, Combinatorica 29, 27-48, 2009
Király Z, Szabó J: Induced graph packing problems, Graphs and Combinatorics 26, 243-267, 2010
Kobayashi Y, Szabó J, Takazawa K: A proof to Cunningham's conjecture on restricted subgraphs and jump systems, EGRES Technical Report No. 2010-04, 2010
Makai M: Parity problems of combinatorial polymatroids, PhD dissertation, ELTE Mathematics Doctoral Program, 2009
Bernáth A: Edge-connectivity augmentation of graphs and hypergraphs, PhD dissertation, ELTE Mathematics Doctoral Program, 2010
Végh L: Connectivity augmentation algorithms, PhD dissertation, ELTE Mathematics Doctoral Program, 2010
Bernáth A: A simple proof of a theorem of Benczúr and Frank, EGRES Technical Report No. 2009-02, 2009
Bernáth A, Grappe R, Szigeti Z: Covering a symmetric crossing supermodular function with partition constraints, Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA10), 2010
Bernáth A, Grappe R, Szigeti Z: Augmenting the edge-connectivity of a hypergraph by adding a multipartite graph, Electron. Notes Discrete Math. 34, 173-177, 2009
Bernáth A: Node-to-area connectivity augmentation of hypergraphs without increasing the rank, EGRES Quick Proof No. 2009-02, 2009
Bernáth A, Király Z: Finding edge-disjoint subgraphs in graphs, EGRES Quick Proof No. 2010-04, 2010
Király Z: Better and Simpler Approximation Algorithms for the Stable Marriage Problem, Algorithmica, available online, 2009
Bérczi K, Végh LA: Restricted b-matchings in degree-bounded graphs, Springer LNCS, Proceedings of the 14th Conference on Integer Programming and Combinatorial Optimization (IPCO XIV), 43-56, 2010
Végh LA: Augmenting undirected node-connectivity by one, Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), 563-572, 2010
Jordán T, Recski A, Szabadka Z: Rigid tensegrity labelings of graphs, European J. Combinatorics 30, 1887-1895, 2009
Jordán T, Szabadka Z: Operations preserving the global rigidity of graphs and frameworks in the plane, Computational Geometry, 42, 511-521., 2009
Jackson B, Jordán T: A sufficient connectivity condition for generic rigidity in the plane, Discrete Applied Mathematics 157, 1965-1968., 2009
Jackson B, Jordán T: The generic rank of body-bar-and-hinge frameworks, European J. Combinatorics 31, 574-588., 2010
Jackson B, Jordán T: Globally rigid circuits of the direction-length rigidity matroid, J. Combinatorial Theory, Ser. B., Vol. 100, 1-22, 2010
Jackson B, Jordán T: Brick partitions of graphs, Discrete Mathematics, Vol. 310, no. 2, pp. 270-275., 2010
Jackson B, Jordán T: Inductive constructions in the analysis of two-dimensional rigid structures, 6th Japanese Hungarian symposium on discrete mathematics and its applications, Budapest, May 2009, 131-140., 2009
Jordán T: Generically globally rigid zeolites in the plane, Information Proc. Letters, Vol. 110, Issues 18-19, Pages 841-844., 2010
Connelly R, Jordán T, Whiteley W: Generic global rigidity of body-bar frameworks, EGRES Technical Report No. 2009-13, 2009
Bérczi K, Frank A: Disjoint Arborescences, RIMS Kokyuroku Bessatsu, to appear, 2009
Fleiner T, Frank A: A quick proof for the cactus representation of mincuts, EGRES Quick Proof No. 2009-03, 2009
Frank A: Connections in Combinatorial Optimization, Oxford University Press, to appear in March 2011, 2011



Back »