Search results for "randomization"

Hits ?▲	Authors	Title	Venue	Year	Link
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