BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Zdeněk Dvořák (Computer Science Institute of Charles University
 )
DTSTART:20201008T090000Z
DTEND:20201008T100000Z
DTSTAMP:20260404T111415Z
UID:ITI-seminar/1
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/ITI-s
 eminar/1/">Approximation algorithms in classes with sublinear separators</
 a>\nby Zdeněk Dvořák (Computer Science Institute of Charles University)
  as part of ITI online seminar\n\n\nAbstract\nLipton and Tarjan proved tha
 t every n-vertex planar graph has a balanced separator of order O(sqrt(n))
  and gave a number of algorithmic applications of this result.  In particu
 lar\, they showed that the maximum size of an independent set in graphs wi
 th this property can be approximated arbitrarily well in polynomial time. 
  The idea of their algorithm applies to other problems\, but only subject 
 to somewhat limiting restrictions (the optimal solution must be of linear 
 size and the problem must be defined by edge constraints).\n\nIn the last 
 few years\, several more sophisticated techniques for graphs with\nsubline
 ar separators were developed\; these techniques overcome the aforementione
 d restrictions and enable us to design approximation algorithms for much m
 ore general classes of problems.  I will survey these developments and the
  outstanding challenges.\n
LOCATION:https://stable.researchseminars.org/talk/ITI-seminar/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Petr Hliněný (Masaryk University\, Brno)
DTSTART:20201015T090000Z
DTEND:20201015T103000Z
DTSTAMP:20260404T111415Z
UID:ITI-seminar/2
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/ITI-s
 eminar/2/">Toroidal grid minors and stretch in embedded graphs</a>\nby Pet
 r Hliněný (Masaryk University\, Brno) as part of ITI online seminar\n\n\
 nAbstract\nWe investigate the toroidal expanse of an embedded graph G\, th
 at is\, the size\nof the largest toroidal grid contained in G as a minor. 
 In the course of this\nwork we introduce a new embedding density parameter
 \, the stretch of an embedded\ngraph G\, and use it to bound the toroidal 
 expanse from above and from below\nwithin a constant factor depending only
  on the genus and the maximum degree. We\nalso show that these parameters 
 are tightly related to the planar crossing\nnumber of G. As a consequence 
 of our bounds\, we derive an efficient constant\nfactor approximation algo
 rithm for the toroidal expanse and for the crossing\nnumber of a surface-e
 mbedded graph with bounded maximum degree.\n
LOCATION:https://stable.researchseminars.org/talk/ITI-seminar/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Frederik Garbe (Institute of Mathematics\, Czech Academy of Scienc
 es)
DTSTART:20201022T090000Z
DTEND:20201022T103000Z
DTSTAMP:20260404T111415Z
UID:ITI-seminar/3
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/ITI-s
 eminar/3/">Limits of Latin squares</a>\nby Frederik Garbe (Institute of Ma
 thematics\, Czech Academy of Sciences) as part of ITI online seminar\n\n\n
 Abstract\nWe develop a limit theory for Latin squares\, paralleling the re
 cent\nlimit theories of dense graphs and permutations. We introduce a noti
 on\nof density\, an appropriate version of the cut distance\, and a space 
 of\nlimit objects - so-called Latinons. Key results of our theory are the\
 ncompactness of the limit space and the equivalence of the topologies\nind
 uced by the cut distance and the left-convergence. Last\, using\nKeevash's
  recent results on combinatorial designs\, we prove that each\nLatinon can
  be approximated by a finite Latin square.\n\nThis is joint work with Robe
 rt Hancock\, Jan Hladký and Maryam Sharifzadeh.\n
LOCATION:https://stable.researchseminars.org/talk/ITI-seminar/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Roman Nedela (University of West Bohemia\, Pilsen)
DTSTART:20201029T100000Z
DTEND:20201029T113000Z
DTSTAMP:20260404T111415Z
UID:ITI-seminar/4
DESCRIPTION:by Roman Nedela (University of West Bohemia\, Pilsen) as part 
 of ITI online seminar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/ITI-seminar/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andreas Feldmann (Faculty of Mathematics and Physics of Charles Un
 iversity\, Prague)
DTSTART:20201105T100000Z
DTEND:20201105T113000Z
DTSTAMP:20260404T111415Z
UID:ITI-seminar/5
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/ITI-s
 eminar/5/">Polynomial Time Approximation Schemes for Clustering in Low Hig
 hway Dimension Graphs</a>\nby Andreas Feldmann (Faculty of Mathematics and
  Physics of Charles University\, Prague) as part of ITI online seminar\n\n
 \nAbstract\nWe study clustering problems such as k-Median\, k-Means\, and 
 Facility Location in graphs of low highway dimension\, which is a graph pa
 rameter modeling transportation networks. It was previously shown that app
 roximation schemes for these problems exist\, which either run in quasi-po
 lynomial time (assuming constant highway dimension) [Feldmann et al. SICOM
 P 2018] or run in FPT time (parameterized by the number of clusters k\, th
 e highway dimension\, and the approximation factor) [Becker et al. ESA 201
 8\, Braverman et al. 2020]. In this paper we show that a polynomial-time a
 pproximation scheme (PTAS) exists (assuming constant highway dimension). W
 e also show that the considered problems are NP-hard on graphs of highway 
 dimension 1. This is joint work with David Saulpic.\n
LOCATION:https://stable.researchseminars.org/talk/ITI-seminar/5/
END:VEVENT
END:VCALENDAR