RANDOM-APPROX

Keyphrases

Publications

2003

Abraham Flaxman, Alan M. Frieze, Trevor I. Fenner
High Degree Vertices and Eigenvalues in the Preferential Attachment Graph. RANDOM-APPROX (2003)
Hadas Shachnai, Tami Tamir
Approximation Schemes for Generalized 2-Dimensional Vector Packing with Application to Data Placement. RANDOM-APPROX (2003)
Mohammad Mahdian, Yingyu Ye, Jiawei Zhang
A 2-Approximation Algorithm for the Soft-Capacitated Facility Location Problem. RANDOM-APPROX (2003)
Inge Li Gørtz, Anthony Wirth
Asymmetry in k-Center Variants. RANDOM-APPROX (2003)
Erik D. Demaine, Nicole Immorlica
Correlation Clustering with Partial Information. RANDOM-APPROX (2003)
Alex D. Scott, Gregory B. Sorkin
Faster Algorithms for MAX CUT and MAX CSP, with Polynomial Expected Time for Sparse Instances. RANDOM-APPROX (2003)
Jay Sethuraman, Chung-Piaw Teo
Effective Routing and Scheduling in Adversarial Queueing Networks. RANDOM-APPROX (2003)
Yingyu Ye, Jiawei Zhang
An Improved Algorithm for Approximating the Radii of Point Sets. RANDOM-APPROX (2003)
Ioannis Koutis
On the Hardness of Approximate Multivariate Integration. RANDOM-APPROX (2003)
Heath Gerhardt, John Watrous
Continuous-Time Quantum Walks on the Symmetric Group. RANDOM-APPROX (2003)
Eli Ben-Sasson, Oded Goldreich, Madhu Sudan
Bounds on 2-Query Codeword Testing. RANDOM-APPROX (2003)
Boaz Barak, Ronen Shaltiel, Avi Wigderson
Computational Analogues of Entropy. RANDOM-APPROX (2003)
Alan M. Frieze, Michael Molloy
The Satisfiability Threshold for Randomly Generated Binary Constraint Satisfaction Problems. RANDOM-APPROX (2003)
Guy Even, Naveen Garg, Jochen Könemann, R. Ravi, Amitabh Sinha
Covering Graphs Using Trees and Stars. RANDOM-APPROX (2003)
Rajiv Gandhi, Samir Khuller, Aravind Srinivasan, Nan Wang
Approximation Algorithms for Channel Allocation Problems in Broadcast Networks. RANDOM-APPROX (2003)
Sofya Raskhodnikova
Approximate Testing of Visual Properties. RANDOM-APPROX (2003)
Volker Kaibel, Anja Remshagen
On the Graph-Density of Random 0/1-Polytopes. RANDOM-APPROX (2003)
Yevgeniy Dodis, Roberto Oliveira
On Extracting Private Randomness over a Public Channel. RANDOM-APPROX (2003)
Amin Coja-Oghlan
The Lovász Number of Random Graphs. RANDOM-APPROX (2003)
Jochen Könemann, Asaf Levin, Amitabh Sinha
Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem. RANDOM-APPROX (2003)
Jittat Fakcharoenphol, Kunal Talwar
An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor. RANDOM-APPROX (2003)
Richard M. Karp, Claire Kenyon
A Gambling Game Arising in the Analysis of Adaptive Randomized Rounding. RANDOM-APPROX (2003)
Artur Czumaj, Chris Riley, Christian Scheideler
Perfectly Balanced Allocation. RANDOM-APPROX (2003)
Zeev Nutov
Approximating Rooted Connectivity Augmentation Problems. RANDOM-APPROX (2003)
Alexander Hall, Katharina Langkau, Martin Skutella
An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times. RANDOM-APPROX (2003)
Kamal Jain, Mohammad Mahdian, Amin Saberi
Approximating Market Equilibria. RANDOM-APPROX (2003)
Shirley Halevy, Eyal Kushilevitz
Distribution-Free Property Testing. RANDOM-APPROX (2003)
Elad Hazan, Shmuel Safra, Oded Schwartz
On the Complexity of Approximating k-Dimensional Matching. RANDOM-APPROX (2003)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
Testing Low-Degree Polynomials over GF(2(. RANDOM-APPROX (2003)
Julia Kempe
Discrete Quantum Walks Hit Exponentially Faster. RANDOM-APPROX (2003)
Jun Tarui, Toshiya Itoh, Yoshinori Takei
A Nearly Linear Size 4-Min-Wise Independent Permutation Family by Finite Geometries. RANDOM-APPROX (2003)
Doratha E. Drake, Stefan Hougardy
Improved Linear Time Approximation Algorithms for Weighted Matchings. RANDOM-APPROX (2003)
Tali Kaufman, Michael Krivelevich, Dana Ron
Tight Bounds for Testing Bipartiteness in General Graphs. RANDOM-APPROX (2003)

volume 2764, 2003

Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, Princeton, NJ, USA, August 24-26, 2003, Proceedings RANDOM-APPROX 2764 (2003)

2001

volume 2129, 2001

Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 Berkeley, CA, USA, August 18-20, 2001, Proceedings RANDOM-APPROX 2129 (2001)