SIAM Journal on Computing, Volume 33

Volume 33, Number 1, 2003

Fabián A. Chudak, David B. Shmoys:
Improved Approximation Algorithms for the Uncapacitated Facility Location Problem. 1-25
Electronic Edition (link) BibTeX
Richard Cole, Ramesh Hariharan:
Faster Suffix Tree Construction with Missing Suffix Links. 26-42
Electronic Edition (link) BibTeX
Juraj Hromkovic, Georg Schnitger:
Nondeterministic Communication with a Limited Number of Advice Bits. 43-68
Electronic Edition (link) BibTeX
Siu-Wing Cheng, Tamal K. Dey:
Quality Meshing with Weighted Delaunay Refinement. 69-93
Electronic Edition (link) BibTeX
Guy Even, Zvi Lotker, Dana Ron, Shakhar Smorodinsky:
Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks. 94-136
Electronic Edition (link) BibTeX
László Babai, Anna Gál, Peter G. Kimmel, Satyanarayana V. Lokam:
Communication Complexity of Simultaneous Messages. 137-166
Electronic Edition (link) BibTeX

Volume 33, Number 2, 2004

Refael Hassin, Asaf Levin:
An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection. 261-268
Electronic Edition (link) BibTeX
Sariel Har-Peled, Yusu Wang:
Shape Fitting with Outliers. 269-285
Electronic Edition (link) BibTeX
Zvi Lotker, Boaz Patt-Shamir, Adi Rosén:
New stability results for adversarial queuing. 286-303
Electronic Edition (link) BibTeX
Iiro S. Honkala, Tero Laihonen:
On identifying codes in the triangular and square grids. 304-312
Electronic Edition (link) BibTeX
Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson:
A bound on the capacity of backoff and acknowledgment-based protocols. 313-331
Electronic Edition (link) BibTeX
Tim Roughgarden:
Stackelberg Scheduling Strategies. 332-350
Electronic Edition (link) BibTeX
Georg Gottlob, Reinhard Pichler:
Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width. 351-378
Electronic Edition (link) BibTeX
William Y. C. Chen, Xueliang Li, Chao Wang, Xiaoyan Zhang:
The Minimum All-Ones Problem for Trees. 379-392
Electronic Edition (link) BibTeX
Rolf H. Möhring, Martin Skutella, Frederik Stork:
Scheduling with AND/OR Precedence Constraints. 393-415
Electronic Edition (link) BibTeX
Leslie Ann Goldberg, Steven Kelk, Mike Paterson:
The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random. 416-432
Electronic Edition (link) BibTeX
Kazuyuki Amano, Akira Maruoka:
The Potential of the Approximation Method. 433-447
Electronic Edition (link) BibTeX
Samir Khuller, Yoo Ah Kim, Yung-Chun (Justin) Wan:
Algorithms for Data Migration with Cloning. 448-461
Electronic Edition (link) BibTeX
Christian Icking, Rolf Klein, Elmar Langetepe, Sven Schuierer, Ines Semrau:
An Optimal Competitive Strategy for Walking in Streets. 462-486
Electronic Edition (link) BibTeX
Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov:
Learning a Hidden Matching. 487-501
Electronic Edition (link) BibTeX
Victor Y. Pan, Xinmao Wang:
On Rational Number Reconstruction and Approximation. 502-503
Electronic Edition (link) BibTeX

Volume 33, Number 3, 2004

Alan Siegel:
On Universal Classes of Extremely Random Constant-Time Hash Functions. 505-543
Electronic Edition (link) BibTeX
Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit:
Local Search Heuristics for k-Median and Facility Location Problems. 544-562
Electronic Edition (link) BibTeX
Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir, Baruch Schieber, Maxim Sviridenko:
Buffer Overflow Management in QoS Switches. 563-583
Electronic Edition (link) BibTeX
Xiao Chen, Jian Shen:
On the Frame--Stewart Conjecture about the Towers of Hanoi. 584-589
Electronic Edition (link) BibTeX
Itsik Pe'er, Tal Pupko, Ron Shamir, Roded Sharan:
Incomplete Directed Perfect Phylogeny. 590-607
Electronic Edition (link) BibTeX
Michael Elkin, David Peleg:
(1+epsilon, beta)-Spanner Constructions for General Graphs. 608-631
Electronic Edition (link) BibTeX
Adam L. Buchsbaum, Howard J. Karloff, Claire Kenyon, Nick Reingold, Mikkel Thorup:
OPT Versus LOAD in Dynamic Storage Allocation. 632-646
Electronic Edition (link) BibTeX
Luc Devroye, Ralph Neininger:
Distances and Finger Search in Random Binary Search Trees. 647-658
Electronic Edition (link) BibTeX
Matthew Andrews, Lisa Zhang:
The Effects of Temporary Sessions on Network Performance. 659-673
Electronic Edition (link) BibTeX
Joseph Y. Halpern, Ron van der Meyden, Moshe Y. Vardi:
Complete Axiomatizations for Reasoning about Knowledge and Time. 674-703
Electronic Edition (link) BibTeX
Guy Kortsarz, Robert Krauthgamer, James R. Lee:
Hardness of Approximation for Vertex-Connectivity Network Design Problems. 704-720
Electronic Edition (link) BibTeX
Michael Molloy:
The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree. 721-737
Electronic Edition (link) BibTeX
Oded Regev:
Quantum Computation and Lattice Problems. 738-760
Electronic Edition (link) BibTeX

Volume 33, Number 4, 2004

Narayan Vikas:
Compaction, Retraction, and Constraint Satisfaction. 761-782
Electronic Edition (link) BibTeX
Boaz Barak, Yehuda Lindell:
Strict Polynomial-Time in Simulation and Extraction. 738-818
Electronic Edition (link) BibTeX
Jesús A. De Loera, Shmuel Onn:
The Complexity of Three-Way Statistical Tables. 819-836
Electronic Edition (link) BibTeX
Chandra Chekuri, Sanjeev Khanna:
On Multidimensional Packing Problems. 837-851
Electronic Edition (link) BibTeX
N. V. Vinodchandran:
Counting Complexity of Solvable Black-Box Group Problems. 852-869
Electronic Edition (link) BibTeX
Dariusz R. Kowalski, Andrzej Pelc:
Time of Deterministic Broadcasting in Radio Networks with Local Knowledge. 870-891
Electronic Edition (link) BibTeX
Jörg Flum, Martin Grohe:
The Parameterized Complexity of Counting Problems. 892-922
Electronic Edition (link) BibTeX
Luc Devroye, Pat Morin, Alfredo Viola:
On Worst-Case Robin Hood Hashing. 923-936
Electronic Edition (link) BibTeX
Prosenjit Bose, Pat Morin:
Online Routing in Triangulations. 937-951
Electronic Edition (link) BibTeX
Werner Schachinger:
Distributional Results for Costs of Partial Match Queries in Asymmetric K-Dimensional Tries. 952-983
Electronic Edition (link) BibTeX
Jin-yi Cai, Osamu Watanabe:
On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy. 984-1009
Electronic Edition (link) BibTeX

Volume 33, Number 5, 2004

Amotz Bar-Noy, Richard E. Ladner:
Efficient Algorithms for Optimal Stream Merging for Media-on-Demand. 1011-1034
Electronic Edition (link) BibTeX
György Dósa, Yong He:
Better Online Algorithms for Scheduling with Machine Cost. 1035-1051
Electronic Edition (link) BibTeX
Joachim Biskup, Jan Paredaens, Thomas Schwentick, Jan Van den Bussche:
Solving Equations in the Relational Algebra. 1052-1066
Electronic Edition (link) BibTeX
Rocco A. Servedio, Steven J. Gortler:
Equivalences and Separations Between Quantum and Classical Learnability. 1067-1092
Electronic Edition (link) BibTeX
Jacobo Torán:
On the Hardness of Graph Isomorphism. 1093-1108
Electronic Edition (link) BibTeX
André van Tonder:
A Lambda Calculus for Quantum Computation. 1109-1135
Electronic Edition (link) BibTeX
Guantao Chen, Jun Xu, Xingxing Yu:
Circumference of Graphs with Bounded Degree. 1136-1170
Electronic Edition (link) BibTeX
Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo:
A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution. 1171-1200
Electronic Edition (link) BibTeX
James B. Orlin, Abraham P. Punnen, Andreas S. Schulz:
Approximate Local Search in Combinatorial Optimization. 1201-1214
Electronic Edition (link) BibTeX
John Havlicek:
A Note on the Homotopy Type of Wait-Free Atomic Snapshot Protocol Complexes. 1215-1222
Electronic Edition (link) BibTeX
Paul W. Purdom, Dirk Van Gucht, Dennis P. Groth:
Average-Case Performance of the Apriori Algorithm. 1223-1260
Electronic Edition (link) BibTeX

Volume 33, Number 6, 2004

Yair Bartal, John W. Byers, Danny Raz:
Fast, Distributed Approximation Algorithms for Positive Linear Programming with Applications to Flow Control. 1261-1279
Electronic Edition (link) BibTeX
Uwe Schwiegelshohn:
Preemptive Weighted Completion Time Scheduling of Parallel Jobs. 1280-1308
Electronic Edition (link) BibTeX
Lane A. Hemaspaandra, Harald Hempel, Arfst Nickelsen:
Algebraic Properties for Selector Functions. 1309-1337
Electronic Edition (link) BibTeX
Uriel Feige, Michael Langberg, Gideon Schechtman:
Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers. 1338-1368
Electronic Edition (link) BibTeX
Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang:
Disjoint NP-Pairs. 1369-1416
Electronic Edition (link) BibTeX
Moses Charikar, Chandra Chekuri, Tomás Feder, Rajeev Motwani:
Incremental Clustering and Dynamic Information Retrieval. 1417-1440
Electronic Edition (link) BibTeX
Tali Kaufman, Michael Krivelevich, Dana Ron:
Tight Bounds for Testing Bipartiteness in General Graphs. 1441-1483
Electronic Edition (link) BibTeX
Marek Piotrów:
Depth Optimal Sorting Networks Resistant to k Passive Faults. 1484-1512
Electronic Edition (link) BibTeX
Pierre McKenzie, Heribert Vollmer, Klaus W. Wagner:
Arithmetic Circuits and Polynomial Replacement Systems. 1513-1531
Electronic Edition (link) BibTeX