CONFERENCESACM-SIAM Symposium on Discrete Algorithms

Program


Poster Session

No poster session is scheduled for SODA07.

Program Schedule

Please note: No updates will be made to the web program.  Paper titles and author listings are updated as final versions of papers are received for the final printed program. 
             
Day Date Event  Session ID Time Title Authors
Friday 5-Jan Registration   4:00 PM - 6:00 PM    
             
Saturday 6-Jan Registration    7:30 AM - 7:00 PM    
    ALENEX and ANALCO Workshops   8:30 AM - 6:30 PM    
    ACM-SIAM SODA Welcome Reception   6:30 PM - 8:30 PM    
             
Sunday 7-Jan Registration    8:00 AM - 4:45 PM    
    Continental Breakfast   8:30 AM    
    Concurrent Sessions 9:00 AM - 11:05 AM 1A 9:00 AM Region-Fault Tolerant Geometric Spanners Mohammad Ali Abam, Mark de Berg, Mohammad Farshi and Joachim Gudmundsson
    9:25 AM A PTAS for TSP with Neighborhoods Among Fat Regions in the Plane Joseph S. B. Mitchell
    9:50 AM Optimal Dynamic Vertical Ray Shooting in Rectilinear Planar Subdivisions Yoav Giora and Haim Kaplan
    10:15 AM Squarepants in a Tree: Sum of Subtree Clustering and Hyperbolic Pants Decomposition David Eppstein
    10:40 AM A Near-Linear Time Constant Factor Approximation for Euclidean Bi-chromatic Matching (Cost) Piotr Indyk
    Concurrent Sessions 9:00 AM - 11:05 AM 1B 9:00 AM Compacting Cuts: A New Linear Formulation for Minimum Cut Robert D. Carr, Goran Konjevod, Greg Little, Venkatesh Natarajan and Ojas Parekh
    9:25 AM Linear Programming Relaxations of Maxcut Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu
    9:50 AM Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems Moses Charikar, Konstantin Makarychev and Yury Makarychev
    10:15 AM Improved Bounds for the Symmetric Rendezvous Value on the Line Q. Han, D. Du, J.C. Vera and L.F. Zuluaga 
    10:40 AM Efficient Solutions to Relaxations of Combinatorial Problems with Submodular Penalties via the Lov\'asz Extension and Non-smooth Convex Optimization Fabi\'an A. Chudak and Kiyohito Nagano
    Concurrent Sessions 9:00 AM - 11:05 AM 1C 9:00 AM Multiple Source Shortest Paths in a Genus $g$ Graph Sergio Cabello and Erin W. Chambers
    9:25 AM Obnoxious Centers in Graphs Sergio Cabello and G\"unter Rote
    9:50 AM Maximum Matching in Graphs with an Excluded Minor Raphael Yuster and Uri Zwick
    10:15 AM Faster Dynamic Matchings and Vertex Connectivity Piotr Sankowski
    10:40 AM Efficient Algorithms for Computing All Low s-t Connectivities and Related Problems Ramesh Hariharan, Telikepalli Kavitha and Debmalya Panigrahi
    Coffee Break   11:05 AM - 11:30 AM    
    Invited Plenary Session    2 11:30 AM - 12:30 PM Analytic Combinatorics, A Calculus of Discrete Structures Philippe Flajolet, INRIA, France
    Luncheon   12:30 PM - 2:00 PM    
    Concurrent Sessions 2:00 PM - 4:05 PM 3A 2:00 PM Equilibria in Online Games Roee Engelberg and Josefh (Seffi) Naor
    2:25 PM The Approximation Complexity of Win-Lose Games Xi Chen, Shang-Hua Teng and Paul Valiant
    2:50 PM Convergence to Approximate Nash Equilibria in Congestion Games Steve Chien and Alistair Sinclair
    3:15 PM Efficient Contention Resolution Protocols for Selfish Agents Amos Fiat, Yishay Mansour and Uri Nadav
    3:40 PM Strong Price of Anarchy Michal Feldman, Nir Andelman and Yishay Mansour
    Concurrent Sessions 2:00 PM - 4:05 PM 3B 2:00 PM Online Buffer Management in QoS Switches Fei Li, Jay Sethuraman and Clifford Stein, Matthias Englert and Matthias Westermann
    2:25 PM Instability of FIFO in the Permanent Sessions Model at Arbitrarily Small Network Loads Matthew Andrews
    2:50 PM On the Separation and Equivalence of Paging Strategies Spyros Angelopoulos, Reza Dorrigiv and Alejandro Lopez-Ortiz
    3:15 PM Pull-Based Data Broadcast with Dependencies: Be Fair to Users, Not to Items Julien Robert and Nicolas Schabanel
    3:40 PM Improved Bounds for the Online Steiner Tree Problem in Graphs of Bounded Edge-Asymmetry Spyros Angelopoulos
    Concurrent Sessions 2:00 PM - 4:05 PM 3C 2:00 PM Minimizing Movement Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, Amin Sayedi, Shayan Oveisgharan and Morteza Zadimoghaddam
    2:25 PM Optimization Problems in Multiple-interval Graphs Ayelet Butman, Danny Hermelin, Moshe Lewenstein and Dror Rawitz
    2:50 PM Approximation Algorithms via Contraction Decomposition Erik D. Demaine, MohammadTaghi Hajiaghayi and Bojan Mohar
    3:15 PM A 1.875--Approximation Algorithm for the Stable Marriage Problem Kazuo Iwama, Shuichi Miyazaki and Naoya Yamauchi
    3:40 PM Improved Algorithms for Path, Matching, and Packing Problems Jianer Chen, Songjian Lu, Sing-Hoi Sze and Fenghui Zhang
    Coffee Break   4:05 PM - 4:30 PM    
    Concurrent Sessions 4:30 PM - 6:35 PM 4A 4:30 PM Model-driven Optimization Using Adaptive Probes Sudipto Guha and Kamesh Munagala
    4:55 PM Estimating the Sortedness of a Data Stream Parikshit Gopalan, T.S. Jayram, Robert Krauthgamer and Ravi Kumar
    5:20 PM A Near-Optimal Algorithm for Computing the Entropy of a Stream Amit Chakrabarti, Graham Cormode and Andrew McGregor
    5:45 PM The Communication and Streaming Complexity of Computing the Longest Common and Increasing Subsequences Xiaoming Sun and David P. Woodruff
    6:10 PM Efficient Aggregation Algorithms for Probabilistic Data T.S. Jayram, Satyen Kale and Erik Vee
    Concurrent Sessions 4:30 PM - 6:35 PM 4B 4:30 PM Multiple Choice Tries and Distributed Hash Tables Luc Devroye, Gabor Lugosi, Gahyun Park, Wojciech Szpankowski
    4:55 PM Approximating Entrpoy from Sublinear Samples Mickey Brautbar and Alex Samorodnitsky
    5:20 PM Torpid Mixing of Local Markov Chains on 3-Colorings of the Discrete Torus David Galvin and Dana Randall
    5:45 PM Probabilistic Analysis of Linear Programming Decoding Konstantinos Daskalakis, Alex Dimakis, Richard Karp and Martin Wainwright
    6:10 PM Scrambling Adversarial Errors Using Few Random Bits Adam Smith
    Concurrent Sessions 4:30 PM - 6:35 PM 4C 4:30 PM Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems Anke van Zuylen, Rajneesh Hegde, Kamal Jain and David P. Williamson 
    4:55 PM Aggregation of Partial Rankings, p-Ratings and Top-m Lists Nir Ailon
    5:20 PM Algorithms and Incentives for Robust Ranking Rajat Bhattacharjee and Ashish Goel
    5:45 PM A Matroid Secretary Problem Moshe Babaioff, Nicole Immorlica and Robert Kleinberg
    6:10 PM An Algebraic Algorithm for Weighted Linear Matroid Intersection Nicholas J. A. Harvey
             
Monday 8-Jan Registration   8:00 AM - 4:45 PM    
    Continental Breakfast   8:30 AM    
    Concurrent Sessions 9:00 AM - 11:05 AM 5A 9:00 AM An Elementary Construction of Constant-Degree Expanders Noga Alon, Oded Schwartz and Asaf Shapira
    9:25 AM The k-orientability Thresholds for G_{n,p} & The Random Graph Threshold for k-orientiability and a Fast Algorithm for Optimal Multiple-Choice Allocation Daniel Fernholz and Vijaya Ramachandran, Julie Cain, Peter Sanders and Nick Wormald
    9:50 AM On Extremal Subgraphs of Random Graphs Graham Brightwell, Konstantinos Panagiotou and Angelika Steger
    10:15 AM Online Vertex Colorings of Random Graphs Without Monochromatic Subgraphs Martin Marciniszyn and Reto Spöhel
    10:40 AM On Testable Properties in Bounded Degree Graphs Artur Czumaj and Christian Sohler
    Concurrent Sessions 9:00 AM - 11:05 AM 5B 9:00 AM Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion Ittai Abraham, Yair Bartal and Ofer Neiman 
    9:25 AM Approximation Algorithms for Embedding General Metrics Into Trees Mihai Badoiu, Piotr Indyk and Anastasios Sidiropoulos
    9:50 AM Embedding into $l^2_{\infty}$ is Easy, Embedding into $l^3_{\infty}$ is NP-Complete  Jeff Edmonds
    10:15 AM Efficient Subspace Approximation Algorithms N. D. Shyamalkumar and K. Varadarajan
    10:40 AM A Divide and Conquer Algorithm for d-Dimensional Arrangement Moses Charikar, Konstantin Makarychev and Yury Makarychev
    Concurrent Sessions 9:00 AM - 11:05 AM 5C 9:00 AM Resilient Search Trees Irene Finocchi, Fabrizio Grandoni and Giuseppe F. Italiano
    9:25 AM Randomization Does Not Help Searching Predecessors Mihai Patrascu and Mikkel Thorup
    9:50 AM Dynamic Weighted Ancestors Tsvi Kopelowitz and Moshe Lewenstein
    10:15 AM Ultra-succinct Representation of Ordered Trees Jesper Jansson, Kunihiko Sadakane and Wing-Kin Sung
    10:40 AM Tree Exploration with Logarithmic Memory Gasieniec, Pelc, Radzik and Zhang
    Coffee Break   11:05 AM - 11:30 AM    
    Invited Plenary Session    6 11:30 AM - 12:30 PM Combinatorial Algorithms for Web Search Engines -- Three Success Stories Monika R. Henzinger, Google Inc & Ecole Polytechnique Federal de Lausanne (EPFL)
    Lunch (attendees on their own)   12:30 PM - 2:00 PM    
    Concurrent Sessions 2:00 PM - 4:05 PM 7A 2:00 PM Deterministic Rendezvous, Treasure Hunts and Strongly Universal Exploration Sequences Amnon Ta-Shma and Uri Zwick 
    2:25 PM Planar Graphs are in 1-STRING J. Chalopin, D. Gonçalves and P. Ochem
    2:50 PM The Bandwidth Conjecture for 3-colourable Graphs Julia Boettcher, Mathias Schacht and Anusch Taraz
    3:15 PM Sandpile Transience on the Grid is Polynomially Bounded Laszlo Babai and Igor Gorodezky
    3:40 PM Digraph Measures: Kelly Decompositions, Games, and Orderings Paul Hunter and Stephan Kreutzer
    Concurrent Sessions 2:00 PM - 4:05 PM 7B 2:00 PM Approximating the Spanning Star Forest Problem and Its Applications to Genomic Sequence Alignment C. Thach Nguyen, Jian Shen, Minmei Hou, Li Sheng, Webb Miller and Louxin Zhang
    2:25 PM Fast Elimination of Redundant Linear Equations and Reconstruction of Recombination-Free Mendelian Inheritance on a Pedigree Jing Xiao, Lan Liu, Lirong Xia and Tao Jiang
    2:50 PM Whole Genome Duplications, Multi-Break Rearrangements, and Genome Halving Problem
 Max A. Alekseyev and Pavel A. Pevzner
    3:15 PM Succinct Indexes for Strings, Binary Relations and Multi-labeled Trees J\'er\'emy Barbay, Meng He, J. Ian Munro and S. Srinivasa Rao
    3:40 PM A Simple Storage Scheme for Strings Achieving Entropy Bounds Paolo Ferragina and Rossano Venturini
    Concurrent Sessions 2:00 PM - 4:05 PM 7C 2:00 PM A Network Formation Game for Bipartite Exchange Economies Eyal Even-Dar, Michael Kearns and Siddharth Suri
    2:25 PM Cheap Labor Can Be Expensive Ning Chen and Anna R. Karlin
    2:50 PM Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing Patrick Briest and Piotr Krysta
    3:15 PM Dynamic Pricing for Impatient Bidders Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rudra, Baruch Schieber and Maxim Sviridenko
    3:40 PM Designing And Learning Optimal Finite Support Auctions Edith Elkind
    Coffee Break   4:05 PM - 4:30 PM    
    Concurrent Sessions 4:30 PM - 6:35 PM 8A 4:30 PM On Bregman Voronoi Diagrams Frank Nielsen, Jean-Daniel Boissonnat and Richard Nock
    4:55 PM Zone Diagrams, Existence, Uniqueness, and Algorithmic Challenge Tetsuo Asano, Jiri Matousek and Takeshi Tokuyama
    5:20 PM Approximate Shortest Paths in Anisotropic Regions Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron and Yajun Wang
    5:45 PM On Bounded Leg Shortest Paths Problems Liam Roditty and Michael Segal
    6:10 PM Counting Colors in Boxes Haim Kaplan, Natan Rubin, Micha Sharir and Elad Verbin
    Concurrent Sessions 4:30 PM - 6:35 PM 8B 4:30 PM Energy Efficient Online Deadline Scheduling HL Chan, WT Chan, TW Lam, LK Lee, KS Mak, and P Wong
    4:55 PM Speed Scaling for Weighted Flow Time Nikhil Bansal, Kirk Pruhs and Cliff Stein
    5:20 PM Path-Independent Load Balancing With Unreliable Machines James Aspnes, Richard Yang and Yitong Yin
    5:45 PM Layered Multicast Scheduling for the L_infinity Objective Qingbo Cai and Vincenzo Liberatore
    6:10 PM Lower Bounds on Average-case Delay for Video-on-Demand Broadcast Protocols Wei-Lung Dustin Tseng and David Kirkpatrick
    Concurrent Sessions 4:30 PM - 6:35 PM 8C 4:30 PM Maximum $s$-$t$-flow with $k$ Crossings in $O(k^3 n \log n)$~time Jan M. Hochstein and Karsten Weihe
    4:55 PM Matrix Scaling by Network Flow G\"unter Rote and Martin Zachariasen
    5:20 PM Single Source Multiroute Flows and Cuts on Uniform Capacity Networks Henning Bruhn, Jakub Cerny, Alexander Hall and Petr Kolman
    5:45 PM Island Hopping and Path Colouring with Applications to WDM Network Design Andrew McGregor and Bruce Shepherd
    6:10 PM Maximum Independent Sets in Graphs of Low Degree Vadim Lozin and Martin Milanic
    Business Meeting   7:00 PM - 8:00 PM    
             
Tuesday 9-Jan Registration   8:00 AM - 4:45 PM    
    Continental Breakfast   8:30 AM    
    Concurrent Sessions 9:00 AM - 11:05 AM 9A 9:00 AM An Unbiased Pointing Operator for Unlabeled Structures, with Applications to Counting and Sampling Manuel Bodirsky, Eric Fusy, Mihyun Kang, Stefan Vigerske
    9:25 AM Noisy Binary Search and its Applications Richard M. Karp and Robert Kleinberg
    9:50 AM Making Deterministic Signatures Quickly Milan Ruzic
    10:15 AM A Faster Cache-Oblivious Shortest-Path Algorithm for Undirected Graphs with Bounded Edge Lengths Luca Allulli, Peter Lichodzijewski and Norbert Zeh
    10:40 AM On the k-simple Shortest Paths Problem in Weighted Directed Graphs Liam Roditty
    Concurrent Sessions 9:00 AM - 11:05 AM 9B 9:00 AM Semi-oblivious Routing: Lower Bounds MohammadTaghi Hajiaghayi, Robert Kleinberg and Tom Leighton
    9:25 AM Optimal Scale-free Compact Routing Schemes in Networks of Low Doubling Dimension Goran Konjevod, Andrea W. Richa and Donglin Xia
    9:50 AM Distributed Algorithms for Multicommodity Flow Problems via Approximate Steepest Descent Framework Baruch Awerbuch, Rohit Khandekar and Satish Rao
    10:15 AM Network Sketching or: "How Much Geometry Hides in Connectivity? -- Part II" Stefan Funke and Nikola Milosavljevic
    10:40 AM Line-of-Sight Networks Alan Frieze, Jon Kleinberg, R. Ravi and Warren Debany
    Concurrent Sessions 9:00 AM - 11:05 AM 9C 9:00 AM All-Pairs Bottleneck Paths in Vertex Weighted Graphs Asaf Shapira, Raphael Yuster and Uri Zwick
    9:25 AM Finding a Heaviest Triangle is not Harder than Matrix Multiplication Artur Czumaj and Andrzej Lingas
    9:50 AM Matrix-Vector Multiplication in Sub-Quadratic Time (Some Preprocessing Required) Ryan Williams
    10:15 AM A Linear Work, $O(n^{1/6})$ Time, Parallel Algorithm for Solving Planar Laplacians  Ioannis Koutis and Gary Miller
    10:40 AM Fast Computation of Power Series Solutions of Systems of Differential Equations Alin Bostan, Frédéric Chyzak, François Ollivier, Bruno Salvy, Éric Schost and Alexandre Sedoglavic
    Coffee Break   11:05 AM - 11:30 AM    
    Invited Plenary Session    10 11:30 AM - 12:30 PM Testing for a Theta Maria Chudnovsky, Columbia University & Clay Mathematics Institute
    Lunch (attendees on their own)   12:30 PM - 2:00 PM    
    Concurrent Sessions 2:00 PM - 4:05 PM 11A 2:00 PM k-means++: The Advantages of Careful Seeding David Arthur and Sergei Vassilvitskii
    2:25 PM Spectral Clustering with Limited Independence Anirban Dasgupta, John Hopcroft, Ravi Kannan and Pradipta Mitra
    2:50 PM Separating Populations with Small Data Kamalika Chaudhuri, Eran Halperin, Satish Rao and Shuheng Zhou
    3:15 PM Restricted Strip Covering and the Sensor Cover Problem Adam L. Buchsbaum, Alon Efrat, Shaili Jain, Suresh Venkatasubramanian and Ke Yi
    3:40 PM Compressing Rectilinear Pictures and Minimizing Access Control Lists David A. Applegate, Gruia Calinescu, David S. Johnson, Howard Karloff, Katrina Ligett and Jia Wang
    Concurrent Sessions 2:00 PM - 4:05 PM 11B 2:00 PM Reconstruction Using Witness Complexes Leonidas J. Guibas and Steve Y. Oudot
    2:25 PM Geometric and Topological Guarantees for the Wrap Reconstruction Algorithm Edgar A. Ramos and Bardia Sadri
    2:50 PM Delaunay Refinement for Piecewise Smooth Complexes Siu-Wing Cheng, Tamal K. Dey and Edgar A. Ramos
    3:15 PM Complexity of Delaunay Triangulation for Points on Lower-dimensional Polyhedra Nina Amenta, Dominique Attali and Olivier Devillers
    3:40 PM On the Number of Tetrahedra with Minimum, Unit, and Distinct Volumes in Three-space Adrian Dumitrescu and Csaba D. T\'oth
    Concurrent Sessions 2:00 PM - 4:05 PM 11C 2:00 PM Games of Fixed Rank: A Hierarchy of Bimatrix Games Ravi Kannan and Thorsten Theobald
    2:25 PM The Effectiveness of Stackelberg Strategies and Tolls for Network Congestion Games Chaitanya Swamy
    2:50 PM Setting Lower Bounds on Truthfulness Ahuva Mu'alem and Michael Schapira
    3:15 PM An Efficient Cost-Sharing Mechanism for the Prize-Collecting Steiner Forest Problem A. Gupta, J. Konemann, S. Leonardi, R. Ravi and G. Schaefer
    3:40 PM A Lower Bound for Scheduling Mechanisms George Christodoulou, Elias Koutsoupias and Angelina Vidali
    Coffee Break   4:05 PM - 4:30 PM    
    Concurrent Sessions 4:30 PM - 6:35 PM 12A 4:30 PM The Independent Even Factor Problem Satoru Iwata and Kenjiro Takazawa
    4:55 PM Fractional Packing in Ideal Clutters Yuji Matsuoka
    5:20 PM Half Integral Packing, Erd\H{o}s-Pos\'a-Property and Graph Minors Ken-ichi Kawarabayashi
    5:45 PM New Upper Bounds on The Approximability of 3D Strip Packing & Harmonic Algorithm for 3-Dimensional Strip Packing Problem  Xin Han, Kazuo Iwama and Guochuan Zhang, Nikhil Bansal and Maxim Sviridenko
    6:10 PM Polynomial Approximation Schemes for Smoothed And Random Instances of Multidimensional Bin Packing David Karger and Krzysztof Onak
    Concurrent Sessions 4:30 PM - 6:35 PM 12B 4:30 PM Quantum Algorithms for Simon's Problem over General Groups Gorjan Alagic, Cristopher Moore and Alexander Russell
    4:55 PM Quantum Algorithm for a Generalized Hidden Shift Problem Andrew M. Childs and Wim van Dam
    5:20 PM The Quantum Schur and Clebsch-Gordan Transforms:I. Efficient Qudit Circuits Dave Bacon, Isaac L. Chuang and Aram W. Harrow
    5:45 PM Correlation Decay and Deterministic FPTAS for Counting List-colorings of a Graph David Gamarnik and Dmitriy Katz 
    6:10 PM Counting Good Truth Assignments of Random $k$-SAT Formulae Andrea Montanari and Devavrat Shah
    Concurrent Sessions 4:30 PM - 6:35 PM 12C 4:30 PM Approximation Algorithms for Network Design Problems with Node Weights  Chandra Chekuri, MohammadTaghi Hajiaghayi, Guy Kortsarz and Mohammad R. Salavatipour
    4:55 PM A 3-approximation Algorithm for Prize Collecting Forest Problems with Submodular Penalty Functions Yogeshwer Sharma and David P. Williamson
    5:20 PM A Polynomial-Time Approximation Scheme for Steiner Tree in Planar Graphs Glencora Borradaile, Claire Kenyon-Mathieu and Philip Klein
    5:45 PM Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP Matthias Englert, Heiko Roeglin and Berthold Voecking
    6:10 PM Approximation Algorithms for Stochastic and Risk-averse Optimization Aravind Srinivasan
    Conference Adjourns   6:35 PM    

 

Donate · Contact Us · Site Map · Join SIAM · My Account
Facebook Twitter Youtube linkedin google+