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:20260422T225927Z
UID:ITI-seminar/1
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/ITI-seminar/
 1/">Approximation algorithms in classes with sublinear separators</a>\nby 
 Zdeněk Dvořák (Computer Science Institute of Charles University) as par
 t of ITI online seminar\n\n\nAbstract\nLipton and Tarjan proved that every
  n-vertex planar graph has a balanced separator of order O(sqrt(n)) and ga
 ve a number of algorithmic applications of this result.  In particular\, t
 hey showed that the maximum size of an independent set in graphs with this
  property can be approximated arbitrarily well in polynomial time.  The id
 ea of their algorithm applies to other problems\, but only subject to some
 what limiting restrictions (the optimal solution must be of linear size an
 d the problem must be defined by edge constraints).\n\nIn the last few yea
 rs\, several more sophisticated techniques for graphs with\nsublinear sepa
 rators were developed\; these techniques overcome the aforementioned restr
 ictions and enable us to design approximation algorithms for much more gen
 eral classes of problems.  I will survey these developments and the outsta
 nding challenges.\n
LOCATION:https://researchseminars.org/talk/ITI-seminar/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Petr Hliněný (Masaryk University\, Brno)
DTSTART:20201015T090000Z
DTEND:20201015T103000Z
DTSTAMP:20260422T225927Z
UID:ITI-seminar/2
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/ITI-seminar/
 2/">Toroidal grid minors and stretch in embedded graphs</a>\nby Petr Hlin
 ěný (Masaryk University\, Brno) as part of ITI online seminar\n\n\nAbstr
 act\nWe investigate the toroidal expanse of an embedded graph G\, that 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 expans
 e from above and from below\nwithin a constant factor depending only on th
 e genus and the maximum degree. We\nalso show that these parameters are ti
 ghtly related to the planar crossing\nnumber of G. As a consequence of our
  bounds\, we derive an efficient constant\nfactor approximation algorithm 
 for the toroidal expanse and for the crossing\nnumber of a surface-embedde
 d graph with bounded maximum degree.\n
LOCATION:https://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:20260422T225927Z
UID:ITI-seminar/3
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/ITI-seminar/
 3/">Limits of Latin squares</a>\nby Frederik Garbe (Institute of Mathemati
 cs\, Czech Academy of Sciences) as part of ITI online seminar\n\n\nAbstrac
 t\nWe develop a limit theory for Latin squares\, paralleling the recent\nl
 imit theories of dense graphs and permutations. We introduce a notion\nof 
 density\, an appropriate version of the cut distance\, and a space of\nlim
 it objects - so-called Latinons. Key results of our theory are the\ncompac
 tness of the limit space and the equivalence of the topologies\ninduced by
  the cut distance and the left-convergence. Last\, using\nKeevash's recent
  results on combinatorial designs\, we prove that each\nLatinon can be app
 roximated by a finite Latin square.\n\nThis is joint work with Robert Hanc
 ock\, Jan Hladký and Maryam Sharifzadeh.\n
LOCATION:https://researchseminars.org/talk/ITI-seminar/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Roman Nedela (University of West Bohemia\, Pilsen)
DTSTART:20201029T100000Z
DTEND:20201029T113000Z
DTSTAMP:20260422T225927Z
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://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:20260422T225927Z
UID:ITI-seminar/5
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/ITI-seminar/
 5/">Polynomial Time Approximation Schemes for Clustering in Low Highway Di
 mension Graphs</a>\nby Andreas Feldmann (Faculty of Mathematics and Physic
 s of Charles University\, Prague) as part of ITI online seminar\n\n\nAbstr
 act\nWe study clustering problems such as k-Median\, k-Means\, and Facilit
 y Location in graphs of low highway dimension\, which is a graph parameter
  modeling transportation networks. It was previously shown that approximat
 ion schemes for these problems exist\, which either run in quasi-polynomia
 l time (assuming constant highway dimension) [Feldmann et al. SICOMP 2018]
  or run in FPT time (parameterized by the number of clusters k\, the highw
 ay dimension\, and the approximation factor) [Becker et al. ESA 2018\, Bra
 verman et al. 2020]. In this paper we show that a polynomial-time approxim
 ation scheme (PTAS) exists (assuming constant highway dimension). We also 
 show that the considered problems are NP-hard on graphs of highway dimensi
 on 1. This is joint work with David Saulpic.\n
LOCATION:https://researchseminars.org/talk/ITI-seminar/5/
END:VEVENT
END:VCALENDAR