Models and Algorithms for Combinatorial Problems in Information Technology  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
81493
Type K
Principal investigator Tuza, Zsolt
Title in Hungarian Modellek és algoritmusok a műszaki informatikában felmerült kombinatorikus problémákra
Title in English Models and Algorithms for Combinatorial Problems in Information Technology
Keywords in Hungarian hálózat, gráf, hipergráf, felbontás, ütemezés, folyamatgráf, erőforrás allokáció
Keywords in English network, graph, hypergraph, partition, scheduling, process graph, resource allocation
Discipline
Electro-technology (Council of Physical Sciences)100 %
Ortelius classification: Computer electronics
Panel Informatics and Electrical Engineering
Department or equivalent Department of Computer Science and Systems Technology (University of Pannonia)
Participants Bertók, Botond
Bujtás, Csilla
Starting date 2010-02-01
Closing date 2013-12-31
Funding (in million HUF) 12.236
FTE (full time equivalent) 5.74
state closed project
Summary in Hungarian
A műszaki informatikában nagy számban merülnek fel olyan problémák, amelyek véges matematikai struktúrákkal modellezhetők. Hogy csak egyetlen példát említsünk, a számítógépes és kommunikációs hálózatok természetes módon reprezentálhatók gráfokkal. Az elméleti megközelítés lehetővé teszi, hogy a problémákat igen precízen elemezzük, olyan feltételeket találjunk, amelyek biztosítják megengedett megoldások létezését és garantálják a megoldások minőségét, továbbá hogy megértsük a mennyiségi és szerkezeti tulajdonságok között fennálló összefüggéseket. További alapvető kérdés az algoritmusok hatékonysága, ami "offline" és "online" helyzetben is felmerül. A tervezett kutatások során ezeket az irányokat és a hozzájuk kapcsolódó kérdéseket kívánjuk vizsgálni. Munkánkat jelentős nemzetközi kooperációban végezzük (legfontosabb partnereinkre a pályázat egyéb helyein utalunk). Meglévő tudományos hátterünk és partnereink szakértelme alapján jó esély van rá, hogy a különféle módszerek alkalmazásával olyan eredményekre jutunk, amelyek eltérő területekből profitálnak, mint például a diszkrét matematika, számítástudomány, diszkrét optimalizálás és operációkutatás.
Summary
In modern Information Technology, a large number of problems arise which can be modeled with discrete mathematical structures. Just to mention one characteristic field, computer and communication networks can be represented with graphs in a natural way. Theoretical approach makes it possible to analyze problems in a very precise way, to find conditions which ensure the existence of feasible solutions and guarantee the quality of solutions, and also to understand connections between quantitative and structural properties. A further issue of essence is algorithmic efficiency, which occurs in offline and online settings, too. In the proposed study we plan to explore these directions and some related ones. We carry out this research in strong international cooperation (our most important partners will be mentioned in other parts of the application). Due to our background and the expertise of our collaborators, there are good chances that different methodologies can be applied to derive results benefiting from various fields, for example discrete mathematics, computer science, discrete optimization and operations research.




 

Final report

  
Results in Hungarian
A folyamattervezés és optimalizálás terén kombinatorikus algoritmusokat terveztünk és implementáltunk különféle alkalmazási területeken (gyártórendszerek ütemezése, jármű hozzárendelési feladatok). Eljárásokat alkottunk, melyek egyrészt becslik a felépítés alatt álló folyamat megbízhatóságát, másrészt redundanciák beépítésével automatikusan növelik annak értékét. A gráf algoritmusok és matematikai programozási feladat megoldási lépései kölcsönösen hasznosítják egymás eredményeit, így javítva eredményességüket. A kombinatorikus struktúrák algoritmusainál tanulmányoztuk a polinom idejű eljárások korlátait, a pontos számításokban és a közelítőleges optimalizálásban egyaránt. Vizsgálataink kiterjedtek a halmazrendszereknek általánosan megfogalmazható korlátozó feltételek melletti partícionálására, dominálására és lefogására. Számos olyan pontot mutattunk ki, ahol a kiszámítási bonyolultság átlép egy magasabb komplexitási osztályba. Gráfokon olyan csúcs- és élpartíciókat vizsgáltunk, amelyekkel a hálózatok egymástól elszeparálódó részeit tudjuk modellezni bizonyos típusú link- illetve csomópontbeli meghibásodások esetén. A titkosított visszakeresést biztosító adattárolás egy kombinatorikus modelljében oldottunk meg nyitott problémákat a szerverek összterheltségének minimális méretére és a kapcsolódó optimális adatelrendezésre vonatkozóan. Néhány eredményünkkel több évtizede nyitott problémákat oldottunk meg.
Results in English
We have constructed and implemented combinatorial algorithms for various fields of process design and optimization, e.g., scheduling of manufacturing systems and vehicle assignment problems. We have designed procedures, which estimate the reliability of the process under construction, and also increase its value by incorporating redundancies. The steps of graph algorithms and the solutions of mathematical programming tasks cooperatively utilize the results of each other, improving the overall productivity. Concerning algorithms on combinatorial structures, we have studied the limitations of polynomial-time procedures, both in exact computation and approximate optimization. We have dealt with partitioning of set systems under restrictive conditions formulated in a general way, and also with their domination and covering. We have identified several points where computational complexity jumps to a higher problem class. On graphs we have studied vertex- and edge-partitions which provide us with models of parts becoming separated in networks as a consequence of link or node failure. In a combinatorial model of distributed data storage that ensures secure data retrieval, we have solved open problems on the minimum total load of servers and on the corresponding optimal arrangements of data. With some of our results we have solved problems which were open for several decades
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=81493
Decision
Yes





 

List of publications

  
M. Barany, B. Bertok, Z. Kovacs, F. Friedler and L. T. Fan: Optimization software for solving vehicle assignment problems to minimize cost and environmental impact of transportation, Chemical Engineering Transactions, 21, 499-504, 2010
Cs. Bujtás, E. Sampathkumar, Zs. Tuza, L. Pushpalatha and Vasundhara R. C.: Improper C-colorings of graphs, Discrete Applied Mathematics, 159, 174-186, 2011
S. Aparna Lakshmanan, Cs. Bujtás and Zs. Tuza: Small edge sets meeting all triangles of a graph, Graphs and Combinatorics, 28, 381-392, 2012
K. Kalauz, Z. Süle, B. Bertok, F. Friedler and L. T. Fan: Generation of redundant structures to guarantee predefined level of reliability in business processes, VOCAL 2010 (Veszprém Optimization Conference: Advanced Algorithms), Veszprém, Hungary, December 13-15, 2010
B. Bertok, K. Kalauz, Z. Süle, L. T. Fan and F. Friedler: Algorithmic synthesis of process networks with time constraints by the P-garph framework, VOCAL 2010 (Veszprém Optimization Conference: Advanced Algorithms), Veszprém, Hungary, December 13-15, 2010
M. Barany, B. Bertok, L. T. Fan and F. Friedler: Relationship between extreme pathways and structurally minimal pathways, Bioprocess and Biosystems Engineering, 36, 1199-1203, 2013
K. Kalauz, Z. Sule, B. Bertok, F. Friedler and L. T. Fan: Reliability analysis of business processes via the P-graph framework, International Conference on Computational Management Science, Vienna, Austria, July 28-30, 2010
B. Bertok, R. Adonyi, F. Friedler and L. T. Fan: Superstructure approach to batch process scheduling by S-graph Representation, Computer-Aided Chemical Engineering, 29, 1105-1109, 2011
M. Barany, B. Bertok, Z. Kovacs, F. Friedler and L. T. Fan: Solving vehicle assignment problems by process-network synthesis to minimize cost and environmental impact of transportation, Clean Technologies and Environmental Policy, 13, 637-642, 2011
M. Barany, B.Bertok, C. Imreh, L. T. Fan and F. Friedler: On the equivalence of direct mechanisms and structurally minimal pathways, Journal of Mathematical Chemistry, 50, 1347-1361, 2012
Cs. Bujtás and Zs. Tuza: Combinatorial batch codes: Extremal problems under Hall-type conditions, Electronic Notes in Discrete Mathematics, 38, 201-206, 2011
Cs. Bujtás and Zs. Tuza: Relaxations of Hall's Condition: Optimal batch codes with multiple queries, Applicable Analysis and Discrete Mathematics, 6, 72-81, 2012
G. Bacsó and Zs. Tuza: Optimal guard sets and the Helly property, European Journal of Combinatorics, 32, 28-32, 2011
C. Bazgan, S. Toubaline and Zs. Tuza: Complexity of most vital nodes for Independent Set in graphs related to tree structures, Lecture Notes in Computer Science 6460, 154-166, 2011
C. Bazgan, S. Toubaline and Zs. Tuza: The most vital nodes with respect to Independent Set and Vertex Cover, Discrete Applied Mathematics, 159, 1933-1946, 2011
G. Bacsó and Zs. Tuza: Distance domination versus iterated domination, Discrete Mathematics, 312, 2672-2675, 2012
Cs. Bujtás, Gy. Dósa, Cs. Imreh, J. Nagy-György and Zs. Tuza: The Graph-Bin Packing Problem, International Journal of Foundations of Computer Science, 22, 1971-1993, 2011
Cs. Bujtás and Zs. Tuza: Maximum number of colors: C-coloring and related problems, Journal of Geometry 101, 83-97, 2011
Cs. Bujtás and Zs. Tuza: Optimal batch codes: Many items or low retrieval requirement, Advances in Mathematics of Communications, 5, 529-541, 2011
Cs. Bujtás and Zs. Tuza: Optimal combinatorial batch codes derived from dual systems, Miskolc Mathematical Notes, 12, 11–23, 2011
Cs. Bujtás, E. Sampathkumar, Zs. Tuza, Ch. Dominic and L. Pushpalatha: 3-consecutive edge coloring of a graph, Discrete Mathematics, 312, 561-573, 2012
Cs. Bujtás, E. Sampathkumar, Zs. Tuza, Ch. Dominic and L. Pushpalatha: Vertex coloring without large polychromatic stars, Discrete Mathematics, 312, 2102-2108, 2012
Cs. Bujtás, M. A. Henning and Zs. Tuza: Transversals and domination in uniform hypergraphs, European Journal of Combinatorics, 33, 62-72, 2012
V. Borozan, S. Fujita, A. Gerek, C. Magnant, Y. Manoussakis, L. Montero and Zs. Tuza: Proper connection of graphs, Discrete Mathematics 312, 2550-2560, 2012
I. Szalkai, Gy. Dosa, Zs. Tuza and B. Szalkai: On minimal solutions of systems of linear equations with applications, Miskolc Mathematical Notes, 13, 529-541, 2012
G. Szederkényi, K. M. Hangos and Z Tuza: Finding weakly reversible realizations of chemical reaction networks using optimization, MATCH - Communications in Mathematical and in Computer Chemistry, 67, 193-212, 2012
D. W. Cranston, A. Pruchnewski, Zs. Tuza and M. Voigt: List colorings of K5-minor-free graphs with special list assignments, Journal of Graph Theory, 71, 18-30, 2012
Zs. Tuza: Choice-perfect graphs, Discussiones Mathematicae Graph Theory, 33, 231-242, 2013
A. Kemnitz, M. Marangio and Zs. Tuza: [1,1,t]-colorings of complete graphs, Graphs and Combinatorics, 29, 1041-1050, 2013
Gy. Dósa, Zs. Tuza and D. Ye: Bin packing with "Largest In Bottom" constraint: Tighter bounds and generalizations, Journal of Combinatorial Optimization, 26, 416-436, 2013
A. Benkő, Gy. Dósa and Zs. Tuza: Bin covering with a general profit function: approximability results, Central European Journal of Operations Research, 21, 805-816, 2013
J. Balogh, J. Békési, Gy. Dósa, H. Kellerer and Zs. Tuza: Black and white bin packing, Lecture Notes in Computer Science 7846, 131-144, 2013
M. Hegyháti and Zs. Tuza: Colorability of mixed hypergraphs and their chromatic inversions, Journal of Combinatorial Optimization, 25, 737-751, 2013
J. Czap and Zs. Tuza: Decompositions of plane graphs under parity constraints given by faces, Discussiones Mathematicae Graph Theory, 33, 521-530, 2013
Cs. Bujtás: Domination game on trees without leaves at distance four, Proc. 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (A. Frank et al., eds.), June 4-7, 2013, Veszprém, Hungary, pp. 73-78, 2013
S. Arumugam, Bibin K. Jose, Cs. Bujtás and Zs. Tuza: Equality of domination and transversal numbers in hypergraphs, Discrete Applied Mathematics 161, 1859-1867, 2013
Cs. Bujtás, E. Sampathkumar, Zs. Tuza, Ch. Dominic and L. Pushpalatha: When the vertex coloring of a graph is an edge coloring of its line graph - A rare coincidence, Ars Combinatoria („közlésre elfogadva”), 2015
S. Aparna Lakshmanan, Cs. Bujtás and Zs. Tuza: Generalized line graphs: Cartesian products and complexity of recognition, („közlésre benyújtva”), 2015
Cs.Bujtás and Zs.Tuza: Color-bounded hypergraphs, VI: Structural and functional jumps in complexity, Discrete Mathematics 313, 1965-1977, 2013
Cs. Bujtás and Zs. Tuza: Approximability of the upper chromatic number of hypergraphs, („közlésre benyújtva”), 2015
Cs. Bujtás and Zs. Tuza: Maximum number of colors in hypertrees of bounded degree, („közlésre benyújtva”), 2015
Cs. Bujtás, M. A. Henning, Zs. Tuza and A. Yeo: Total transversals and total domination in uniform hypergraphs, („közlésre benyújtva”), 2015
Cs. Bujtás and Zs. Tuza: Turán numbers and batch codes, („közlésre benyújtva”), 2015
Gy. Dósa, R. Li, X. Han and Zs. Tuza: Tight absolute bound for First Fit Decreasing bin-packing: FFD(L) ≤ 11/9 OPT(L) + 6/9, Theoretical Computer Science 510, 13–61, 2013
Gy. Dosa, Z. Tan, Zs. Tuza, Y. Yan and C. Sik Lányi: Improved bounds for batch scheduling with nonidentical job sizes, („közlésre benyújtva”), 2015
P. Horak and Zs. Tuza: Speeding up deciphering by hypergraph ordering, Designs, Codes and Cryptography („közlésre elfogadva”), 2014
Zs. Tuza and Cs. Bujtás: Coloring problems on interval hypergraphs, Midsummer Combinatorial Workshop 2012, Prague, KAM-DIMATIA Series, 39-41, 2013



Back »