Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
27 | Dan Gutfreund |
Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Benny Applebaum, Yuval Ishai, Eyal Kushilevitz |
On Pseudorandom Generators with Linear Stretch in NC0. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Christoph Ambühl, Thomas Erlebach, Matús Mihalák, Marc Nunkesser |
Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Yair Bartal, Stefano Leonardi 0001, Gil Shallom, René Sitters |
On the Value of Preemption in Scheduling. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Leah Epstein, Magnús M. Halldórsson, Asaf Levin, Hadas Shachnai |
Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Viswanath Nagarajan, R. Ravi 0001 |
Minimum Vehicle Routing with a Common Deadline. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Sashka Davis, Jeff Edmonds, Russell Impagliazzo |
Online Algorithms to Minimize Resource Reallocations and Network Communication. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Amit Deshpande 0001, Santosh S. Vempala |
Adaptive Sampling and Fast Low-Rank Matrix Approximation. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Inge Li Gørtz |
Hardness of Preemptive Finite Capacity Dial-a-Ride. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson |
Approximating Precedence-Constrained Single Machine Scheduling by Coloring. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Sharon Marko, Dana Ron |
Distance Approximation in Bounded-Degree and General Sparse Graphs. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Oded Lachish, Ilan Newman, Asaf Shapira |
Space Complexity vs. Query Complexity. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Jean Cardinal, Samuel Fiorini, Gwenaël Joret |
Tight Results on Minimum Entropy Set Cover. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | T.-H. Hubert Chan, Donglin Xia, Goran Konjevod, Andréa W. Richa |
A Tight Lower Bound for the Steiner Point Removal Problem on Trees. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Shlomo Hoory, Avner Magen, Toniann Pitassi |
Monotone Circuits for the Majority Function. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Yi-Kai Liu 0001, Vadim Lyubashevsky, Daniele Micciancio |
On Bounded Distance Decoding for General Lattices. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Thomas Strohmer, Roman Vershynin |
A Randomized Solver for Linear Systems with Exponential Convergence. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Uriel Feige, Elchanan Mossel, Dan Vilenchik |
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Rajeev Motwani 0001, Rina Panigrahy, Ying Xu 0002 |
Fractional Matching Via Balls-and-Bins. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Yi-Kai Liu 0001 |
Consistency of Local Density Matrices Is QMA-Complete. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Zeev Nutov |
Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Michael Langberg, Yuval Rabani, Chaitanya Swamy |
Approximation Algorithms for Graph Homomorphism Problems. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Samir Khuller, Yoo Ah Kim, Azarakhsh Malekian |
Improved Algorithms for Data Migration. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Alexander Grigoriev, Maxim Sviridenko, Marc Uetz |
LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | David P. Woodruff |
Better Approximations for the Minimum Common Integer Partition Problem. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Benjamin E. Birnbaum, Kenneth J. Goldman |
An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Nikhil Bansal 0001, Don Coppersmith, Baruch Schieber |
Minimizing Setup and Beam-On Times in Radiation Therapy. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Petros Drineas, Michael W. Mahoney, S. Muthukrishnan 0001 |
Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Oded Goldreich 0001, Dana Ron |
Approximating Average Parameters of Graphs. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Retsef Levi, Maxim Sviridenko |
Improved Approximation Algorithm for the One-Warehouse Multi-Retailer Problem. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Sanjeev Arora, Elad Hazan, Satyen Kale |
A Fast Random Sampling Algorithm for Sparsifying Matrices. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Philipp Woelfel |
Maintaining External Memory Efficient Hash Tables. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Elena Grigorescu, Swastik Kopparty, Madhu Sudan 0001 |
Local Decoding and Testing for Homomorphisms. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Nayantara Bhatnagar, Sam Greenberg, Dana Randall |
The Effect of Boundary Conditions on Mixing Rates of Markov Chains. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Anthony Man-Cho So, Jiawei Zhang 0006, Yinyu Ye 0001 |
Stochastic Combinatorial Optimization with Controllable Risk Aversion Level. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Irit Dinur, Madhu Sudan 0001, Avi Wigderson |
Robust Local Testability of Tensor Products of LDPC Codes. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Martin Marciniszyn, Jozef Skokan, Reto Spöhel, Angelika Steger |
Threshold Functions for Asymmetric Ramsey Properties Involving Cliques. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Murali K. Ganapathy |
Robust Mixing. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Alexander Healy |
Randomness-Efficient Sampling Within NC1. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Rajiv Gandhi, Julián Mestre |
Combinatorial Algorithms for Data Migration to Minimize Average Completion Time. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Shuchi Chawla 0001, Tim Roughgarden |
Single-Source Stochastic Routing. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Chandra Chekuri, Martin Pál |
An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum |
Dobrushin Conditions and Systematic Scan. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour |
Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
27 | Chandra Chekuri, Klaus Jansen, José D. P. Rolim, Luca Trevisan (eds.) |
Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Joseph Cheriyan, Mohammad R. Salavatipour |
Packing Element-Disjoint Steiner Trees. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Venkatesan Guruswami, Luca Trevisan |
The Complexity of Making Unique Choices: Approximating 1-in- k SAT. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Jens Maßberg, Jens Vygen |
Approximation Algorithms for Network Design and Facility Location with Service Capacities. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Sourav Chakraborty 0001, Jaikumar Radhakrishnan, Nandakumar Raghunathan |
Bounds for Error Reduction with Few Quantum Queries. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Rémi Monasson |
A Generating Function Method for the Average-Case Analysis of DPLL. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma |
On the Error Parameter of Dispersers. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Uriel Feige, Eran Ofek |
Finding a Maximum Independent Set in a Sparse Random Graph. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Christopher Umans |
Reconstructive Dispersers and Hitting Set Generators. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Dekel Tsur |
Tight Bounds for String Reconstruction Using Substring Queries. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Alexander Hall, Christos H. Papadimitriou |
Approximating the Distortion. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Shlomo Moran, Sagi Snir |
Efficient Approximation of Convex Recolorings. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Julián Mestre |
A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Venkatesan Guruswami, Atri Rudra |
Tolerant Locally Testable Codes. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Moses Charikar, Chandra Chekuri, Martin Pál |
Sampling Bounds for Stochastic Optimization. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Viswanath Nagarajan, R. Ravi 0001 |
Approximation Algorithms for Requirement Cut on Graphs. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Raphael Yuster |
Fractional Decompositions of Dense Hypergraphs. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Paul Valiant |
The Tensor Product of Two Codes Is Not Necessarily Robustly Testable. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Stanislav Angelov, Sanjeev Khanna, Keshav Kunal |
The Network as a Storage Device: Dynamic Routing with Bounded Buffers. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Victor Chepoi, Karim Nouioua, Yann Vaxès |
A Rounding Algorithm for Approximating Minimum Manhattan Networks. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Boulos Harb, Sampath Kannan, Andrew McGregor 0001 |
Approximating the Best-Fit Tree Under Lp Norms. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Eyal Kaplan, Moni Naor, Omer Reingold |
Derandomized Constructions of k-Wise (Almost) Independent Permutations. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Anupam Gupta 0001, Amit Kumar 0001 |
Where's the Winner? Max-Finding and Sorting with Metric Costs. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Kamalika Chaudhuri, Satish Rao, Samantha J. Riesenfeld, Kunal Talwar |
What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Jeffrey C. Jackson, Rocco A. Servedio |
On Learning Random DNF Formulas Under the Uniform Distribution. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Andrew McGregor 0001 |
Finding Graph Matchings in Data Streams. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Eyal Rozenman, Salil P. Vadhan |
Derandomized Squaring of Graphs. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Uriel Feige, Kunal Talwar |
Approximating the Bandwidth of Caterpillars. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Vadim Lyubashevsky |
The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | V. S. Anil Kumar 0001, Madhav V. Marathe, Srinivasan Parthasarathy 0002, Aravind Srinivasan |
Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Gustav Hast |
Beating a Random Assignment. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Shirley Halevy, Eyal Kushilevitz |
A Lower Bound for Distribution-Free Monotonicity Testing. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Cristopher Moore, Gabriel Istrate, Demetrios D. Demopoulos, Moshe Y. Vardi |
A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Dana Randall, Peter Winkler 0001 |
Mixing Points on a Circle. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Anupam Gupta 0001, Martin Pál, R. Ravi 0001, Amitabh Sinha |
What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Zeev Dvir, Amir Shpilka |
An Improved Analysis of Mergers. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Adi Avidor, Uri Zwick |
Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Jan Remy, Angelika Steger |
Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Venkatesan Guruswami, Salil P. Vadhan |
A Lower Bound on List Size for List Decoding. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Iannis Tourlakis |
Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Martin Marciniszyn, Reto Spöhel, Angelika Steger |
The Online Clique Avoidance Game on Random Graphs. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Oded Lachish, Ilan Newman |
Testing Periodicity. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
27 | Klaus Jansen, Sanjeev Khanna, José D. P. Rolim, Dana Ron (eds.) |
Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques, 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, and 8th International Workshop on Randomization and Computation, RANDOM 2004, Cambridge, MA, USA, August 22-24, 2004, Proceedings |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Amin Coja-Oghlan, Andreas Goerdt, André Lanka |
Strong Refutation Heuristics for Random k-SAT. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Moshe Babaioff, Liad Blumrosen |
Computationally-Feasible Truthful Auctions for Convex Bundles. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Yevgeniy Dodis, Ariel Elbaz, Roberto Oliveira 0001, Ran Raz |
Improved Randomness Extraction from Two Independent Sources. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Vittorio Bilò, Vineet Goyal, R. Ravi 0001, Mohit Singh |
On the Crossing Spanning Tree Problem. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Piotr Berman, Bhaskar DasGupta, Eduardo D. Sontag |
Randomized Approximation Algorithms for Set Multicover Problems with Applications to Reverse Engineering of Protein and Gene Networks. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar 0001 |
The Sketching Complexity of Pattern Matching. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Abraham Flaxman, Alan M. Frieze |
The Diameter of Randomly Perturbed Digraphs and Some Applications.. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Anupam Gupta 0001, Aravind Srinivasan, Éva Tardos |
Cost-Sharing Mechanisms for Network Design. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Shirley Halevy, Eyal Kushilevitz |
Distribution-Free Connectivity Testing. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Rahul Garg 0001, Sanjiv Kapoor, Vijay V. Vazirani |
An Auction-Based Market Equilibrium Algorithm for the Separable Gross Substitutability Case. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Amin Coja-Oghlan, Cristopher Moore, Vishal Sanwalani |
Counting Connected Graphs and Hypergraphs via the Probabilistic Method. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Zoya Svitkina, Éva Tardos |
Min-Max Multiway Cut. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
27 | Eli Ben-Sasson, Madhu Sudan 0001 |
Robust Locally Testable Codes and Products of Codes. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|