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
  
• Richard Cole, Ramesh Hariharan:
  Faster Suffix Tree Construction with Missing Suffix Links. 26-42
  
• Juraj Hromkovic, Georg Schnitger:
  Nondeterministic Communication with a Limited Number of Advice Bits. 43-68
  
• Siu-Wing Cheng, Tamal K. Dey:
  Quality Meshing with Weighted Delaunay Refinement. 69-93
  
• 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
  
• László Babai, Anna Gál, Peter G. Kimmel, Satyanarayana V. Lokam:
  Communication Complexity of Simultaneous Messages. 137-166
  

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

Volume 33, Number 3, 2004

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

Volume 33, Number 4, 2004

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

Volume 33, Number 5, 2004

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

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
  
• Uwe Schwiegelshohn:
  Preemptive Weighted Completion Time Scheduling of Parallel Jobs. 1280-1308
  
• Lane A. Hemaspaandra, Harald Hempel, Arfst Nickelsen:
  Algebraic Properties for Selector Functions. 1309-1337
  
• Uriel Feige, Michael Langberg, Gideon Schechtman:
  Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers. 1338-1368
  
• Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang:
  Disjoint NP-Pairs. 1369-1416
  
• Moses Charikar, Chandra Chekuri, Tomás Feder, Rajeev Motwani:
  Incremental Clustering and Dynamic Information Retrieval. 1417-1440
  
• Tali Kaufman, Michael Krivelevich, Dana Ron:
  Tight Bounds for Testing Bipartiteness in General Graphs. 1441-1483
  
• Marek Piotrów:
  Depth Optimal Sorting Networks Resistant to k Passive Faults. 1484-1512
  
• Pierre McKenzie, Heribert Vollmer, Klaus W. Wagner:
  Arithmetic Circuits and Polynomial Replacement Systems. 1513-1531