"Personaalne uurimistoetus" projekt PUT620
PUT620 "Biklikid - kombinatoorika, optimiseerimine ja kommunikatsioon (1.01.2015−31.12.2018)", Dirk Oliver Jim Theis, Tartu Ülikool, Loodus- ja täppisteaduste valdkond, Arvutiteaduse instituut.
PUT620
Biklikid - kombinatoorika, optimiseerimine ja kommunikatsioon
Bicliques -- Combinatorics, Optimization, and Communication
1.01.2015
31.12.2018
Personaalne uurimistoetus
Otsinguprojekt
ValdkondAlamvaldkondCERCS erialaFrascati Manual’i erialaProtsent
4. Loodusteadused ja tehnika4.4. MatemaatikaP110 Matemaatiline loogika, hulgateooria, kombinatoorika1.1. Matemaatika ja arvutiteadus (matemaatika ja teised sellega seotud teadused: arvutiteadus ja sellega seotud teadused (ainult tarkvaraarendus, riistvara arendus kuulub tehnikavaldkonda)50,0
4. Loodusteadused ja tehnika4.4. MatemaatikaP160 Statistika, operatsioonanalüüs, programmeerimine, finants- ja kindlustusmatemaatika 1.1. Matemaatika ja arvutiteadus (matemaatika ja teised sellega seotud teadused: arvutiteadus ja sellega seotud teadused (ainult tarkvaraarendus, riistvara arendus kuulub tehnikavaldkonda)25,0
4. Loodusteadused ja tehnika4.6. ArvutiteadusedP175 Informaatika, süsteemiteooria1.1. Matemaatika ja arvutiteadus (matemaatika ja teised sellega seotud teadused: arvutiteadus ja sellega seotud teadused (ainult tarkvaraarendus, riistvara arendus kuulub tehnikavaldkonda)25,0
PerioodSumma
01.01.2015−31.12.201563 600,00 EUR
01.01.2016−31.12.201663 600,00 EUR
01.01.2017−31.12.201763 600,00 EUR
190 800,00 EUR

Biklikid kahealuselistes graafides on kolme kombinatoorse matemaatika ja teoreetilise arvutiteaduse valdkonna ühisosas. Kommunikatsioonikeerukus: Lovász'i ja Saks'i log-astaku hüpotees on samaväärne küsimustega biklikikatete või kahealuseliste graafide biklikkide suuruste kohta. Kombinatoorne optimiseerimine: need mõisted on väga tähtsad hiljutistes tulemustes mõnede kombinatoorse optimiseerimise ülesannete lineaarse planeerimise formulatsioonis vajaminevate tõkete ja muutujate arvu kohta, näiteks rändkaupmehe ülesandes. Kombinatoorika: alles eelmisel aastal näidati, et P. Frankl'i kuulus ühendi suhtes kinnise hulga hüpotees on samaväärne küsimusega sisalduvuse mõttes maksimaalsete biklikkide kohta kahealuselises graafis. Me tahame rakendada ekstremaalse ja tõenäosusliku kombinatoorika lähenemist ja meetodeid biklikkide ja biklikikatete uurimiseks. Et uuritavad objektid on neil juhtudel muutunud üllatavalt sarnaseks, siis me loodame kõigi kolme probleemi uurimisel anda tugeva panuse.
Bicliques in bipartite graphs are at the intersection of three areas of combinatorial mathematics and theoretical computer science. Communication Complexity: The Log-Rank Conjecture by Lovász and Saks (1988) is equivalent to questions about biclique coverings of or sizes of bicliques in bipartite graphs. Combinatorial Optimization: These concepts are at the core of recent results on bounds on the number of constraints and variables a Linear Programming formulation for a given combinatorial optimization problem, e.g., the Traveling Salesman Problem, must have. Combinatorics: Only last year, Péter Frankl’s famous Union-Closed Sets Conjecture was shown to be equivalent to a question about inclusion-wise maximal bicliques in bipartite graphs. We want to apply approaches and tools of extremal and probabilistic combinatorics to the study of bicliques and biclique coverings. Since the objects of interest become stunningly similar, we hope to make significant contributions to all three problems.

Vastutav täitja (1)

IsikKraadTöökoht ja ametCVOsalemise periood
Dirk Oliver Jim TheisdoktorikraadTartu Ülikool, Matemaatika-informaatikateaduskond, Arvutiteaduse instituut, teoreetilise informaatika dotsent (1,00)EST / ENG01.01.2015−31.12.2018

Põhitäitjad (2)

IsikKraadTöökoht ja ametCVOsalemise periood
Kaveh KhoshkhahdoktorikraadEST / ENG01.01.2015−31.12.2018
Ago-Erik RietdoktorikraadTartu Ülikool, Matemaatika-informaatikateaduskond, Matemaatika Instituut, teadur (1,00)EST / ENG01.01.2015−31.12.2016

Täitjad (5)

IsikKraadTöökoht ja ametCVOsalemise periood
Bahman Ghandchi01.01.2016−31.12.2018
Kairi Kangro01.09.2015−30.06.2016
Abdullah MakkehEST / ENG01.01.2015−31.12.2018
Mozhgan PourmoradnasseriTartu Ülikool, Matemaatika-informaatikateaduskond, Arvutiteaduse instituut, Assistent (0,50)EST / ENG01.01.2015−31.12.2017
Karl Tarbemagistrikraad01.09.2015−30.06.2016
Publikatsioonid
Publikatsioonid
Lee, Jonathan; Riet, Ago-Erik. (2015). Graph Saturation Games. LAGOS 2015 proceedings: Latin-American Algorithms, Graphs and Optimization Symposium 2015, 10-15 May 2015, Praia das Fontes, Beberibe, Ceará, Brazil. Tartu Ülikool, x−x.
Lee, Jonathan; Riet, Ago-Erik (2015). F-Saturation Games. Discrete Mathematics, 338 (12), 2356−2362.10.1016/j.disc.2015.05.028.
Khoshkhah, Kaveh (2015). On finding orientations with the fewest number of vertices with small out-degree. Discrete Applied Mathematics, 194, 163−166.10.1016/j.dam.2015.05.007.
Friesen, Mirjam; Hamed, Aya; Lee, Troy; Theis, Dirk Oliver (2015). Fooling-sets and rank. European Journal of Combinatorics, 48, 143−153.10.1016/j.ejc.2015.02.016.
Visk, Kristo; Riet, Ago-Erik (2016). Generalisation of Kraft inequality for source coding into permutations. In: 2016 IEEE International Symposium on Information Theory (1237−1241). 2016 IEEE International Symposium on Information Theory: IEEE Xplore.10.1109/ISIT.2016.7541496.
Pulaj, Jonad; Raymond, Annie; Theis, Dirk Oliver (2016). New Conjectures for Union-Closed Families. Electronic Journal of Combinatorics, 23 (3), 1−19.
Klauck, Hartmut; Lee, Troy; Theis, Dirk Oliver; Thomas, Rekha R. (2015). Limitations of convex programming: lower bounds on extended formulations and factorization ranks (Dagstuhl Seminar 15082). Dagstuhl Reports, 5 (2), 109−127.10.4230/DagRep.5.2.109.
Pourmoradnasseri, Mozhgan; Theis, Dirk Oliver (2017). Nondeterministic Communication Complexity of random Boolean functions. Lecture Notes in Computer Science, 1−12 [ilmumas].
Pourmoradnasseri, Mozhgan; Theis, Dirk Oliver (2017). The (minimum) rank of typical fooling-set matrices. Lecture Notes in Computer Science, 1−10.x [ilmumas].
Theis, Dirk Oliver; Makkeh, Abdullah (2017). Comparison of IP and CNF Models for Control of Automated Valet Parking Systems. Springer Proccedings in Mathematics and Statistics, 1−8 [ilmumas].