default search action
19th SODA 2008: San Francisco, California, USA
- Shang-Hua Teng:
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008. SIAM 2008 - Nir Ailon, Edo Liberty:
Fast dimension reduction using Rademacher series on dual BCH codes. 1-9 - Ping Li:
Estimators and tail bounds for dimension reduction in lα (0 < α ≤ 2) using stable random projections. 10-19 - Mark A. Iwen:
A deterministic sub-linear time sparse fourier algorithm via non-adaptive compressed sensing methods. 20-29 - Piotr Indyk:
Explicit constructions for compressed sensing of sparse signals. 30-33 - Aaron Bernstein, David R. Karger:
Improved distance sensitivity oracles via random sampling. 34-43 - S. Thomas McCormick, Satoru Fujishige:
Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization. 44-53 - Jin-yi Cai, Pinyan Lu:
Holographic algorithms with unsymmetric signatures. 54-63 - Guy Kindler, Assaf Naor, Gideon Schechtman:
The UGC hardness threshold of the ℓp Grothendieck problem. 64-73 - Ilias Diakonikolas, Mihalis Yannakakis:
Succinct approximate convex pareto curves. 74-83 - Daniele Micciancio:
Efficient reductions among lattice problems. 84-93 - Xiaomin Chen, János Pach, Mario Szegedy, Gábor Tardos:
Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. 94-101 - Raghavan Dhandapani:
Greedy drawings of triangulations. 102-111 - Siu-Wing Cheng, Tamal K. Dey:
Maintaining deforming surface meshes. 112-121 - Arno Eigenwillig, Michael Kerber:
Exact and efficient 2D-arrangements of arbitrary algebraic curves. 122-131 - Nicla Bernasconi, Konstantinos Panagiotou, Angelika Steger:
On properties of random dissections and triangulations. 132-141 - Bonnie Berger, Rohit Singh, Jinbo Xu:
Graph algorithms for biological systems analysis. 142-151 - Julián Mestre:
Adaptive local ratio. 152-160 - Ulrich Faigle, Britta Peis:
Two-phase greedy algorithms for some classes of combinatorial linear programs. 161-166 - Ding-Zhu Du, Ronald L. Graham, Panos M. Pardalos, Peng-Jun Wan, Weili Wu, Wenbo Zhao:
Analysis of greedy approximations with nonsubmodular potential functions. 167-175 - Claire Mathieu, Warren Schudy:
Yet another algorithm for dense max cut: go greedy. 176-182 - Ignaz Rutter, Alexander Wolff:
Computing large matchings fast. 183-192 - Penny E. Haxell, Gordon T. Wilfong:
A fractional model of the border gateway protocol (BGP). 193-199 - Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan, Harald Räcke, Jaikumar Radhakrishnan:
Minimizing average latency in oblivious routing. 200-207 - Gianluca De Marco:
Distributed broadcast in unknown radio networks. 208-217 - Robert Elsässer, Thomas Sauerwald:
The power of memory in randomized broadcasting. 218-227 - Amos Fiat, Yishay Mansour, Uri Nadav:
Competitive queue management for latency sensitive packets. 228-237 - Elchanan Mossel, Allan Sly:
Rapid mixing of Gibbs sampling on graphs that are sparse on average. 238-247 - László Babai, Nikolay Nikolov, László Pyber:
Product growth and mixing in finite groups. 248-257 - Venkatesan Guruswami, Atri Rudra:
Concatenated codes can achieve list-decoding capacity. 258-267 - Mark Braverman, Elchanan Mossel:
Noisy sorting without resampling. 268-276 - Michael Zuckerman, Ariel D. Procaccia, Jeffrey S. Rosenschein:
Algorithms for the coalitional manipulation problem. 277-286 - Uriel Feige:
On allocations that maximize fairness. 287-293 - Susanne Albers:
On the value of coordination in network design. 294-303 - Matthew Cary, Abraham D. Flaxman, Jason D. Hartline, Anna R. Karlin:
Auctions for structured procurement. 304-313 - Baruch Awerbuch, Yossi Azar, Rohit Khandekar:
Fast load balancing via bounded best response. 314-322 - Yossi Azar, Kamal Jain, Vahab S. Mirrokni:
(Almost) optimal coordination mechanisms for unrelated machine scheduling. 323-332 - T.-H. Hubert Chan, Anupam Gupta, Kunal Talwar:
Ultra-low-dimensional embeddings for doubling metrics. 333-342 - Alexandr Andoni, Piotr Indyk, Robert Krauthgamer:
Earth mover distance over high-dimensional spaces. 343-352 - Venkatesan Guruswami, James R. Lee, Alexander A. Razborov:
Almost Euclidean subspaces of lN1 via expander codes. 353-362 - Ittai Abraham, Yair Bartal, Ofer Neiman:
Embedding metric spaces in their intrinsic dimension. 363-372 - Noga Alon, Michael R. Capalbo:
Optimal universal graphs with deterministic embedding. 373-378 - Ilan Gronau, Shlomo Moran, Sagi Snir:
Fast and reliable reconstruction of phylogenetic trees with very short edges. 379-388 - Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, Udi Wieder:
Trace reconstruction with constant deletion probability and related results. 389-398 - Krishnamurthy Viswanathan, Ram Swaminathan:
Improved string reconstruction over insertion-deletion channels. 399-408 - Ho-Lin Chen, Ashish Goel, Chris Luhrs:
Dimension augmentation and combinatorial criteria for efficient error-resistant DNA self-assembly. 409-418 - Ely Porat, Klim Efremenko:
Approximating general metric distances between a pattern and a text. 419-427 - Yuval Emek, David Peleg, Liam Roditty:
A near-linear time algorithm for computing replacement paths in planar directed graphs. 428-435 - Ran Duan, Seth Pettie:
Bounded-leg distance and reachability oracles. 436-445 - Ken-ichi Kawarabayashi, Bruce A. Reed:
A nearly linear time algorithm for the half integral disjoint paths packing. 446-454 - Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi:
Fast edge splitting and Edmonds' arborescence construction for unweighted graphs. 455-464 - Virginia Vassilevska:
Nondecreasing paths in a weighted graph or: how to optimally read a train schedule. 465-472 - Jessica Chang, Thomas Erlebach, Renars Gailis, Samir Khuller:
Broadcast scheduling: algorithms and complexity. 473-482 - Tomás Ebenlendr, Marek Krcál, Jirí Sgall:
Graph balancing: a special case of scheduling unrelated parallel machines. 483-490 - Julien Robert, Nicolas Schabanel:
Non-clairvoyant scheduling with precedence constraints. 491-500 - Guy E. Blelloch, Rezaul Alam Chowdhury, Phillip B. Gibbons, Vijaya Ramachandran, Shimin Chen, Michael Kozuch:
Provably good multicore cache performance for divide-and-conquer algorithms. 501-510 - Brighten Godfrey:
Balls and bins with structure: balanced allocations on hypergraphs. 511-517 - Naoyuki Kamiyama, Naoki Katoh, Atsushi Takizawa:
Arc-disjoint in-trees in directed graphs. 518-526 - Sergio Cabello, Matt DeVos, Jeff Erickson, Bojan Mohar:
Finding one tight cycle. 527-531 - Chandra Chekuri, Guy Even, Anupam Gupta, Danny Segev:
Set connectivity problems in undirected graphs and the directed Steiner network problem. 532-541 - Nicholas J. A. Harvey:
Matroid intersection, pointer chasing, and Young's seminormal representation of Sn. 542-549 - Harold N. Gabow, Suzanne Gallagher:
Iterated rounding algorithms for the smallest k-edge connected spanning subgraph. 550-559 - Persi Diaconis:
Shuffling cards, adding numbers, and symmetric functions. 560 - Timothy M. Chan:
On the bichromatic k-set problem. 561-570 - Jie Gao, Leonidas J. Guibas, Steve Oudot, Yue Wang:
Geodesic Delaunay triangulation and witness complex in the plane. 571-580 - Adrian Dumitrescu, Csaba D. Tóth:
Minimum weight convex Steiner partitions. 581-590 - Lee-Ad Gottlieb, Liam Roditty:
Improved algorithms for fully dynamic geometric spanners and geometric routing. 591-600 - Josep Díaz, Dieter Mitsche, Xavier Pérez-Giménez:
On the connectivity of dynamic random geometric graphs. 601-610 - Aravind Srinivasan:
Improved algorithmic versions of the Lovász Local Lemma. 611-620 - Frédéric Havet, Bruce A. Reed, Jean-Sébastien Sereni:
L(2, 1)-labelling of graphs. 621-630 - Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos:
Catalan structures and dynamic programming in H-minor-free graphs. 631-640 - Isolde Adler, Martin Grohe, Stephan Kreutzer:
Computing excluded minors. 641-650 - Reid Andersen, Kevin J. Lang:
An algorithm for improving graph partitions. 651-660 - Chandra Chekuri, Nitish Korula, Martin Pál:
Improved algorithms for orienteering and related problems. 661-670 - Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy:
Approximation algorithms for labeling hierarchical taxonomies. 671-680 - Mark Huber, Jenny Law:
Fast approximation of the permanent for very dense problems. 681-689 - T.-H. Hubert Chan, Anupam Gupta:
Approximating TSP on metrics with bounded global growth. 690-699 - Nir Halman, Diego Klabjan, Chung-Lun Li, James B. Orlin, David Simchi-Levi:
Fully polynomial time approximation schemes for stochastic dynamic programs. 700-709 - Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Clifford Stein, Zoya Svitkina:
On distributing symmetric streaming computations. 710-719 - Amit Chakrabarti, T. S. Jayram, Mihai Patrascu:
Tight lower bounds for selection in randomly ordered streams. 720-729 - Funda Ergün, Hossein Jowhari:
On distance to monotonicity and longest increasing subsequence of a data stream. 730-736 - Piotr Indyk, Andrew McGregor:
Declaring independence via the sketching of sketches. 737-745 - Michael Mitzenmacher, Salil P. Vadhan:
Why simple hash functions work: exploiting the entropy in a data stream. 746-755 - Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick:
Maximum overhang. 756-765 - Joshua N. Cooper, Benjamin Doerr, Tobias Friedrich, Joel Spencer:
Deterministic random walks on regular trees. 766-772 - Benjamin Doerr, Tobias Friedrich, Thomas Sauerwald:
Quasirandom rumor spreading. 773-781 - Domingos Dellamonica Jr., Yoshiharu Kohayakawa, Vojtech Rödl, Andrzej Rucinski:
Universality of random graphs. 782-788 - Asaf Shapira, Raphael Yuster:
The effect of induced subgraphs on quasi-randomness. 789-798 - Marcel R. Ackermann, Johannes Blömer, Christian Sohler
:
Clustering for metric and non-metric distance measures. 799-808 - Robert Krauthgamer, Tim Roughgarden:
Metric clustering via consistent labeling. 809-818 - Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, Kasturi R. Varadarajan:
On clustering to minimize the sum of radii. 819-825 - Ke Chen:
A constant factor approximation algorithm for k-median clustering with outliers. 826-835 - Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote:
Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension. 836-843 - Alex Fabrikant, Christos H. Papadimitriou:
The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond. 844-853 - Ho-Lin Chen, Tim Roughgarden, Gregory Valiant:
Designing networks with good equilibria. 854-863 - Sushil Bikhchandani, Sven de Vries, James Schummer, Rakesh V. Vohra:
Ascending auctions for integral (poly)matroids with concave nondecreasing separable values. 864-873 - Peter Bro Miltersen, Troels Bjerre Sørensen:
Fast algorithms for finding proper strategies in game trees. 874-883 - Ofer Dekel, Felix A. Fischer, Ariel D. Procaccia:
Incentive compatible regression learning. 884-893 - Guy E. Blelloch:
Space-efficient dynamic orthogonal point location, segment intersection, and range reporting. 894-903 - Timothy M. Chan, Eric Y. Chen:
In-place 2-d nearest neighbor search. 904-911 - Sébastien Collette, Vida Dujmovic, John Iacono, Stefan Langerman, Pat Morin:
Distribution-sensitive point location in convex subdivisions. 912-921 - Kenneth L. Clarkson:
Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm. 922-931 - Anirban Dasgupta, Petros Drineas
Sampling algorithms and coresets for ℓp regression. 932-941 - Naveen Garg, Anupam Gupta, Stefano Leonardi, Piotr Sankowski:
Stochastic analyses for online combinatorial optimization problems. 942-951 - Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev, Maxim Sviridenko:
Online make-to-order joint replenishment model: primal dual competitive algorithms. 952-961 - Michael E. Saks, C. Seshadhri:
Parallel monotonicity reconstruction. 962-971 - Ioannis Caragiannis:
Better bounds for online load balancing on unrelated machines. 972-981 - Gagan Goel, Aranyak Mehta:
Online budgeted matching in random input models with applications to Adwords. 982-991 - Andrei Z. Broder:
Computational advertising. 992 - Henry C. Lin, Christos Amanatidis, Martha Sideri, Richard M. Karp, Christos H. Papadimitriou:
Linked decompositions of networks and the power of choice in Polya urns. 993-1002 - Reid Andersen:
A local algorithm for finding dense subgraphs. 1003-1009 - Prasad Chebolu, Páll Melsted:
PageRank and the random surfer model. 1010-1018 - Arpita Ghosh, Mohammad Mahdian:
Charity auctions on social networks. 1019-1028 - Ning Chen:
On the approximability of influence in social networks. 1029-1037 - Bruce M. Kapron, David Kempe, Valerie King, Jared Saia, Vishal Sanwalani:
Fast asynchronous byzantine agreement and leader election with full information. 1038-1047 - Bhavani Shankar, Prasant Gopal, Kannan Srinathan, C. Pandu Rangan:
Unconditionally reliable message transmission in directed networks. 1048-1055 - Chinmoy Dutta, Yashodhan Kanoria, D. Manjunath, Jaikumar Radhakrishnan:
A tight lower bound for parity in noisy communication networks. 1056-1065 - James Aspnes, Muli Safra
Ranged hash functions and the price of churn. 1066-1075 - Graham Cormode, S. Muthukrishnan, Ke Yi:
Algorithms for distributed functional monitoring. 1076-1085 - Amihood Amir, Igor Nor:
Real-time indexing over fixed finite alphabets. 1086-1095 - Shay Mozes, Krzysztof Onak, Oren Weimann:
Finding an optimal tree searching strategy in linear time. 1096-1105 - Prosenjit Bose, Karim Douïeb, Stefan Langerman:
Dynamic optimality for skip lists and B-trees. 1106-1114 - Seth Pettie:
Splay trees, Davenport-Schinzel sequences, and the deque conjecture. 1115-1124 - Surender Baswana, Soumojit Sarkar:
Fully dynamic algorithm for graph spanners with poly-logarithmic update time. 1125-1134 - Mario Mense, Christian Scheideler:
SPREAD: an adaptive scheme for redundant and fair storage in dynamic heterogeneous storage systems. 1135-1144 - Ashish Goel, Hamid Nazerzadeh:
Price based protocols for fair resource allocation: convergence time analysis and extension to Leontief utilities. 1145-1153 - Zoya Svitkina:
Lower-bounded facility location. 1154-1163 - Barbara M. Anthony, Vineet Goyal, Anupam Gupta, Viswanath Nagarajan:
A plant location guide for the unsure. 1164-1173 - Friedrich Eisenbrand, Fabrizio Grandoni
Approximating connected facility location problems via random facility sampling and core detouring. 1174-1183 - Andrei Z. Broder, Adam Kirsch, Ravi Kumar, Michael Mitzenmacher, Eli Upfal, Sergei Vassilvitskii:
The hiring problem and Lake Wobegon strategies. 1184-1193 - Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky
Weak ε-nets and interval chains. 1194-1203 - Takuro Fukunaga, Magnús M. Halldórsson, Hiroshi Nagamochi:
Robust cost colorings. 1204-1212 - Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron:
Comparing the strength of query types in property testing: the case of testing k-colorability. 1213-1222 - Nayantara Bhatnagar, Sam Greenberg, Dana Randall:
Sampling stable marriages: why spouse-swapping won't work. 1223-1232 - Adrian Dumitrescu, Csaba D. Tóth:
On stars and Steiner stars. 1233-1240 - Boris Aronov, Mark de Berg, Chris Gray, Elena Mumford:
Cutting cycles of rods in space: hardness and approximation. 1241-1248 - Olivier Devillers, Jeff Erickson, Xavier Goaoc:
Empty-ellipse graphs. 1249-1257 - David Eppstein:
Recognizing partial cubes in quadratic time. 1258-1266 - Thomas Erlebach, Erik Jan van Leeuwen:
Approximating geometric coverage problems. 1267-1276
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-11-04 20:29 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: