Search results for "APPROX-RANDOM"

Hits ?▲	Authors	Title	Venue	Year	Link
1	Chandra Chekuri, Martin Pál	An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
1	Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum	Dobrushin Conditions and Systematic Scan.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
1	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
1	Joseph Cheriyan, Mohammad R. Salavatipour	Packing Element-Disjoint Steiner Trees.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	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
1	Venkatesan Guruswami, Luca Trevisan	The Complexity of Making Unique Choices: Approximating 1-in- k SAT.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Jens Maßberg, Jens Vygen	Approximation Algorithms for Network Design and Facility Location with Service Capacities.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Sourav Chakraborty 0001, Jaikumar Radhakrishnan, Nandakumar Raghunathan	Bounds for Error Reduction with Few Quantum Queries.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Rémi Monasson	A Generating Function Method for the Average-Case Analysis of DPLL.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma	On the Error Parameter of Dispersers.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Uriel Feige, Eran Ofek	Finding a Maximum Independent Set in a Sparse Random Graph.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Christopher Umans	Reconstructive Dispersers and Hitting Set Generators.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Dekel Tsur	Tight Bounds for String Reconstruction Using Substring Queries.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Alexander Hall, Christos H. Papadimitriou	Approximating the Distortion.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Shlomo Moran, Sagi Snir	Efficient Approximation of Convex Recolorings.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Julián Mestre	A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami, Atri Rudra	Tolerant Locally Testable Codes.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Moses Charikar, Chandra Chekuri, Martin Pál	Sampling Bounds for Stochastic Optimization.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Viswanath Nagarajan, R. Ravi 0001	Approximation Algorithms for Requirement Cut on Graphs.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Raphael Yuster	Fractional Decompositions of Dense Hypergraphs.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Paul Valiant	The Tensor Product of Two Codes Is Not Necessarily Robustly Testable.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Stanislav Angelov, Sanjeev Khanna, Keshav Kunal	The Network as a Storage Device: Dynamic Routing with Bounded Buffers.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Victor Chepoi, Karim Nouioua, Yann Vaxès	A Rounding Algorithm for Approximating Minimum Manhattan Networks.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Boulos Harb, Sampath Kannan, Andrew McGregor 0001	Approximating the Best-Fit Tree Under Lp Norms.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Eyal Kaplan, Moni Naor, Omer Reingold	Derandomized Constructions of k-Wise (Almost) Independent Permutations.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Anupam Gupta 0001, Amit Kumar 0001	Where's the Winner? Max-Finding and Sorting with Metric Costs.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	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
1	Jeffrey C. Jackson, Rocco A. Servedio	On Learning Random DNF Formulas Under the Uniform Distribution.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Andrew McGregor 0001	Finding Graph Matchings in Data Streams.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Eyal Rozenman, Salil P. Vadhan	Derandomized Squaring of Graphs.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Uriel Feige, Kunal Talwar	Approximating the Bandwidth of Caterpillars.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	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
1	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
1	Gustav Hast	Beating a Random Assignment.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Shirley Halevy, Eyal Kushilevitz	A Lower Bound for Distribution-Free Monotonicity Testing.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	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
1	Dana Randall, Peter Winkler 0001	Mixing Points on a Circle.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	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
1	Zeev Dvir, Amir Shpilka	An Improved Analysis of Mergers.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Adi Avidor, Uri Zwick	Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Jan Remy, Angelika Steger	Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami, Salil P. Vadhan	A Lower Bound on List Size for List Decoding.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Iannis Tourlakis	Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Martin Marciniszyn, Reto Spöhel, Angelika Steger	The Online Clique Avoidance Game on Random Graphs.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	Oded Lachish, Ilan Newman	Testing Periodicity.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	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
1	Amin Coja-Oghlan, Andreas Goerdt, André Lanka	Strong Refutation Heuristics for Random k-SAT.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Moshe Babaioff, Liad Blumrosen	Computationally-Feasible Truthful Auctions for Convex Bundles.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Yevgeniy Dodis, Ariel Elbaz, Roberto Oliveira 0001, Ran Raz	Improved Randomness Extraction from Two Independent Sources.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Vittorio Bilò, Vineet Goyal, R. Ravi 0001, Mohit Singh	On the Crossing Spanning Tree Problem.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	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
1	Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar 0001	The Sketching Complexity of Pattern Matching.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Abraham Flaxman, Alan M. Frieze	The Diameter of Randomly Perturbed Digraphs and Some Applications..	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Anupam Gupta 0001, Aravind Srinivasan, Éva Tardos	Cost-Sharing Mechanisms for Network Design.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Shirley Halevy, Eyal Kushilevitz	Distribution-Free Connectivity Testing.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	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
1	Amin Coja-Oghlan, Cristopher Moore, Vishal Sanwalani	Counting Connected Graphs and Hypergraphs via the Probabilistic Method.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Zoya Svitkina, Éva Tardos	Min-Max Multiway Cut.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Eli Ben-Sasson, Madhu Sudan 0001	Robust Locally Testable Codes and Products of Codes.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Nir Ailon, Bernard Chazelle, Seshadhri Comandur, Ding Liu	Estimating the Distance to a Monotone Function.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	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
1	Noga Alon, Vera Asodi	Edge Coloring with Delays.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Dan Gutfreund, Emanuele Viola	Fooling Parity Tests with Parity Gates.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Dimitris Achlioptas, Cristopher Moore	The Chromatic Number of Random Regular Graphs.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Kedar Dhamdhere	Approximating Additive Distortion of Embeddings into Line Metrics.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Vahab S. Mirrokni, Adrian Vetta	Convergence Issues in Competitive Games.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Dariusz R. Kowalski, Andrzej Pelc	Centralized Deterministic Broadcasting in Undirected Multi-hop Radio Networks.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Marek Chrobak, Petr Kolman, Jirí Sgall	The Greedy Algorithm for the Minimum Common String Partition Problem.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Samir Khuller, Yoo Ah Kim, Gerhard J. Woeginger	Approximation Schemes for Broadcasting in Heterogenous Networks.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Gustav Hast	Approximating Max kCSP Using Random Restrictions.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	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
1	Markus Bläser	A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Andrej Bogdanov, Hoeteck Wee	A Stateful Implementation of a Random Function Supporting Parity Queries over Hypercubes.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Michael Elkin, Guy Kortsarz	Polylogarithmic Inapproximability of the Radio Broadcast Problem.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Uriel Feige, Daniel Reichman 0001	On Systems of Linear Equations with Two Variables per Equation.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Chandra Chekuri, Amit Kumar 0001	Maximum Coverage Problem with Group Budget Constraints and Applications.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Alantha Newman	Cuts and Orderings: On Semidefinite Relaxations for the Linear Ordering Problem.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Michael Langberg	Testing the Independence Number of Hypergraphs.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Andris Ambainis, Adam D. Smith	Small Pseudo-random Families of Matrices: Derandomizing Approximate Quantum Encryption.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Sumit Ganguly	Estimating Frequency Moments of Data Streams Using Random Linear Combinations.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Konstantin Andreev, Charles Garrod, Bruce M. Maggs, Adam Meyerson	Simultaneous Source Location.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Mansoor Alicherry, Randeep Bhatia, Yung-Chun (Justin) Wan	Designing Networks with Existing Traffic to Support Fast Restoration.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Luca Trevisan	A Note on Approximate Counting for k-DNF.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF

Publications at "APPROX-RANDOM"( http://dblp.L3S.de/Venues/APPROX-RANDOM )