Print

All talks are in Kongshøll

(Vestarabryggja 15, University of the Faroe Islands, Torshavn)

Day 1: Monday, June 27

8:40 – 8:50: Opening session (session chair: Qin Xin)

8:50 - 9:40: Invited Talk: David Peleg. On Realizing a Single Degree Sequence by a Bipartite Graph. (session chair: Artur Czumaj)

9:40 - 9:55: Coffee Break

9:55 - 12:00: Session one: (session chair: Mikkel Thorup)

  • Philip Bille, Inge Li Gørtz and Tord Stordalen. Predecessor on the Ultra-Wide Word RAM.
  • Tatsuya Yanagita, Sankardeep Chakraborty, Kunihiko Sadakane and Srinivasa Rao Satti. Space-Efficient Data Structure for Posets with Applications.
  • Junhao Gan, Anthony Wirth and Xin Zhang. An Almost Optimal Algorithm for Unbounded Search with Noisy Information.
  • Md Lutfar Rahman and Thomas Watson. Erdos-Selfridge Theorem for Nonmonotone CNFs.
  • Daniel Bertschinger, Meghana M Reddy and Enrico Mann. Lions and Contamination: Monotone Clearings. (Best student paper award)

12:00 - 13:00: Lunch

13:00 - 14:40: Session two: (session chair: Jukka Suomela)

  • Antonios Antoniadis, Peyman Jabbarzade Ganje and Golnoosh Shahkarami. A Novel Prediction Setup for Online Speed-Scaling.
  • Joan Boyar, Lene Favrholdt and Kim S. Larsen. Online Unit Profit Knapsack with Untrusted Predictions.
  • Rachita Sowle and Sharath Raghvendra. A Scalable Work Function Algorithm for the k-Server Problem.
  • Mark De Berg, Arpan Sadhukhan and Frits Spieksma. Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem.

14:40 – 14:55: Coffee Break

14:55 – 16:35: Session three: (session chair: Joan Boyar)

  • Helena Bergold, Daniel Bertschinger, Nicolas Grelier, Wolfgang Mulzer and Patrick Schnider. Well-Separation and Hyperplane Transversals in High Dimensions.
  • Safwa Ameer, Matt Gibson-Lopez, Erik Krohn and Qing Wang. On the Visibility Graphs of Pseudo-Polygons and Simple Polygons.
  • Jonas Cleve, Nicolas Grelier, Kristin Knorr, Maarten Löffler, Wolfgang Mulzer and Daniel Perz. Nearest-Neighbor Decompositions of Drawings.
  • Boris Aronov and Matthew Katz. Dynamic Approximate Multiplicatively-Weighted Nearest Neighbors.

17:20 – 19:30: reception and a 2-hour tour in Torshavn with a local guide

Day 2: Tuesday, June 28

8:50 - 9:40: Invited Talk: Mikkel Thorup. Reconstructing the Tree of Life (Fitting Distances by Tree Metrics). (session chair: Magnus Halldorsson)

9:40 - 9:55: Coffee Break

9:55 - 12:00: Session four: (session chair: Leszek Gasieniec)

  • David Adjiashvili, Felix Hommelsheim, Moritz Muehlenthaler and Oliver Schaudt. Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults.
  • Michael Elkin, Yuval Gitlitz and Ofer Neiman. Almost Shortest Paths with Near-Additive Error in Weighted Graphs.
  • Antonios Antoniadis, Sándor Kisfaludi-Bak, Bundit Laekhanukit and Daniel Vaz. On the Approximability of the Traveling Salesman Problem with Line Neighborhoods.
  • Pankaj K. Agarwal, Sharath Raghvendra, Pouyan Shirzadian and Rachita Sowle. An Improved -Approximation Algorithm for Geometric Bipartite Matching.
  • Tanmay Inamdar and Kasturi Varadarajan. Non-Uniform k-Center and Greedy Clustering.

12:00 - 13:00: Lunch

13:00 - 14:40: Session five: (session chair: Zdenek Dvorak)

  • Max Bannach, Pamela Fleischmann and Malte Skambath. Max-SAT with Absolute Value Functions: A Parameterized Perspective.
  • Chien-Chung Huang and François Sellier. Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms.
  • Foivos Fioravantes, Nikolaos Melissinos and Theofilos Triomatis. Complexity of Finding Maximum Locally Irregular Induced Subgraphs.
  • Cristina Bazgan, Katrin Casel and Pierre Cazals. Dense Graph Partitioning on Sparse and Dense Graphs.

14:40 – 14:55: Coffee Break

14:55 – 16:35: Session six: (session chair: Magnus Halldorsson)

  • Benjamin Aram Berendsohn. The Diameter of Caterpillar Associahedra.
  • Haitao Wang. Unit-Disk Range Searching and Applications.
  • Matt Gibson-Lopez and Serge Zamarripa. Optimal Bounds for Weak Consistent Digital Rays in 2D.
  • Hugo Akitaya, Erik D. Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara and Jules Wulms. Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares.

17:20 – 21:00: Conference banquet and entertainment at Hotel Hafnia (the top floor)

Day 3: Wednesday, June 29

8:30 - 9:20: Invited Talk: Leszek Gąsieniec. Time, Clocks and Efficiency of Population Protocols. (session chair: Qin Xin)

9:20 - 9:35: Coffee Break

9:35 - 11:15: Session seven: (session chair: Artur Czumaj)

  • Patrizio Angelini, Michael Bekos, Giordano Da Lozzo, Martin Gronemann, Fabrizio Montecchiani and Alessandra Tappini. Recognizing Map Graphs of Bounded Treewidth.
  • Prosenjit Bose, Pat Morin and Saeed Odak. An Optimal Algorithm for Product Structure in Planar Graphs.
  • Zdenek Dvorak. Approximation Metatheorems for Classes with Bounded Expansion.
  • Pascal Kunz, Till Fluschnik, Rolf Niedermeier and Malte Renken. Most Classic Problems Remain NP-hard on Relative Neighborhood Graphs and Their Relatives.

11:20 -12:15: Business Meeting (chair: Magnus Halldorsson)

12:15 - 13:15: Lunch and Happy Hour

13:15 - 19:00: Excursion