Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
27 | Nir Ailon, Bernard Chazelle, Seshadhri Comandur, Ding Liu |
Estimating the Distance to a Monotone Function. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Michael Ben-Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld |
Non-Abelian Homomorphism Testing, and Distributions Close to Their Self-convolutions. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Noga Alon, Vera Asodi |
Edge Coloring with Delays. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Dan Gutfreund, Emanuele Viola |
Fooling Parity Tests with Parity Gates. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Dimitris Achlioptas, Cristopher Moore |
The Chromatic Number of Random Regular Graphs. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Kedar Dhamdhere |
Approximating Additive Distortion of Embeddings into Line Metrics. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Vahab S. Mirrokni, Adrian Vetta |
Convergence Issues in Competitive Games. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Dariusz R. Kowalski, Andrzej Pelc |
Centralized Deterministic Broadcasting in Undirected Multi-hop Radio Networks. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Marek Chrobak, Petr Kolman, Jirí Sgall |
The Greedy Algorithm for the Minimum Common String Partition Problem. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Samir Khuller, Yoo Ah Kim, Gerhard J. Woeginger |
Approximation Schemes for Broadcasting in Heterogenous Networks. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Gustav Hast |
Approximating Max kCSP Using Random Restrictions. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | David Gamarnik, Tomasz Nowicki, Grzegorz Swirszcz |
Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results Using the Local Weak Convergence Method. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Markus Bläser |
A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Andrej Bogdanov, Hoeteck Wee |
A Stateful Implementation of a Random Function Supporting Parity Queries over Hypercubes. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Michael Elkin, Guy Kortsarz |
Polylogarithmic Inapproximability of the Radio Broadcast Problem. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Uriel Feige, Daniel Reichman 0001 |
On Systems of Linear Equations with Two Variables per Equation. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Chandra Chekuri, Amit Kumar 0001 |
Maximum Coverage Problem with Group Budget Constraints and Applications. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Alantha Newman |
Cuts and Orderings: On Semidefinite Relaxations for the Linear Ordering Problem. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Michael Langberg |
Testing the Independence Number of Hypergraphs. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Sumit Ganguly |
Estimating Frequency Moments of Data Streams Using Random Linear Combinations. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Konstantin Andreev, Charles Garrod, Bruce M. Maggs, Adam Meyerson |
Simultaneous Source Location. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Mansoor Alicherry, Randeep Bhatia, Yung-Chun (Justin) Wan |
Designing Networks with Existing Traffic to Support Fast Restoration. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Luca Trevisan |
A Note on Approximate Counting for k-DNF. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Sanjeev Arora, Klaus Jansen, José D. P. Rolim, Amit Sahai (eds.) |
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 |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Kamal Jain, Mohammad Mahdian, Amin Saberi |
Approximating Market Equilibria. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Tali Kaufman, Michael Krivelevich, Dana Ron |
Tight Bounds for Testing Bipartiteness in General Graphs. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Hadas Shachnai, Tami Tamir |
Approximation Schemes for Generalized 2-Dimensional Vector Packing with Application to Data Placement. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Alex D. Scott, Gregory B. Sorkin |
Faster Algorithms for MAX CUT and MAX CSP, with Polynomial Expected Time for Sparse Instances. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Jittat Fakcharoenphol, Kunal Talwar |
An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Shirley Halevy, Eyal Kushilevitz |
Distribution-Free Property Testing. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Elad Hazan, Shmuel Safra, Oded Schwartz |
On the Complexity of Approximating k-Dimensional Matching. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Alan M. Frieze, Michael Molloy 0001 |
The Satisfiability Threshold for Randomly Generated Binary Constraint Satisfaction Problems. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Boaz Barak, Ronen Shaltiel, Avi Wigderson |
Computational Analogues of Entropy. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Volker Kaibel, Anja Remshagen |
On the Graph-Density of Random 0/1-Polytopes. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Heath Gerhardt, John Watrous |
Continuous-Time Quantum Walks on the Symmetric Group. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Artur Czumaj, Chris Riley, Christian Scheideler |
Perfectly Balanced Allocation. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Yevgeniy Dodis, Roberto Oliveira 0001 |
On Extracting Private Randomness over a Public Channel. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Alexander Hall, Katharina Langkau, Martin Skutella |
An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Eli Ben-Sasson, Oded Goldreich 0001, Madhu Sudan 0001 |
Bounds on 2-Query Codeword Testing. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron |
Testing Low-Degree Polynomials over GF(2(. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Rajiv Gandhi, Samir Khuller, Aravind Srinivasan, Nan Wang 0001 |
Approximation Algorithms for Channel Allocation Problems in Broadcast Networks. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Jay Sethuraman, Chung-Piaw Teo |
Effective Routing and Scheduling in Adversarial Queueing Networks. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Mohammad Mahdian, Yingyu Ye, Jiawei Zhang 0006 |
A 2-Approximation Algorithm for the Soft-Capacitated Facility Location Problem. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Sofya Raskhodnikova |
Approximate Testing of Visual Properties. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Amin Coja-Oghlan |
The Lovász Number of Random Graphs. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Doratha E. Drake, Stefan Hougardy |
Improved Linear Time Approximation Algorithms for Weighted Matchings. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Guy Even, Naveen Garg 0001, Jochen Könemann, R. Ravi 0001, Amitabh Sinha |
Covering Graphs Using Trees and Stars. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Erik D. Demaine, Nicole Immorlica |
Correlation Clustering with Partial Information. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Inge Li Gørtz, Anthony Wirth |
Asymmetry in k-Center Variants. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Zeev Nutov |
Approximating Rooted Connectivity Augmentation Problems. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Jun Tarui, Toshiya Itoh, Yoshinori Takei |
A Nearly Linear Size 4-Min-Wise Independent Permutation Family by Finite Geometries. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Yingyu Ye, Jiawei Zhang |
An Improved Algorithm for Approximating the Radii of Point Sets. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Ioannis Koutis |
On the Hardness of Approximate Multivariate Integration. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Jochen Könemann, Asaf Levin, Amitabh Sinha |
Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Richard M. Karp, Claire Kenyon |
A Gambling Game Arising in the Analysis of Adaptive Randomized Rounding. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Julia Kempe |
Discrete Quantum Walks Hit Exponentially Faster. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Abraham Flaxman, Alan M. Frieze, Trevor I. Fenner |
High Degree Vertices and Eigenvalues in the Preferential Attachment Graph. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
27 | Michel X. Goemans, Klaus Jansen, José D. P. Rolim, Luca Trevisan (eds.) |
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 |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Sriram V. Pemmaraju |
Equitable Coloring Extends Chernoff-Hoeffding Bounds. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Estela Maris Rodrigues, Marie-France Sagot, Yoshiko Wakabayashi |
Some Approximation Results for the Maximum Agreement Forest Problem. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai |
Minimizing Average Completion of Dedicated Tasks and Interval Graphs. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov |
A 3/2-Approximation Algorithm for Augmenting the Edge-Connectivity of a Graph from 1 to 2 Using a Subset of a Given Edge Set. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Susanne Albers, Carsten Witt |
Minimizing Stall Time in Single and Parallel Disk Systems Using Multicommodity Network Flows. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Kazuyuki Amano, John Tromp, Paul M. B. Vitányi, Osamu Watanabe 0001 |
On a Generalized Ruin Problem. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Michal Parnas, Dana Ron, Ronitt Rubinfeld |
Testing Parenthesis Languages. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Sung-woo Cho, Ashish Goel |
Exact Sampling in Machine Scheduling Problems. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Michel X. Goemans |
Using Complex Semidefinite Programming for Approximating MAX E2-LIN3. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Luca Becchetti, Stefano Leonardi 0001, Alberto Marchetti-Spaccamela, Kirk Pruhs |
Online Weighted Flow Time and Deadline Scheduling. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Anna R. Karlin |
Web Search via Hub Synthesis. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Reuven Bar-Yehuda, Dror Rawitz |
On the Equivalence between the Primal-Dual Schema and the Local-Ratio Technique. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | John Dunagan, Santosh S. Vempala |
On Euclidean Embeddings and Bandwidth Minimization. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Luca Trevisan |
Error-Correcting Codes and Pseudorandom Projections. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Andreas Baltz, Tomasz Schoen, Anand Srivastav |
On the b-Partite Random Asymmetric Traveling Salesman Problem and Its Assignment Relaxation. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
Asymmetric b-partite TSP, Assignment Problem |
27 | Russell Impagliazzo |
Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Alantha Newman |
The Maximum Acyclic Subgraph Problem and Degree-3 Graphs. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Yevgeniy Dodis, Shai Halevi |
Incremental Codes. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Alberto Caprara, Hans Kellerer, Ulrich Pferschy |
Approximation Schemes for Ordered Vector Packing Problems. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Lars Engebretsen |
The Non-approximability of Non-Boolean Predicates. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Don Coppersmith |
L Infinity Embeddings. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Piotr Berman, Junichiro Fukuyama |
An Online Algorithm for the Postman Problem with a Small Penalty. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Mohammad Mahdian, Evangelos Markakis, Amin Saberi, Vijay V. Vazirani |
A Greedy Facility Location Algorithm Analyzed Using Dual Fitting. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Adam R. Klivans |
On the Derandomization of Constant Depth Circuits. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Adriana Felicia Bumb, Walter Kern |
A Simple Dual Ascent Algorithm for the Multilevel Facility Location Problem. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Michal Parnas, Dana Ron, Alex Samorodnitsky |
Proclaiming Dictators and Juntas or Testing Boolean Formulae. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Andrea E. F. Clementi, Pierluigi Crescenzi, Angelo Monti, Paolo Penna, Riccardo Silvestri |
On Computing Ad-hoc Selective Families. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Noga Alon, Michael R. Capalbo, Yoshiharu Kohayakawa, Vojtech Rödl, Andrzej Rucinski 0001, Endre Szemerédi |
Near-optimum Universal Graphs for Graphs with Bounded Degrees. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Salil P. Vadhan |
Order in Pseudorandomness. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Shiro Matuura, Tomomi Matsui |
63-Approximation Algorithm for MAX DICUT. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Rahul Garg 0001, Vijay Kumar, Vinayaka Pandit |
Approximation Algorithms for Budget-Constrained Auctions. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
approximation algorithm, auctions, rounding, winner determination |
27 | Dorit S. Hochbaum, Klaus Jansen, José D. P. Rolim, Alistair Sinclair (eds.) |
Randomization, Approximation, and Combinatorial Algorithms and Techniques, Third International Workshop on Randomization and Approximation Techniques in Computer Science, and Second International Workshop on Approximation Algorithms for Combinatorial Optimization Problems RANDOM-APPROX'99, Berkeley, CA, USA, August 8-11, 1999, Proceedings |
RANDOM-APPROX |
1999 |
DBLP DOI BibTeX RDF |
|
27 | Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan |
Approximating Minimum Manhattan Networks. |
RANDOM-APPROX |
1999 |
DBLP DOI BibTeX RDF |
|
27 | Dimitris Fotakis 0001, Paul G. Spirakis |
Efficient Redundant Assignments under Fault-Tolerance Constraints. |
RANDOM-APPROX |
1999 |
DBLP DOI BibTeX RDF |
|
27 | Klaus Jansen, Roberto Solis-Oba, Maxim Sviridenko |
A Linear Time Approximation Scheme for the Job Shop Scheduling Problem. |
RANDOM-APPROX |
1999 |
DBLP DOI BibTeX RDF |
|
27 | Michael E. Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman |
Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families. |
RANDOM-APPROX |
1999 |
DBLP DOI BibTeX RDF |
|
27 | Tugkan Batu, Ronitt Rubinfeld, Patrick White |
Fast Approximate PCPs for Multidimensional Bin-Packing Problems. |
RANDOM-APPROX |
1999 |
DBLP DOI BibTeX RDF |
|
27 | Csanád Imreh, John Noga |
Scheduling with Machine Cost. |
RANDOM-APPROX |
1999 |
DBLP DOI BibTeX RDF |
|
27 | Foto N. Afrati, Evripidis Bampis, Claire Kenyon, Ioannis Milis |
Scheduling on a Constant Number of Machines. |
RANDOM-APPROX |
1999 |
DBLP DOI BibTeX RDF |
|
27 | Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri |
Hardness Results for the Power Range Assignmet Problem in Packet Radio Networks. |
RANDOM-APPROX |
1999 |
DBLP DOI BibTeX RDF |
|
27 | Magnús M. Halldórsson, Guy Kortsarz |
Multicoloring Planar Graphs and Partial k-Trees. |
RANDOM-APPROX |
1999 |
DBLP DOI BibTeX RDF |
|
27 | Andrei Z. Broder, Michael Mitzenmacher |
Completeness and Robustness Properties of Min-Wise Independent Permutations. |
RANDOM-APPROX |
1999 |
DBLP DOI BibTeX RDF |
|