ISAAC 2015 Accepted Papers

Andrew Winslow. An Optimal Algorithm for Tiling the Plane with a Translated Polyomino
Eli Fox-Epstein, Duc Hoang, Yota Otachi and Ryuhei Uehara. Sliding Token on Bipartite Permutation Graphs
Mamadou Moustapha Kanté, Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Sigve H. Saether and Yngve Villanger. Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width
Yasushi Kawase. The secretary problem with a choice function.
Siu-Wing Cheng and Lau Man Kit. Adaptive point location in planar convex subdivisions
Prosenjit Bose, Rolf Fagerberg, André van Renssen and Sander Verdonschot. Competitive Local Routing with Constraints
Hicham El-Zein, Ian Munro and Siwei Yang. On the Succinct Representation of Unlabeled Permutations
Siu-Wing Cheng, Man Kwun Chiu, Jiongxin Jin and Antoine Vigneron. Navigating Weighted Regions with Scattered Skinny Tetrahedra
Sang Duk Yoon, Min-Gyu Kim, Wanbin Son and Hee-Kap Ahn. Geometric Matching Algorithms for Two Realistic Terrains
Petr Hlineny and Gelasio Salazar. On Hardness of the Joint Crossing Number
Diptarka Chakraborty and Raghunath Tewari. An $O(n^{\epsilon})$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
Jun Yan. Quantum Bit Commitment with Application in Quantum Zero-Knowledge Proof
Sándor Fekete, Robert Schweller and Andrew Winslow. Size-Dependent Tile Self-Assembly: Constant-Height Rectangles and Stability
Paz Carmi and Lilach Chaitman-Yerushalmi. On the Minimum Cost Range Assignment Problem
Tobias Friedrich, Timo Kötzing, Martin S. Krejca and Andrew M. Sutton. The Benefit of Recombination in Noisy Evolutionary Search
Matthias Ernst, Maciej Liśkiewicz and Rüdiger Reischuk. Algorithmic Learning for Steganography: Proper Learning of k-term DNF Formulas from Positive Samples
Sumedh Tirodkar and Sundar Vishwanathan. On the Approximability of the Minimum Rainbow Subgraph Problem and Other Related Problems
Wing-Kai Hon, Sharma V. Thankachan and Bojian Xu. An In-place Framework for Exact and Approximate Shortest Unique Substring Queries
Dmitry Itsykson, Alexander Knop and Dmitry Sokolov. Heuristic time hierarchies via hierarchies for sampling distributions
Qin Huang, Xingwu Liu, Xiaoming Sun and Jialin Zhang. How to Select the Top $k$ Elements from Evolving Data?
Lukáš Folwarczný and Jiří Sgall. General Caching Is Hard: Even with Small Pages
Eunjin Oh, Jean-Lou De Carufel and Hee-Kap Ahn. The 2-center problem in a simple polygon
Vladimir Kolmogorov, Michal Rolinek and Rustem Takhanov. Effectiveness of Structural Restrictions for Hybrid CSPs
Michael A. Bender, Samuel McCauley, Andrew McGregor, Shikha Singh and Hoa T. Vu. Run Generation Revisited: What Goes Up May or May Not Come Down
Tobias Friedrich, Maximilian Katzmann and Anton Krohmer. Unbounded Discrepancy of Deterministic Random Walks on Grids
Esther Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Matthew Katz, Joseph Mitchell and Marina Simakov. Choice is Hard
Joshua Grochow and Youming Qiao. Polynomial-time isomorphism test of groups that are tame extensions (Extended Abstract)
Ferdinando Cicalese, Eduardo Laber and Aline Saettler. Trading off Worst and Expected Cost in Decision Tree Problems
David Cattanéo and Simon Perdrix. Minimum Degree up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms
Shogo Nakajima and Francois Le Gall. Quantum Algorithm for Triangle Finding in Sparse Graphs
Guillaume Fertin, Irena Rusu and Stéphane Vialette. Obtaining a Triangular Matrix by Independent Row-Column Permutations
Chih-Hung Liu and Sandro Montanari. Minimizing the Diameter of a Spanning Tree for Imprecise Points
Maike Buchin and Stef Sijben. Model-based Classification of Trajectories
Maciej Skorski. A New Approximate Min-Max Theorem with Applications in Cryptography
Ashwin Arulselvan, Ágnes Cseh, Martin Groß, David Manlove and Jannik Matuschke. Many-to-one matchings with lower quotas: Algorithms and complexity
Mike Behrisch, Miki Hermann, Stefan Mengel and Gernot Salzer. Give Me Another One!
Moritz von Looz, Henning Meyerhenke and Roman Prutkin. Generating Random Hyperbolic Graphs in Subquadratic Time
Elena Khramtcova and Evanthia Papadopoulou. Linear-Time Algorithms for the Farthest-Segment Voronoi Diagram and Related Tree Structures
Yi-Jun Chang and Hsu-Chun Yen. Unfolding Orthogonal Polyhedra with Linear Refinement
Matteo Pontecorvi and Vijaya Ramachandran. Fully Dynamic Betweenness Centrality
Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski, Evangelos Kranakis, Danny Krizanc and Najmeh Taleb. When Patrolmen Become Corrupted: Monitoring a Graph using Faulty Mobile Robots
Marek Chrobak, Mordecai J. Golin, J. Ian Munro and Neal E. Young. Optimal search trees with 2-way comparisons
Oswin Aichholzer, Vincent Kusters, Wolfgang Mulzer, Alexander Pilz and Manuel Wettstein. An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings
Stefan Funke and Sabine Storandt. Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing
Karl Bringmann and Marvin Künnemann. Improved approximation for Frechet distance on c-packed curves matching conditional lower bounds
Pankaj K. Agarwal, Kyle Fox, Abhinandan Nath, Anastasios Sidiropoulos and Yusu Wang. Computing the Gromov-Hausdorff Distance for Metric Trees
Martin Farach-Colton and Meng-Tsung Tsai. On the Complexity of Computing Prime Tables
Haitao Wang and Xiao Zhang. Minimizing the Maximum Moving Cost of Interval Coverage
Matt Gibson, Erik Krohn and Qing Wang. The VC-Dimension of Visibility on the Boundary of a Simple Polygon
Tomáš Gavenčiak, Przemyslaw Gordinowicz, Vít Jelínek, Pavel Klavík and Jan Kratochvil. Cops and Robbers on String Graphs
Stephen Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer and Thomas Thierauf. Game values and computational complexity: An analysis via black-white combinatorial games
Andrew Mastin, Patrick Jaillet and Sang Chin. Randomized Minmax Regret for Combinatorial Optimization Under Uncertainty
Timothy M. Chan and Gelin Zhou. Multidimensional Range Selection
Makoto Nishida, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda. Inferring Strings from Full Abelian Periods
Pradeesha Ashok, Sudeshna Kolay and Aditi Dudeja. Exact and FPT algorithms for Max-Conflict Free Coloring in Hypergraphs
Qian-Ping Gu and Gengchun Xu. Constant Query Time $(1+\epsilon)$-Approximate Distance Oracle for Planar Graphs
Sergey Bereg, Krzysztof Fleszar, Philipp Kindermann, Sergey Pupyrev, Joachim Spoerhase and Alexander Wolff. Colored Non-Crossing Euclidean Steiner Forest
Mingyu Xiao. On a generalization of Nemhauser and Trotter's local optimization theorem
Sebastian Brandt, Nicolas Mattia, Jochen Seidel and Roger Wattenhofer. Toehold DNA Languages are Regular
Samira Daruki, Justin Thaler and Suresh Venkatasubramanian. Streaming Verification in Data Analysis
Shahin Kamali and Alejandro Lopez-Ortiz. All-Around Near-Optimal Solutions for the Online Bin Packing Problem
Martin Nöllenburg, Roman Prutkin and Ignaz Rutter. Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions
Abdolhamid Ghodselahi and Fabian Kuhn. Serving Online Requests with Mobile Servers
Sabine Storandt. Approximation Algorithms in the Successive Hitting Set Model
Eric Angel, Evripidis Bampis, Vincent Chau and Alexander Kononov. Min-Power Covering Problems