default search action
14th RANDOM / 13th APPROX 2010: Barcelona, Spain
- Maria J. Serna
, Ronen Shaltiel, Klaus Jansen, José D. P. Rolim:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings. Lecture Notes in Computer Science 6302, Springer 2010, ISBN 978-3-642-15368-6
Contributed Talks of APPROX
- Hyung-Chan An, Robert D. Kleinberg, David B. Shmoys:
Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem. 1-11 - Per Austrin:
Improved Inapproximability for Submodular Maximization. 12-24 - MohammadHossein Bateni, Julia Chuzhoy:
Approximation Algorithms for the Directed k-Tour and k-Stroll Problems. 25-38 - MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Morteza Zadimoghaddam:
Submodular Secretary Problem and Extensions. 39-52 - Piotr Berman, Sofya Raskhodnikova:
Approximation Algorithms for Min-Max Generalization Problems. 53-66 - Gruia Calinescu
Min-Power Strong Connectivity. 67-80 - Prasad Chebolu, Leslie Ann Goldberg, Russell A. Martin:
The Complexity of Approximately Counting Stable Matchings. 81-94 - Victor Chepoi
Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs. 95-109 - Mahdi Cheraghchi
Approximating Linear Threshold Predicates. 110-123 - Eden Chlamtac, Robert Krauthgamer
Approximating Sparsest Cut in Graphs of Bounded Treewidth. 124-137 - Irit Dinur
On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors. 138-151 - Matthias Englert, Anupam Gupta, Robert Krauthgamer
Vertex Sparsifiers: New Results from Old Techniques. 152-165 - Thomas Erlebach
PTAS for Weighted Set Cover on Unit Squares. 166-177 - Igor Gorodezky, Robert D. Kleinberg, David B. Shmoys, Gwen Spencer:
Improved Lower Bounds for the Universal and a priori TSP. 178-191 - Lee-Ad Gottlieb
Proximity Algorithms for Nearly-Doubling Spaces. 192-204 - Lee-Ad Gottlieb
Matrix Sparsification and the Sparse Null Space Problem. 205-218 - MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Julián Mestre:
The Checkpoint Problem. 219-231 - Ishay Haviv, Oded Regev:
The Euclidean Distortion of Flat Tori. 232-245 - Piotr Indyk, Avner Magen, Anastasios Sidiropoulos, Anastasios Zouzias:
Online Embeddings. 246-259 - Frank Kammer, Torsten Tholey, Heiko Voepel:
Approximation Algorithms for Intersection Graphs. 260-273 - Ken-ichi Kawarabayashi, Yusuke Kobayashi:
An O(logn)-Approximation Algorithm for the Disjoint Paths Problem in Eulerian Planar Graphs and 4-Edge-Connected Planar Graphs. 274-286 - Ken-ichi Kawarabayashi, Yusuke Kobayashi:
Improved Algorithm for the Half-Disjoint Paths Problem. 287-297 - Subhash Khot, Preyas Popat, Rishi Saket:
Approximate Lasserre Integrality Gap for Unique Games. 298-311 - Spyros C. Kontogiannis
Exploiting Concavity in Bimatrix Games: New Polynomially Tractable Subclasses. 312-325 - Guyslain Naves
Maximum Flows on Disjoint Paths. 326-337 - Evdokia Nikolova:
Approximation Algorithms for Reliable Stochastic Combinatorial Optimization. 338-351 - Kirk Pruhs, Clifford Stein:
How to Schedule When You Have to Buy Your Energy. 352-365 - Mohit Singh, Kunal Talwar:
Improving Integrality Gaps via Chvátal-Gomory Rounding. 366-379
Contributed Talks of RANDOM
- Eric Allender, Vikraman Arvind, Fengming Wang:
Uniform Derandomization from Pathetic Lower Bounds. 380-393 - Noga Alon, Eric Blais:
Testing Boolean Function Isomorphism. 394-405 - Rasmus Resen Amossen, Andrea Campagna, Rasmus Pagh:
Better Size Estimation for Sparse Matrix Products. 406-419 - Eli Ben-Sasson, Michael Viderman:
Low Rate Is Insufficient for Local Testability. 420-433 - Nayantara Bhatnagar, Allan Sly, Prasad Tetali:
Reconstruction Threshold for the Hardcore Model. 434-447 - Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners. 448-461 - Jop Briët, Sourav Chakraborty, David García-Soriano
Monotonicity Testing and Shortest-Path Routing on the Cube. 462-475 - Joshua Brody, Amit Chakrabarti
Better Gap-Hamming Lower Bounds via Better Round Elimination. 476-489 - Amin Coja-Oghlan, Mikael Onsjö, Osamu Watanabe:
Propagation Connectivity of Random Hypergraphs. 490-503 - Anindya De, Omid Etesami, Luca Trevisan
Improved Pseudorandom Generators for Depth 2 Circuits. 504-517 - Irit Dinur
The Structure of Winning Strategies in Parallel Repetition Games. 518-530 - Elya Dolev, Dana Ron
Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries. 531-544 - Funda Ergün, Hossein Jowhari, Mert Saglam:
Periodicity in Streams. 545-559 - Nikolaos Fountoulakis
Rumor Spreading on Random Regular Graphs and Expanders. 560-573 - Oded Goldreich
On Testing Computability by Small Width OBDDs. 574-587 - Parikshit Gopalan, Rocco A. Servedio:
Learning and Lower Bounds for AC0 with Threshold Gates. 588-601 - Thomas P. Hayes, Alistair Sinclair:
Liftings of Tree-Structured Markov Chains - (Extended Abstract). 602-616 - Russell Impagliazzo
Constructive Proofs of Concentration Bounds. 617-631 - Piotr Indyk, Stanislaw J. Szarek
Almost-Euclidean Subspaces of l1N\ell_1^N via Tensor Products: A Simple Approach to Randomness Reduction. 632-641 - Yuichi Yoshida, Hiro Ito:
Testing Outerplanarity of Bounded Degree Graphs. 642-655 - Roy Kasher, Julia Kempe
Two-Source Extractors Secure against Quantum Adversaries. 656-669 - Tali Kaufman, Michael Viderman:
Locally Testable vs. Locally Decodable Codes. 670-682 - Aaron Roth
Differential Privacy and the Fat-Shattering Dimension of Linear Queries. 683-695 - Atri Rudra, Steve Uurtamo:
Two Theorems on List Decoding - (Extended Abstract). 696-709 - Alistair Sinclair, Dan Vilenchik:
Delaying Satisfiability for Random 2SAT. 710-723 - David Steurer:
Improved Rounding for Parallel Repeated Unique Games. 724-737 - Suguru Tamaki, Yuichi Yoshida:
A Query Efficient Non-adaptive Long Code Test with Perfect Completeness. 738-751 - Thomas Watson:
Relativized Worlds without Worst-Case to Average-Case Reductions for NP. 752-765 - David P. Woodruff:
A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field. 766-779
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-17 20:46 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: