| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Kai-Min Chung, Salil P. Vadhan |
Tight Bounds for Hashing Block Sources.  |
APPROX-RANDOM  |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrej Bogdanov, Elchanan Mossel, Salil P. Vadhan |
The Complexity of Distinguishing Markov Random Fields. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Matei David, Toniann Pitassi, Emanuele Viola |
Improved Separations between Nondeterministic and Randomized Multiparty Communication. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuval Lando, Zeev Nutov |
Inapproximability of Survivable Networks. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Shashi Mittal, Andreas S. Schulz |
A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Ido Ben-Eliezer, Michael Krivelevich |
Small Sample Spaces Cannot Fool Low Degree Polynomials. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Eden Chlamtac, Gyanit Singh |
Improved Approximation Guarantees through Higher Levels of SDP Hierarchies. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Ariel Gabizon, Ronen Shaltiel |
Increasing the Output Length of Zero-Error Dispersers. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Hang Dinh, Alexander Russell |
Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Viswanath Nagarajan, R. Ravi 0001 |
The Directed Minimum Latency Problem. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Aravind Srinivasan |
Budgeted Allocations in the Full-Information Setting. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Jacek Cichon, Marek Klonowski, Lukasz Krzywiecki, Bartlomiej Rózanski, Pawel Zielinski 0001 |
Random Subsets of the Interval and P2P Protocols. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Manor Mendel, Assaf Naor |
Maximum Gradient Embeddings and Monotone Clustering. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith |
Sublinear Algorithms for Approximating String Compressibility. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Moni Naor, Asaf Nussboim |
Implementing Huge Sparse Random Graphs. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Dan Gutfreund, Amnon Ta-Shma |
Worst-Case to Average-Case Reductions Revisited. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Hamed Hatami, Avner Magen, Evangelos Markakis |
Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to l1 Embeddability of Negative Type Metrics. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Anupam Gupta 0001, MohammadTaghi Hajiaghayi, Amit Kumar 0001 |
Stochastic Steiner Tree with Non-uniform Inflation. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Andreas S. Schulz, Nelson A. Uhan |
Encouraging Cooperation in Sharing Supermodular Costs. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Arkadev Chattopadhyay, Bruce A. Reed |
Properly 2-Colouring Linear Hypergraphs. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Sourav Chakraborty 0001, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman |
Testing st -Connectivity. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilia Binder, Mark Braverman |
Derandomization of Euclidean Random Walks. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Shahar Dobzinski |
Two Randomized Mechanisms for Combinatorial Auctions. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Dana Glasner, Rocco A. Servedio |
Distribution-Free Testing Lower Bounds for Basic Boolean Functions. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Ravi Kumar 0001, Rina Panigrahy |
On Finding Frequent Elements in a Data Stream. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Kazuo Iwama, Guochuan Zhang |
Optimal Resource Augmentations for Online Knapsack. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
On-line algorithms, knapsack, resource augmentation |
| 1 | Kfir Barhum, Oded Goldreich 0001, Adi Shraibman |
On Approximating the Average Distance Between Points. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilias Diakonikolas, Mihalis Yannakakis |
Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Moses Charikar, Klaus Jansen, Omer Reingold, José D. P. Rolim (eds.) |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007, Proceedings |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Atri Rudra |
Better Binary List-Decodable Codes Via Multilevel Concatenation. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Jaroslaw Byrka |
An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Scott Diehl |
Lower Bounds for Swapping Arthur and Merlin. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Sam Greenberg, Dana Randall |
Slow Mixing of Markov Chains Using Fault Lines and Fat Contours. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Yael Dekel, James R. Lee, Nathan Linial |
Eigenvectors of Random Graphs: Nodal Domains. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Moshe Babaioff, Nicole Immorlica, David Kempe 0001, Robert Kleinberg |
A Knapsack Secretary Problem with Applications. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Sumit Ganguly, Graham Cormode |
On Estimating Frequency Moments of Data Streams. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Mira Gonen, Dana Ron |
On the Benefits of Adaptivity in Property Testing of Dense Graphs. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | James R. Lee, Prasad Raghavendra |
Coarse Differentiation and Multi-flows in Planar Graphs. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Ashkan Aazami, Michael D. Stilp |
Approximation Algorithms and Hardness for Domination with Propagation. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
Power Dominating Set, Approximation Algorithms, Integer Programming, Planar Graphs, Greedy Algorithms, Dominating Set, Hardness of Approximation, PTAS |
| 1 | Subhash Khot, Rishi Saket |
Hardness of Embedding Metric Spaces of Equal Size. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Colin Cooper, Alan M. Frieze |
The Cover Time of Random Digraphs. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Raphael Yuster |
Almost Exact Matchings. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich 0001, Or Sheffet |
On the Randomness Complexity of Property Testing. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Viswanath Nagarajan, R. Ravi 0001 |
Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Eldar Fischer, Eyal Rozenberg |
Lower bounds for testing forbidden induced substructures in bipartite-graph-like combinatorial objects. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Matthias Christandl, Michal Koucký 0001, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin |
High Entropy Random Selection Protocols. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Mohit Singh |
Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Subhash Khot, Ashok Kumar Ponnuswami |
Approximation Algorithms for the Max-Min Allocation Problem. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Chadi Kari, Yoo Ah Kim, Seungjoon Lee, Alexander Russell, Minho Shin |
Soft Edge Coloring. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Behrisch 0002, Amin Coja-Oghlan, Mihyun Kang |
Local Limit Theorems for the Giant Component of Random Hypergraphs. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Mohsen Bayati, Jeong Han Kim, Amin Saberi |
A Sequential Algorithm for Generating Random Graphs. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Ning Chen 0005, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra, Gyanit Singh |
Improved Approximation Algorithms for the Spanning Star Forest Problem. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Victor Chepoi, Bertrand Estellon |
Packing and Covering delta -Hyperbolic Spaces by Balls. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
approximation algorithm, metric space, packing, covering, ball |
| 1 | Omer Barkol, Yuval Ishai, Enav Weinreb |
On Locally Decodable Codes, Self-correctable Codes, and t -Private PIR. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Greg N. Frederickson, Barry Wittman |
Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems with Unit-Time Windows. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
On the Approximation Resistance of a Random Predicate. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
On Nontrivial Approximation of CSPs. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Nicholas C. Wormald |
Analysis of Algorithms on the Cores of Random Graphs. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Dan Gutfreund |
Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Benny Applebaum, Yuval Ishai, Eyal Kushilevitz |
On Pseudorandom Generators with Linear Stretch in NC0. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
|
| 1 | Yair Bartal, Stefano Leonardi 0001, Gil Shallom, René Sitters |
On the Value of Preemption in Scheduling. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
|
| 1 | Viswanath Nagarajan, R. Ravi 0001 |
Minimum Vehicle Routing with a Common Deadline. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Sashka Davis, Jeff Edmonds, Russell Impagliazzo |
Online Algorithms to Minimize Resource Reallocations and Network Communication. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Deshpande 0001, Santosh S. Vempala |
Adaptive Sampling and Fast Low-Rank Matrix Approximation. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Inge Li Gørtz |
Hardness of Preemptive Finite Capacity Dial-a-Ride. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson |
Approximating Precedence-Constrained Single Machine Scheduling by Coloring. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Sharon Marko, Dana Ron |
Distance Approximation in Bounded-Degree and General Sparse Graphs. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Lachish, Ilan Newman, Asaf Shapira |
Space Complexity vs. Query Complexity. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Jean Cardinal, Samuel Fiorini, Gwenaël Joret |
Tight Results on Minimum Entropy Set Cover. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
|
| 1 | Shlomo Hoory, Avner Magen, Toniann Pitassi |
Monotone Circuits for the Majority Function. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Yi-Kai Liu 0001, Vadim Lyubashevsky, Daniele Micciancio |
On Bounded Distance Decoding for General Lattices. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Thomas Strohmer, Roman Vershynin |
A Randomized Solver for Linear Systems with Exponential Convergence. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Elchanan Mossel, Dan Vilenchik |
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Rajeev Motwani 0001, Rina Panigrahy, Ying Xu 0002 |
Fractional Matching Via Balls-and-Bins. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Yi-Kai Liu 0001 |
Consistency of Local Density Matrices Is QMA-Complete. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeev Nutov |
Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Langberg, Yuval Rabani, Chaitanya Swamy |
Approximation Algorithms for Graph Homomorphism Problems. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Samir Khuller, Yoo Ah Kim, Azarakhsh Malekian |
Improved Algorithms for Data Migration. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
|
| 1 | David P. Woodruff |
Better Approximations for the Minimum Common Integer Partition Problem. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
|
| 1 | Nikhil Bansal 0001, Don Coppersmith, Baruch Schieber |
Minimizing Setup and Beam-On Times in Radiation Therapy. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
|
| 1 | Oded Goldreich 0001, Dana Ron |
Approximating Average Parameters of Graphs. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Retsef Levi, Maxim Sviridenko |
Improved Approximation Algorithm for the One-Warehouse Multi-Retailer Problem. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Sanjeev Arora, Elad Hazan, Satyen Kale |
A Fast Random Sampling Algorithm for Sparsifying Matrices. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Philipp Woelfel |
Maintaining External Memory Efficient Hash Tables. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Elena Grigorescu, Swastik Kopparty, Madhu Sudan 0001 |
Local Decoding and Testing for Homomorphisms. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Josep Díaz, Klaus Jansen, José D. P. Rolim, Uri Zwick (eds.) |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Nayantara Bhatnagar, Sam Greenberg, Dana Randall |
The Effect of Boundary Conditions on Mixing Rates of Markov Chains. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
|
| 1 | Irit Dinur, Madhu Sudan 0001, Avi Wigderson |
Robust Local Testability of Tensor Products of LDPC Codes. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin Marciniszyn, Jozef Skokan, Reto Spöhel, Angelika Steger |
Threshold Functions for Asymmetric Ramsey Properties Involving Cliques. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Murali K. Ganapathy |
Robust Mixing. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander Healy |
Randomness-Efficient Sampling Within NC1. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Rajiv Gandhi, Julián Mestre |
Combinatorial Algorithms for Data Migration to Minimize Average Completion Time. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Shuchi Chawla 0001, Tim Roughgarden |
Single-Source Stochastic Routing. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license