default search action
18th SODA 2007: New Orleans, Louisiana, USA
- Nikhil Bansal, Kirk Pruhs, Clifford Stein:
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 - 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 J. 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 D. 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 Gn, 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 R. 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
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 Linfinity 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(k3n 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, F. 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(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 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 L. 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 W. 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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-12 21:04 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: