7. RANDOM / 6. APPROX 2003: Princeton University, NY, USA

Contributed Talks of APPROX

• Erik D. Demaine, Nicole Immorlica:
  Correlation Clustering with Partial Information. 1-13
  
• Doratha E. Drake, Stefan Hougardy:
  Improved Linear Time Approximation Algorithms for Weighted Matchings. 14-23
  
• Guy Even, Naveen Garg, Jochen Könemann, R. Ravi, Amitabh Sinha:
  Covering Graphs Using Trees and Stars. 24-35
  
• Jittat Fakcharoenphol, Kunal Talwar:
  An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor. 36-46
  
• Rajiv Gandhi, Samir Khuller, Aravind Srinivasan, Nan Wang:
  Approximation Algorithms for Channel Allocation Problems in Broadcast Networks. 47-58
  
• Inge Li Gørtz, Anthony Wirth:
  Asymmetry in k-Center Variants. 59-70
  
• Alexander Hall, Katharina Langkau, Martin Skutella:
  An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times. 71-82
  
• Elad Hazan, Shmuel Safra, Oded Schwartz:
  On the Complexity of Approximating k-Dimensional Matching. 83-97
  
• Kamal Jain, Mohammad Mahdian, Amin Saberi:
  Approximating Market Equilibria. 98-108
  
• Jochen Könemann, Asaf Levin, Amitabh Sinha:
  Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem. 109-121
  
• Ioannis Koutis:
  On the Hardness of Approximate Multivariate Integration. 122-128
  
• Mohammad Mahdian, Yingyu Ye, Jiawei Zhang:
  A 2-Approximation Algorithm for the Soft-Capacitated Facility Location Problem. 129-140
  
• Zeev Nutov:
  Approximating Rooted Connectivity Augmentation Problems. 141-152
  
• Jay Sethuraman, Chung-Piaw Teo:
  Effective Routing and Scheduling in Adversarial Queueing Networks. 153-164
  
• Hadas Shachnai, Tami Tamir:
  Approximation Schemes for Generalized 2-Dimensional Vector Packing with Application to Data Placement. 165-177
  
• Yingyu Ye, Jiawei Zhang:
  An Improved Algorithm for Approximating the Radii of Point Sets. 178-187
  

Contributed Talks of RANDOM

• Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron:
  Testing Low-Degree Polynomials over GF(2(. 188-199
  
• Boaz Barak, Ronen Shaltiel, Avi Wigderson:
  Computational Analogues of Entropy. 200-215
  
• Eli Ben-Sasson, Oded Goldreich, Madhu Sudan:
  Bounds on 2-Query Codeword Testing. 216-227
  
• Amin Coja-Oghlan:
  The Lovász Number of Random Graphs. 228-239
  
• Artur Czumaj, Chris Riley, Christian Scheideler:
  Perfectly Balanced Allocation. 240-251
  
• Yevgeniy Dodis, Roberto Oliveira:
  On Extracting Private Randomness over a Public Channel. 252-263
  
• Abraham Flaxman, Alan M. Frieze, Trevor I. Fenner:
  High Degree Vertices and Eigenvalues in the Preferential Attachment Graph. 264-274
  
• Alan M. Frieze, Michael Molloy:
  The Satisfiability Threshold for Randomly Generated Binary Constraint Satisfaction Problems. 275-289
  
• Heath Gerhardt, John Watrous:
  Continuous-Time Quantum Walks on the Symmetric Group. 290-301
  
• Shirley Halevy, Eyal Kushilevitz:
  Distribution-Free Property Testing. 302-317
  
• Volker Kaibel, Anja Remshagen:
  On the Graph-Density of Random 0/1-Polytopes. 318-328
  
• Richard M. Karp, Claire Kenyon:
  A Gambling Game Arising in the Analysis of Adaptive Randomized Rounding. 329-340
  
• Tali Kaufman, Michael Krivelevich, Dana Ron:
  Tight Bounds for Testing Bipartiteness in General Graphs. 341-353
  
• Julia Kempe:
  Discrete Quantum Walks Hit Exponentially Faster. 354-369
  
• Sofya Raskhodnikova:
  Approximate Testing of Visual Properties. 370-381
  
• Alex D. Scott, Gregory B. Sorkin:
  Faster Algorithms for MAX CUT and MAX CSP, with Polynomial Expected Time for Sparse Instances. 382-395
  
• Jun Tarui, Toshiya Itoh, Yoshinori Takei:
  A Nearly Linear Size 4-Min-Wise Independent Permutation Family by Finite Geometries. 396-408
  

Last update Thu May 23 17:51:56 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page