/ ISAAC 2015 / 26th Symposium on Algorithms and Computation/ Dec.8ー11, 2015
ISAAC 2015


December 8 (Tuesday)
19:00-21:00 Welcome Reception, Sirius(51F)



Download: Program.pdf

Day 1 (December 9) - ISAAC 2015

Session A (Iris I) Session B (Iris II)
08:45-9:45 Invited Talk 1: Soft Clustering: Models and Algorithms. Ravi Kannan / Chair: Kazuhisa Makino (Towers Ballroom)
9:45-10:05 Coffee Break
Session 1
Computational Geometry I / Sang Won Bae Data Structures / Amr Elmasry

An Optimal Algorithm for Tiling the Plane with a Translated Polyomino. Andrew Winslow

On the Succinct Representation of Unlabeled Permutations. Hicham El-Zein, Ian Munro and Siwei Yang

Adaptive point location in planar convex subdivisions. Siu-Wing Cheng and Lau Man Kit

How to Select the Top k Elements from Evolving Data?. Qin Huang, Xingwu Liu, Xiaoming Sun and Jialin Zhang

Competitive Local Routing with Constraints. Prosenjit Bose, Rolf Fagerberg, Andrè van Renssen and Sander Verdonschot

Optimal search trees with 2-way comparisons. Marek Chrobak, Mordecai J. Golin, J. Ian Munro and Neal E. Young

Navigating Weighted Regions with Scattered Skinny Tetrahedra. Siu-Wing Cheng, Man Kwun Chiu, Jiongxin Jin and Antoine Vigneron

Multidimensional Range Selection. Timothy M. Chan and Gelin Zhou
11:45-13:40 Lunch
Session 2
Combinatorial Optimization and Approximation Algorithms I / Naonori Kakimura Randomized Algorithms I / Rene Sitters

On the Minimum Cost Range Assignment Problem. Paz Carmi and Lilach Chaitman-Yerushalmi

The secretary problem with a choice function. Yasushi Kawase

On the Approximability of the Minimum Rainbow Subgraph Problem and Other Related Problems. Sumedh Tirodkar and Sundar Vishwanathan

The Benefit of Recombination in Noisy Evolutionary Search. Tobias Friedrich, Timo Kötzing, Martin S. Krejca and Andrew M. Sutto

General Caching Is Hard: Even with Small Pages. Lukáš Folwarczny and Jiří Sgall

Algorithmic Learning for Steganography: Proper Learning of k-term DNF Formulas from Positive Samples. Matthias Ernst, Maciej Liśkiewicz and Rüdiger Reischuk
14:55-15:15 Coffee Break
Session 3
Combinatorial Optimization and Approximation Algorithms II / Kei Kimura Randomized Algorithms II / Shuji Kijima

Obtaining a Triangular Matrix by Independent Row-Column Permutations Guillaume Fertin, Irena Rusu and Stéphane Vialette

Heuristic time hierarchies via hierarchies for sampling distributions. Dmitry Itsykson, Alexander Knop and Dmitry Sokolov

Many-to-one matchings with lower quotas: Algorithms and complexity. Ashwin Arulselvan, Ágnes Cseh, Martin Groß, David Manlove and Jannik Matuschke

Unbounded Discrepancy of Deterministic Random Walks on Grids. Tobias Friedrich, Maximilian Katzmann and Anton Krohmer

Minimizing the Maximum Moving Cost of Interval Coverage. Haitao Wang and Xiao Zhang

Trading off Worst and Expected Cost in Decision Tree Problems. Ferdinando Cicalese, Eduardo Laber and Aline Saettler

Day 2 (December 10) - ISAAC 2015

Session A (Iris I) Session B (Iris II)
08:45-9:45 Invited Talk 2: Computing on Strategic Inputs. Constantinos Daskalakis / Chair: Khaled Elbassioni (Towers Ballroom)
9:45-10:05 Coffee Break
Session 4
Graph Algorithms and FPT I / Michael Lampis Computational Geometry II / Sang Won Bae

Sliding Token on Bipartite Permutation Graphs. Eli Fox-Epstein, Duc Hoang, Yota Otachi and Ryuhei Uehara

Geometric Matching Algorithms for Two Realistic Terrains. Sang Duk Yoon, Min-Gyu Kim, Wanbin Son and Hee-Kap Ahn

Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width. Mamadou Moustapha Kanté, Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Sigve H. Saether and Yngve Villanger

Size-Dependent Tile Self-Assembly: Constant-Height Rectangles and Stability. Sándor Fekete, Robert Schweller and Andrew Winslow

Minimum Degree up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms. David Cattanéo and Simon Perdrix

The 2-center problem in a simple polygon. Eunjin Oh, Jean-Lou De Carufel and Hee-Kap Ahn

Exact and FPT algorithms for Max-Conflict Free Coloring in Hypergraphs. Pradeesha Ashok, Sudeshna Kolay and Aditi Dudeja

Choice is Hard. Esther Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Matthew Katz, Joseph Mitchell and Marina Simakov
11:45-13:15 Lunch
Session 5
Graph Algorithms and FPT II / Tsan-sheng Hsu Computational Geometry III / Der-Tsai Lee

Fully Dynamic Betweenness Centrality. Matteo Pontecorvi and Vijaya Ramachandran

Minimizing the Diameter of a Spanning Tree for Imprecise Points. Chih-Hung Liu and Sandro Montanari

When Patrolmen Become Corrupted: Monitoring a Graph using Faulty Mobile Robots. Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski, Evangelos Kranakis, Danny Krizanc and Najmeh Taleb

Model-based Classification of Trajectories. Maike Buchin and Stef Sijben

Cops and Robbers on String Graphs. Tomáš Gavenčiak, Przemyslaw Gordinowicz, Vít Jelínek, Pavel Klavík and Jan Kratochvil

Linear-Time Algorithms for the Farthest-Segment Voronoi Diagram and Related Tree Structures. Elena Khramtcova and Evanthia Papadopoulou

Min-Power Covering Problems. Eric Angel, Evripidis Bampis, Vincent Chau and Alexander Kononov

Unfolding Orthogonal Polyhedra with Linear Refinement. Yi-Jun Chang and Hsu-Chun Yen
14:55-15:15 Coffee Break
Session 6
Combinatorial Optimization and Approximation Algorithms III / Rene Sitters Randomized Algorithms III / Shuji Kijima

Colored Non-Crossing Euclidean Steiner Forest. Sergey Bereg, Krzysztof Fleszar, Philipp Kindermann, Sergey Pupyrev, Joachim Spoerhase and Alexander Wolff

Generating Random Hyperbolic Graphs in Subquadratic Time. Moritz von Looz, Henning Meyerhenke and Roman Prutkin

On a generalization of Nemhauser and Trotter's local optimization theorem. Mingyu Xiao

Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing. Stefan Funke and Sabine Storandt

Approximation Algorithms in the Successive Hitting Set Model. Sabine Storandt

Randomized Minmax Regret for Combinatorial Optimization Under Uncertainty. Andrew Mastin, Patrick Jaillet and Sang Chin
19:00-21:00 Banquet(Towers Ballroom)

Day 3 (December 11) - ISAAC 2015

Session A (Iris I) Session B (Iris II)
08:45-9:45 Invited Talk 3: Lower bounds on the size of linear programs. Thomas Rothvoss / Chair: Kazuhisa Makino (Towers Ballroom)
9:45-10:05 Coffee Break
Session 7
Computational Geometry IV / Chan-Su Shin Complexity and Quantum Computation I / Michal Koucky

An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings. Oswin Aichholzer, Vincent Kusters, Wolfgang Mulzer, Alexander Pilz and Manuel Wettstein

Quantum Bit Commitment with Application in Quantum Zero-Knowledge Proof. Jun Yan

Improved approximation for Frechet distance on c-packed curves matching conditional lower bounds. Karl Bringmann and Marvin Künnemann

Effectiveness of Structural Restrictions for Hybrid CSPs. Vladimir Kolmogorov, Michal Rolinek and Rustem Takhanov

Computing the Gromov-Hausdorff Distance for Metric Trees. Pankaj K. Agarwal, Kyle Fox, Abhinandan Nath, Anastasios Sidiropoulos and Yusu Wang

Polynomial-time isomorphism test of groups that are tame extensions (Extended Abstract). Joshua Grochow and Youming Qiao

The VC-Dimension of Visibility on the Boundary of a Simple Polygon. Matt Gibson, Erik Krohn and Qing Wang

Quantum Algorithm for Triangle Finding in Sparse Graphs. Shogo Nakajima and Francois Le Gall
11:45-13:15 Lunch
Session 8
Graph Drawing & Planar Graphs / Seokhee Hong Complexity and Quantum Computation II / Valia Mitsou

On Hardness of the Joint Crossing Number. Petr Hlineny and Gelasio Salazar

A New Approximate Min-Max Theorem with Applications in Cryptography. Maciej Skorski

An O(nε) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs. Diptarka Chakraborty and Raghunath Tewari

Give Me Another One!. Mike Behrisch, Miki Hermann, Stefan Mengel and Gernot Salzer

Constant Query Time (1+ε)-Approximate Distance Oracle for Planar Graphs. Qian-Ping Gu and Gengchun Xu

On the Complexity of Computing Prime Tables. Martin Farach-Colton and Meng-Tsung Tsai

Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions. Martin Nölenburg, Roman Prutkin and Ignaz Rutter

Game values and computational complexity: An analysis via black-white combinatorial games. Stephen Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer and Thomas Thierauf
14:55-15:15 Coffee Break
Session 9
Online and Streaming Algorithms / Yasushi Kawase String and DNA Algorithms / Michal Koucky

Run Generation Revisited: What Goes Up May or May Not Come Down. Michael A. Bender, Samuel McCauley, Andrew McGregor, Shikha Singh and Hoa T. Vuf

An In-place Framework for Exact and Approximate Shortest Unique Substring Queries. Wing-Kai Hon, Sharma V. Thankachan and Bojian Xu

Streaming Verification in Data Analysis. Samira Daruki, Justin Thaler and Suresh Venkatasubramanian

Inferring Strings from Full Abelian Periods. Makoto Nishida, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda

All-Around Near-Optimal Solutions for the Online Bin Packing Problem. Shahin Kamali and Alejandro Lopez-Ortiz

Toehold DNA Languages are Regular. Sebastian Brandt, Nicolas Mattia, Jochen Seidel and Roger Wattenhofer

Serving Online Requests with Mobile Servers. Abdolhamid Ghodselahi and Fabian Kuhn