>> PDF version
| December 5, 2011 | ||
| 12:00- | Registration for GCOE Final Symposium and ISAAC | |
| 13:00- | (>> CompView Final Symposium) | |
| 18:15- | Reception | Duck (Oshidori)/Peacock (Kujaku) 2nd floor |
| December 6, 2011 | ||
| 8:30- | Registration | |
| 9:00-9:10 | Opening | |
| Osamu Watanabe | Opening Address | |
| 9:10-10:10 | Invited Talk 1 | |
| Chair: Shin-ichi Nakano | ||
| Dorothea Wagner | Algorithm Engineering for Route Planning: An Update | |
| 10:10-10:30 | Coffee Break | |
| 10:30-11:50 | Session 1 (4 talks) | |
| Session 1A: Approximation Algorithms I | ||
| Chair: Kazuo Iwama | ||
| Adrian Bock, Elyot Grant, Jochen Könemann and Laura Sanità | The School Bus Problem on Trees | |
| M. Reza Khani and Mohammad R. Salavatipour | Improved Approximations for Buy-at-bulk and Shallow-Light k-Steiner Trees and (k,2)-Subgraph | |
| Wei Yu and Guochuan Zhang | Improved Approximation Algorithms for Routing Shop Scheduling | |
| Markus Chimani and Matthias Woste | Contraction-Based Steiner Tree Approximations in Practice | |
| Session 1B: Computational Geometry I | ||
| Chair: Takeshi Tokuyama | ||
| Hee-Kap Ahn, Sang-Sub Kim, Christian Knauer, Lena Schlipf, Chan-Su Shin and Antoine Vigneron | Covering and Piercing Disks with Two Centers | |
| Hee-Kap Ahn, Sang Won Bae, Christian Knauer, Mira Lee, Chan-Su Shin and Antoine Vigneron | Generating Realistic Roofs over a Rectilinear Polygon | |
| Luis Barba, Matias Korman, Stefan Langerman and Rodrigo I. Silveira | Computing the Visibility Polygon Using Few Variables | |
| Matias Korman | Minimizing Interference in Ad-Hoc Networks with Bounded Communication Radius | |
| 11:50-14:00 | Lunch | |
| 14:00-15:00 | Invited Talk 2 | |
| Chair: Osamu Watanabe | ||
| Sanjeev Arora | Semidefinite Programming and Approximation Algorithms: A Survey | |
| 15:00-15:20 | Coffee Break | |
| 15:20-17:00 | Session 2 (5 talks) | |
| Session 2A: Graph Algorithms | ||
| Chair: Ryuhei Uehara | ||
| Jakub Radoszewski and Wojciech Rytter | Hamiltonian Paths in the Square of a Tree | |
| Andreas Brandstädt and Raffaele Mosca | Dominating Induced Matchings for P7-free Graphs in Linear Time | |
| Rémy Belmonte, Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, Marcin Kamiński and Daniël Paulusma | Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths | |
| Van Bang Le and Ragnar Nevries | Recognizing Polar Planar Graphs Using New Results for Monopolarity | |
| Naoyuki Kamiyama | Robustness of Minimum Cost Arborescences | |
| Session 2B: Data Structures I | ||
| Chair: Nodari Sitchinava | ||
| Meng He, J. Ian Munro and Gelin Zhou | Path Queries in Weighted Trees | |
| Amr Elmasry, Meng He, J. Ian Munro and Patrick K. Nicholson | Dynamic Range Majority Data Structures | |
| Meng He, J. Ian Munro and Patrick K. Nicholson | Dynamic Range Selection in Linear Space | |
| Yakov Nekrich | A Dynamic Stabbing-Max Data Structure with Sub-Logarithmic Query Time | |
| Mordecai Golin, John Iacono, Danny Krizanc, Rajeev Raman and Srinivasa Rao Satti | Encoding 2D Range Maximum Queries | |
| December 7, 2011 | ||
| 8:30- | Registration | |
| 9:00-10:00 | Session 3 (3 talks) | |
| Session 3A: Distributed Systems | ||
| Chair: Shuji Kijima | ||
| Tobias Friedrich, Thomas Sauerwald and Alexandre Stauffer | Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions | |
| Cheng-Hsiao Tsou, Gen-Huey Chen and Ching-Chi Lin | Broadcasting in Heterogeneous Tree Networks with Uncertainty | |
| Kai-Simon Goetzmann, Tobias Harks, Max Klimm and Konstantin Miller | Optimal File Distribution in Peer-to-Peer Networks | |
| Session 3B: Computational Geometry II | ||
| Chair: Bettina Speckmann | ||
| Adrian Dumitrescu and Evan Hilscher | Animal Testing | |
| Adrian Dumitrescu and Masud Hasan | Cutting Out Polygons with a Circular Saw | |
| Mark de Berg, Atlas F. Cook IV and Joachim Gudmundsson | Fast Fréchet Queries | |
| 10:00-10:20 | Coffee Break | |
| 10:20-11:40 | Session 4 (4 talks) | |
| Session 4A: Graph Drawing and Information Visualization | ||
| Chair: Seok-Hee Hong | ||
| Kevin Buchin, Bettina Speckmann and Kevin Verbeek | Angle-Restricted Steiner Arborescences for Flow Map Layout | |
| Mark de Berg, Bettina Speckmann and Vincent van der Weele | Treemaps with Bounded Aspect Ratio | |
| Patrizio Angelini, Giuseppe Di Battista and Fabrizio Frati | Simultaneous Embedding of Embedded Planar Graphs | |
| Muhammad Jawaherul Alam, Therese Biedl, Stefan Felsner, Andreas Gerasch, Michael Kaufmann and Stephen G. Kobourov | Linear-Time Algorithms for Hole-Free Rectilinear Proportional Contact Graph Representations | |
| Session 4B: Data Structures II | ||
| Chair: Rajeev Raman | ||
| Michael T. Goodrich and Joseph A. Simons | Fully Retroactive Approximate Range and Nearest Neighbor Searching | |
| Arash Farzan and Johannes Fischer | Compact Representation of Posets | |
| Luca Castelli Aleardi and Olivier Devillers | Explicit Array-Based Compact Data Structures for Triangulations | |
| Gonzalo Navarro and Luis M. S. Russo | Space-Efficient Data-Analysis Queries on Grids | |
| 11:40-14:00 | Lunch | |
| 14:00-15:20 | Session 5 (4 talks) | |
| Session 5A: Parameterized Algorithms I | ||
| Chair: Dorothea Wagner | ||
| Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan and Saket Saurabh | A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments | |
| Sheng-Ying Hsiao | Fixed-Parameter Complexity of Feedback Vertex Set in Bipartite Tournaments | |
| Sylvain Guillemot | Parameterized Algorithms for Inclusion of Linear Matchings | |
| Chunhao Wang and Qian-Ping Gu | Computational Study on Bidimensionality Theory Based Algorithm for Longest Path Problem | |
| Session 5B: Parallel and External Memory Algorithms | ||
| Chair: Kunsoo Park | ||
| Michael T. Goodrich, Nodari Sitchinava and Qin Zhang | Sorting, Searching, and Simulation in the MapReduce Framework | |
| Elaine Angelino, Michael T. Goodrich, Michael Mitzenmacher and Justin Thaler | External Memory Multimaps | |
| Yakov Nekrich | External Memory Orthogonal Range Reporting with Fast Updates | |
| Jörg Lässig and Dirk Sudholt | Analysis of Speedups in Parallel Evolutionary Algorithms for Combinatorial Optimization | |
| 15:20-15:40 | Coffee Break | |
| 15:40-16:40 | Session 6 (3 talks) | |
| Session 6A: Game Theory and Internet Algorithms | ||
| Chair: Joachim Gudmundsson | ||
| David Avis, Kazuo Iwama and Daichi Paku | Verifying Nash Equilibria in PageRank Games on Undirected Web Graphs | |
| Aviv Nisgav and Boaz Patt-Shamir | Improved Collaborative Filtering | |
| Fabien de Montgolfier, Mauricio Soto and Laurent Viennot | Asymptotic Modularity of Some Graph Classes | |
| Session 6B: Computational Complexity | ||
| Chair: Martin Fürer | ||
| Ho-Lin Chen, David Doty and Shinnosuke Seki | Program Size and Temperature in Self-assembly | |
| Tomoyuki Yamakami | Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems | |
| Dmitry Itsykson and Dmitry Sokolov | Lower Bounds for Myopic DPLL Algorithms with a Cut Heuristic | |
| 18:15- | Banquet | |
| December 8, 2011 | ||
| 8:30- | Registration | |
| 9:00-10:00 | Session 7 (3 talks) | |
| Session 7A: Approximation Algorithms II | ||
| Chair: Siu-Wing Cheng | ||
| Ryuta Ando and Tomomi Matsui | Algorithm for Single Allocation Problem on Hub-and-Spoke Networks in 2-Dimensional Plane | |
| Martin Fürer and Huiwen Yu | Packing-Based Approximation Algorithm for the k-Set Cover Problem | |
| Mong-Jen Kao and D.T. Lee | Capacitated Domination: Constant Factor Approximations for Planar Graphs | |
| Session 7B: Randomized Algorithms | ||
| Chair:Dirk Sudholt | ||
| Ioannis Atsonios, Olivier Beaumont, Nicolas Hanusse and Yusik Kim | On Power-Law Distributed Balls in Bins and its Applications to View Size Estimation | |
| Masatora Ogata, Yukiko Yamauchi, Shuji Kijima and Masafumi Yamashita | A Randomized Algorithm for Finding Frequent Elements in Streams Using O(log log N) Space | |
| Jeremy Hurwitz | A Nearly-Quadratic Gap Between Adaptive and Non-adaptive Property Testers | |
| 10:00-10:20 | Coffee Break | |
| 10:20-11:40 | Session 8 (4 talks) | |
| Session 8A: Online and Streaming Algorithms | ||
| Chair:Tetsuo Shibuya | ||
| Shota Yasutake, Kohei Hatano, Shuji Kijima, Eiji Takimoto and Masayuki Takeda | Online Linear Optimization over Permutations | |
| Hiroshi Fujiwara, Takuma Kitano and Toshihiro Fujito | On the Best Possible Competitive Ratio for Multislope Ski Rental | |
| Kuan-Chieh Robert Tseng and David Kirkpatrick | Input-Thrifty Extrema Testing | |
| Ho-Leung Chan, Tak-Wah Lam, Lap-Kei Lee, Jiangwei Pan, Hing-Fung Ting and Qin Zhang | Edit Distance to Monotonicity in Sliding Windows | |
| Session 8B: Computational Geometry III | ||
| Chair: Sang Won Bae | ||
| Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, Tao B. Schardl and Isaac Shapiro-Ellowitz | Folding Equilateral Plane Graphs | |
| Danny Z. Chen and Haitao Wang | Efficient Algorithms for the Weighted k-Center Problem on a Real Line | |
| Danny Z. Chen and Haitao Wang | Outlier Respecting Points Approximation | |
| Danny Z. Chen and Haitao Wang | An Improved Algorithm for Reconstructing a Simple Polygon from the Visibility Angles | |
| 11:40-14:00 | Lunch | |
| 14:00-15:20 | Session 9 (4 talks) | |
| Session 9A: Parameterized Algorithms II | ||
| Chair:Sylvain Guillemot | ||
| Jiong Guo, Sepp Hartung, Rolf Niedermeier and Ondřej Suchý | The Parameterized Complexity of Local Search for TSP, More Refined | |
| Martin Dörnfelder, Jiong Guo, Christian Komusiewicz and Mathias Weller | On the Parameterized Complexity of Consensus Clustering | |
| Victor Campos, Sulamita Klein, Rudini Sampaio and Ana Silva | Two Fixed-Parameter Algorithms for the Cocoloring Problem | |
| Cristina Bazgan, Morgan Chopin and Michael Fellows | Parameterized Complexity of the Firefighter Problem | |
| Session 9B: String Algorithms | ||
| Chair: Kunihiko Sadakane | ||
| Travis Gagie, Pawel Gawrychowski and Simon J. Puglisi | Faster Approximate Pattern Matching in Compressed Repetitive Texts | |
| Yoshifumi Sakai | A New Algorithm for the Characteristic String Problem under Loose Similarity Criteria | |
| Wing-Kai Hon, Chen-Hua Lu, Rahul Shah and Sharma V. Thankachan | Succinct Indexes for Circular Patterns | |
| Amihood Amir, Alberto Apostolico, Gad M. Landau, Avivit Levy, Moshe Lewenstein and Ely Porat | Range LCP | |
| 15:20-15:40 | Coffee Break | |
| 15:40-17:00 | Session 10 (4 talks) | |
| Session 10A: Optimization | ||
| Chair: Takehiro Ito | ||
| Naonori Kakimura, Kazuhisa Makino and Kento Seimi | Computing Knapsack Solutions with Cardinality Robustness | |
| Lisa Hellerstein, Özgür Özkan and Linda Sellie | Max-Throughput for (Conservative) k-of-n Testing | |
| Amihood Amir, Estrella Eisenberg, Avivit Levy and Noa Lewenstein | Closest Periodic Vectors in Lp Spaces | |
| Matt Gibson, Dongfeng Han, Milan Sonka and Xiaodong Wu | Maximum Weight Digital Regions Decomposable into Digital Star-Shaped Regions | |
| Session 10B: Computational Biology | ||
| Chair: Kun-Mao Chao | ||
| Hung-I Yu, Tien-Ching Lin and D. T. Lee | Finding Maximum Sum Segments in Sequences with Uncertainty | |
| Yun Cui, Jesper Jansson and Wing-Kin Sung | Algorithms for Building Consensus MUL-trees | |
| Francis Y.L. Chin, Henry C.M. Leung and S.M. Yiu | Adaptive Phenotype Testing for AND/OR Items | |
| Taku Onodera and Tetsuo Shibuya | An Index Structure for Spaced Seed Search | |