18. SODA 2007: New Orleans, Louisiana, USA

• Mohammad Ali Abam, Mark de Berg, Mohammad Farshi, Joachim Gudmundsson:
  Region-fault tolerant geometric spanners. 1-10
  
• Joseph S. B. Mitchell:
  A PTAS for TSP with neighborhoods among fat regions in the plane. 11-18
  
• Yoav Giyora, Haim Kaplan:
  Optimal dynamic vertical ray shooting in rectilinear planar subdivisions. 19-28
  
• David Eppstein:
  Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition. 29-38
  
• Piotr Indyk:
  A near linear time constant factor approximation for Euclidean bichromatic matching (cost). 39-42
  
• Robert D. Carr, Goran Konjevod, Greg Little, Venkatesh Natarajan, Ojas Parekh:
  Compacting cuts: a new linear formulation for minimum cut. 43-52
  
• Wenceslas Fernandez de la Vega, Claire Kenyon-Mathieu:
  Linear programming relaxations of maxcut. 53-61
  
• Moses Charikar, Konstantin Makarychev, Yury Makarychev:
  Near-optimal algorithms for maximum constraint satisfaction problems. 62-68
  
• Qiaoming Han, Donglei Du, Juan Carlos Vera, Luis Fernando Zuluaga:
  Improved bounds for the symmetric rendezvous value on the line. 69-78
  
• Fabián A. Chudak, Kiyohito Nagano:
  Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovász extension and non-smooth convex optimization. 79-88
  
• Sergio Cabello, Erin W. Chambers:
  Multiple source shortest paths in a genus g graph. 89-97
  
• Sergio Cabello, Günter Rote:
  Obnoxious centers in graphs. 98-107
  
• Raphael Yuster, Uri Zwick:
  Maximum matching in graphs with an excluded minor. 108-117
  
• Piotr Sankowski:
  Faster dynamic matchings and vertex connectivity. 118-126
  
• Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi:
  Efficient algorithms for computing all low s-t edge connectivities and related problems. 127-136
  
• Philippe Flajolet:
  Analytic combinatorics: a calculus of discrete structures. 137-148
  
• Roee Engelberg, Joseph Naor:
  Equilibria in online games. 149-158
  
• Xi Chen, Shang-Hua Teng, Paul Valiant:
  The approximation complexity of win-lose games. 159-168
  
• Steve Chien, Alistair Sinclair:
  Convergence to approximate Nash equilibria in congestion games. 169-178
  
• Amos Fiat, Yishay Mansour, Uri Nadav:
  Efficient contention resolution protocols for selfish agents. 179-188
  
• Nir Andelman, Michal Feldman, Yishay Mansour:
  Strong price of anarchy. 189-198
  
• Fei Li, Jay Sethuraman, Clifford Stein:
  Better online buffer management. 199-208
  
• Matthias Englert, Matthias Westermann:
  Considering suppressed packets improves buffer management in QoS switches. 209-218
  
• Matthew Andrews:
  Instability of FIFO in the permanent sessions model at arbitrarily small network loads. 219-228
  
• Spyros Angelopoulos, Reza Dorrigiv, Alejandro López-Ortiz:
  On the separation and equivalence of paging strategies. 229-237
  
• Julien Robert, Nicolas Schabanel:
  Pull-based data broadcast with dependencies: be fair to users, not to items. 238-247
  
• Spyros Angelopoulos:
  Improved bounds for the online steiner tree problem in graphs of bounded edge-asymmetry. 248-257
  
• Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, Morteza Zadimoghaddam:
  Minimizing movement. 258-267
  
• Ayelet Butman, Danny Hermelin, Moshe Lewenstein, Dror Rawitz:
  Optimization problems in multiple-interval graphs. 268-277
  
• Erik D. Demaine, Mohammad Taghi Hajiaghayi, Bojan Mohar:
  Approximation algorithms via contraction decomposition. 278-287
  
• Kazuo Iwama, Shuichi Miyazaki, Naoya Yamauchi:
  A 1.875: approximation algorithm for the stable marriage problem. 288-297
  
• Jianer Chen, Songjian Lu, Sing-Hoi Sze, Fenghui Zhang:
  Improved algorithms for path, matching, and packing problems. 298-307
  
• Sudipto Guha, Kamesh Munagala:
  Model-driven optimization using adaptive probes. 308-317
  
• Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, Ravi Kumar:
  Estimating the sortedness of a data stream. 318-327
  
• Amit Chakrabarti, Graham Cormode, Andrew McGregor:
  A near-optimal algorithm for computing the entropy of a stream. 328-335
  
• Xiaoming Sun, David P. Woodruff:
  The communication and streaming complexity of computing the longest common and increasing subsequences. 336-345
  
• T. S. Jayram, Satyen Kale, Erik Vee:
  Efficient aggregation algorithms for probabilistic data. 346-355
  
• Manuel Bodirsky, Éric Fusy, Mihyun Kang, Stefan Vigerske:
  An unbiased pointing operator for unlabeled structures, with applications to counting and sampling. 356-365
  
• Mickey Brautbar, Alex Samorodnitsky:
  Approximating entropy from sublinear samples. 366-375
  
• David Galvin, Dana Randall:
  Torpid mixing of local Markov chains on 3-colorings of the discrete torus. 376-384
  
• Constantinos Daskalakis, Alexandros G. Dimakis, Richard M. Karp, Martin J. Wainwright:
  Probabilistic analysis of linear programming decoding. 385-394
  
• Adam Smith:
  Scrambling adversarial errors using few random bits, optimal information reconciliation, and better private codes. 395-404
  
• Anke van Zuylen, Rajneesh Hegde, Kamal Jain, David P. Williamson:
  Deterministic pivoting algorithms for constrained ranking and clustering problems. 405-414
  
• Nir Ailon:
  Aggregation of partial rankings, p-ratings and top-m lists. 415-424
  
• Rajat Bhattacharjee, Ashish Goel:
  Algorithms and incentives for robust ranking. 425-433
  
• Moshe Babaioff, Nicole Immorlica, Robert Kleinberg:
  Matroids, secretary problems, and online mechanisms. 434-443
  
• Nicholas J. A. Harvey:
  An algebraic algorithm for weighted linear matroid intersection. 444-453
  
• Noga Alon, Oded Schwartz, Asaf Shapira:
  An elementary construction of constant-degree expanders. 454-458
  
• Daniel Fernholz, Vijaya Ramachandran:
  The k-orientability thresholds for G_{n, p}. 459-468
  
• Julie Anne Cain, Peter Sanders, Nicholas C. Wormald:
  The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation. 469-476
  
• Graham Brightwell, Konstantinos Panagiotou, Angelika Steger:
  On extremal subgraphs of random graphs. 477-485
  
• Martin Marciniszyn, Reto Spöhel:
  Online vertex colorings of random graphs without monochromatic subgraphs. 486-493
  
• Artur Czumaj, Christian Sohler:
  On testable properties in bounded degree graphs. 494-501
  
• Ittai Abraham, Yair Bartal, Ofer Neiman:
  Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion. 502-511
  
• Mihai Badoiu, Piotr Indyk, Anastasios Sidiropoulos:
  Approximation algorithms for embedding general metrics into trees. 512-521
  
• Nariankadu D. Shyamalkumar, Kasturi R. Varadarajan:
  Efficient subspace approximation algorithms. 532-540
  
• Moses Charikar, Konstantin Makarychev, Yury Makarychev:
  A divide and conquer algorithm for d-dimensional arrangement. 541-546
  
• Irene Finocchi, Fabrizio Grandoni, Giuseppe F. Italiano:
  Resilient search trees. 547-553
  
• Mihai Patrascu, Mikkel Thorup:
  Randomization does not help searching predecessors. 555-564
  
• Tsvi Kopelowitz, Moshe Lewenstein:
  Dynamic weighted ancestors. 565-574
  
• Jesper Jansson, Kunihiko Sadakane, Wing-Kin Sung:
  Ultra-succinct representation of ordered trees. 575-584
  
• Leszek Gasieniec, Andrzej Pelc, Tomasz Radzik, Xiaohui Zhang:
  Tree exploration with logarithmic memory. 585-594
  
• Maria Chudnovsky, Paul D. Seymour:
  Testing for a theta. 595-598
  
• Amnon Ta-Shma, Uri Zwick:
  Deterministic rendezvous, treasure hunts and strongly universal exploration sequences. 599-608
  
• Jérémie Chalopin, Daniel Gonçalves, Pascal Ochem:
  Planar graphs are in 1-STRING. 609-617
  
• Julia Böttcher, Mathias Schacht, Anusch Taraz:
  On the bandwidth conjecture for 3-colourable graphs. 618-626
  
• László Babai, Igor Gorodezky:
  Sandpile transience on the grid is polynomially bounded. 627-636
  
• Paul Hunter, Stephan Kreutzer:
  Digraph measures: Kelly decompositions, games, and orderings. 637-644
  
• C. Thach Nguyen, Jian Shen, Minmei Hou, Li Sheng, Webb Miller, Louxin Zhang:
  Approximating the spanning star forest problem and its applications to genomic sequence alignment. 645-654
  
• Jing Xiao, Lan Liu, Lirong Xia, Tao Jiang:
  Fast elimination of redundant linear equations and reconstruction of recombination-free mendelian inheritance on a pedigree. 655-664
  
• Max A. Alekseyev, Pavel A. Pevzner:
  Whole genome duplications, multi-break rearrangements, and genome halving problem. 665-679
  
• Jérémy Barbay, Meng He, J. Ian Munro, S. Srinivasa Rao:
  Succinct indexes for strings, binary relations and multi-labeled trees. 680-689
  
• Paolo Ferragina, Rossano Venturini:
  A simple storage scheme for strings achieving entropy bounds. 690-696
  
• Eyal Even-Dar, Michael J. Kearns, Siddharth Suri:
  A network formation game for bipartite exchange economies. 697-706
  
• Ning Chen, Anna R. Karlin:
  Cheap labor can be expensive. 707-715
  
• Patrick Briest, Piotr Krysta:
  Buying cheap is expensive: hardness of non-parametric multi-product pricing. 716-725
  
• Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rudra, Baruch Schieber, Maxim Sviridenko:
  Dynamic pricing for impatient bidders. 726-735
  
• Edith Elkind:
  Designing and learning optimal finite support auctions. 736-745
  
• Frank Nielsen, Jean-Daniel Boissonnat, Richard Nock:
  On Bregman Voronoi diagrams. 746-755
  
• Tetsuo Asano, Jirí Matousek, Takeshi Tokuyama:
  Zone diagrams: existence, uniqueness and algorithmic challenge. 756-765
  
• Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, Yajun Wang:
  Approximate shortest paths in anisotropic regions. 766-774
  
• Liam Roditty, Michael Segal:
  On bounded leg shortest paths problems. 775-784
  
• Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin:
  Counting colors in boxes. 785-794
  
• Ho-Leung Chan, Wun-Tat Chan, Tak Wah Lam, Lap-Kei Lee, Kin-Sum Mak, Prudence W. H. Wong:
  Energy efficient online deadline scheduling. 795-804
  
• Nikhil Bansal, Kirk Pruhs, Clifford Stein:
  Speed scaling for weighted flow time. 805-813
  
• James Aspnes, Yang Richard Yang, Yitong Yin:
  Path-independent load balancing with unreliable machines. 814-823
  
• Qingbo Cai, Vincenzo Liberatore:
  Layered multicast scheduling for the L_infinity objective. 824-833
  
• Wei-Lung Dustin Tseng, David G. Kirkpatrick:
  Lower bounds on average-case delay for video-on-demand broadcast protocols. 834-842
  
• Jan M. Hochstein, Karsten Weihe:
  Maximum s-t-flow with k crossings in O(k³n log n) time. 843-847
  
• Günter Rote, Martin Zachariasen:
  Matrix scaling by network flow. 848-854
  
• Henning Bruhn, Jakub Cerný, Alexander Hall, Petr Kolman:
  Single source multiroute flows and cuts on uniform capacity networks. 855-863
  
• Andrew McGregor, Bruce Shepherd:
  Island hopping and path colouring with applications to WDM network design. 864-873
  
• Vadim V. Lozin, Martin Milanic:
  Maximum independent sets in graphs of low degree. 874-880
  
• Richard M. Karp, Robert Kleinberg:
  Noisy binary search and its applications. 881-890
  
• Luc Devroye, Gábor Lugosi, GaHyun Park, Wojciech Szpankowski:
  Multiple choice tries and distributed hash tables. 891-899
  
• Milan Ruzic:
  Making deterministic signatures quickly. 900-909
  
• Luca Allulli, Peter Lichodzijewski, Norbert Zeh:
  A faster cache-oblivious shortest-path algorithm for undirected graphs with bounded edge lengths. 910-919
  
• Liam Roditty:
  On the K-simple shortest paths problem in weighted directed graphs. 920-928
  
• Mohammad Taghi Hajiaghayi, Robert Kleinberg, Tom Leighton:
  Semi-oblivious routing: lower bounds. 929-938
  
• Goran Konjevod, Andréa W. Richa, Donglin Xia:
  Optimal scale-free compact routing schemes in networks of low doubling dimension. 939-948
  
• Baruch Awerbuch, Rohit Khandekar, Satish Rao:
  Distributed algorithms for multicommodity flow problems via approximate steepest descent framework. 949-957
  
• Stefan Funke, Nikola Milosavljevic:
  Network sketching or: "How Much Geometry Hides in Connectivity?--Part II". 958-967
  
• Alan M. Frieze, Jon M. Kleinberg, R. Ravi, Warren Debany:
  Line-of-sight networks. 968-977
  
• Asaf Shapira, Raphael Yuster, Uri Zwick:
  All-pairs bottleneck paths in vertex weighted graphs. 978-985
  
• Artur Czumaj, Andrzej Lingas:
  Finding a heaviest triangle is not harder than matrix multiplication. 986-994
  
• Ryan Williams:
  Matrix-vector multiplication in sub-quadratic time: (some preprocessing required). 995-1001
  
• Ioannis Koutis, Gary L. Miller:
  A linear work, O(n^1/6) time, parallel algorithm for solving planar Laplacians. 1002-1011
  
• Alin Bostan, Frédéric Chyzak, François Ollivier, Bruno Salvy, Éric Schost, Alexandre Sedoglavic:
  Fast computation of power series solutions of systems of differential equations. 1012-1021
  
• Monika Rauch Henzinger:
  Combinatorial algorithms for web search engines: three success stories. 1022-1026
  
• David Arthur, Sergei Vassilvitskii:
  k-means++: the advantages of careful seeding. 1027-1035
  
• Anirban Dasgupta, John E. Hopcroft, Ravi Kannan, Pradipta Prometheus Mitra:
  Spectral clustering with limited independence. 1036-1045
  
• Kamalika Chaudhuri, Eran Halperin, Satish Rao, Shuheng Zhou:
  A rigorous analysis of population stratification with limited data. 1046-1055
  
• Adam L. Buchsbaum, Alon Efrat, Shaili Jain, Suresh Venkatasubramanian, Ke Yi:
  Restricted strip covering and the sensor cover problem. 1056-1063
  
• David Applegate, Gruia Calinescu, David S. Johnson, Howard J. Karloff, Katrina Ligett, Jia Wang:
  Compressing rectilinear pictures and minimizing access control lists. 1066-1075
  
• Leonidas J. Guibas, Steve Oudot:
  Reconstruction using witness complexes. 1076-1085
  
• Edgar A. Ramos, Bardia Sadri:
  Geometric and topological guarantees for the WRAP reconstruction algorithm. 1086-1095
  
• Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos:
  Delaunay refinement for piecewise smooth complexes. 1096-1105
  
• Nina Amenta, Dominique Attali, Olivier Devillers:
  Complexity of Delaunay triangulation for points on lower-dimensional polyhedra. 1106-1113
  
• Adrian Dumitrescu, Csaba D. Tóth:
  On the number of tetrahedra with minimum, unit, and distinct volumes in three-space. 1114-1123
  
• Ravi Kannan, Thorsten Theobald:
  Games of fixed rank: a hierarchy of bimatrix games. 1124-1132
  
• Chaitanya Swamy:
  The effectiveness of Stackelberg strategies and tolls for network congestion games. 1133-1142
  
• Ahuva Mu'alem, Michael Schapira:
  Setting lower bounds on truthfulness: extended abstract. 1143-1152
  
• Anupam Gupta, Jochen Könemann, Stefano Leonardi, R. Ravi, Guido Schäfer:
  An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem. 1153-1162
  
• George Christodoulou, Elias Koutsoupias, Angelina Vidali:
  A lower bound for scheduling mechanisms. 1163-1170
  
• Satoru Iwata, Kenjiro Takazawa:
  The independent even factor problem. 1171-1180
  
• Yuji Matsuoka:
  Fractional packing in ideal clutters. 1181-1186
  
• Ken-ichi Kawarabayashi:
  Half integral packing, Erdős-Posá-property and graph minors. 1187-1196
  
• Nikhil Bansal, Xin Han, Kazuo Iwama, Maxim Sviridenko, Guochuan Zhang:
  Harmonic algorithm for 3-dimensional strip packing problem. 1197-1206
  
• David R. Karger, Krzysztof Onak:
  Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems. 1207-1216
  
• Gorjan Alagic, Cristopher Moore, Alexander Russell:
  Quantum algorithms for Simon's problem over general groups. 1217-1224
  
• Andrew M. Childs, Wim van Dam:
  Quantum algorithm for a generalized hidden shift problem. 1225-1232
  
• Dave Bacon, Isaac L. Chuang, Aram Wettroth Harrow:
  The quantum Schur and Clebsch-Gordan transforms: I. efficient qudit circuits. 1235-1244
  
• David Gamarnik, Dmitriy Katz:
  Correlation decay and deterministic FPTAS for counting list-colorings of a graph. 1245-1254
  
• Andrea Montanari, Devavrat Shah:
  Counting good truth assignments of random k-SAT formulae. 1255-1264
  
• Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour:
  Approximation algorithms for node-weighted buy-at-bulk network design. 1265-1274
  
• Yogeshwer Sharma, Chaitanya Swamy, David P. Williamson:
  Approximation algorithms for prize collecting forest problems with submodular penalty functions. 1275-1284
  
• Glencora Borradaile, Claire Kenyon-Mathieu, Philip N. Klein:
  A polynomial-time approximation scheme for Steiner tree in planar graphs. 1285-1294
  
• Matthias Englert, Heiko Röglin, Berthold Vöcking:
  Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP: extended abstract. 1295-1304
  
• Aravind Srinivasan:
  Approximation algorithms for stochastic and risk-averse optimization. 1305-1313
  

Last update Wed Feb 15 05:18:35 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page