Search results for "randomization"

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