18. SODA 2007: New Orleans, Louisiana, USA
Nikhil Bansal, Kirk Pruhs, Clifford Stein (Eds.): Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007. SIAM 2007 ISBN 978-0-898716-24-5- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Amnon Ta-Shma, Uri Zwick: Deterministic rendezvous, treasure hunts and strongly universal exploration sequences. 599-608
- Julia Böttcher, Mathias Schacht, Anusch Taraz: On the bandwidth conjecture for 3-colourable graphs. 618-626
- 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
- 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
- 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
- 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
- James Aspnes, Yang Richard Yang, Yitong Yin: Path-independent load balancing with unreliable machines. 814-823
- Wei-Lung Dustin Tseng, David G. Kirkpatrick: Lower bounds on average-case delay for video-on-demand broadcast protocols. 834-842
- 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
- 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
- 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(n1/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
- 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
- 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
- Chaitanya Swamy: The effectiveness of Stackelberg strategies and tolls for network congestion games. 1133-1142
- 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
- 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
- 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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T211851 by the dblp team