default search action
15th RANDOM / 14th APPROX 2011: Princeton, NJ, USA
- Leslie Ann Goldberg, Klaus Jansen, R. Ravi, José D. P. Rolim:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings. Lecture Notes in Computer Science 6845, Springer 2011, ISBN 978-3-642-22934-3
Contributed Talks of APPROX
- Sanjeev Arora, Rong Ge:
New Tools for Graph Coloring. 1-12 - Per Austrin, Mark Braverman, Eden Chlamtac:
Inapproximability of NP-Complete Variants of Nash Equilibrium. 13-25 - Khanh Do Ba, Piotr Indyk:
Sparse Recovery with Partial Support Knowledge. 26-37 - Nikhil Bansal, Ravishankar Krishnaswamy, Barna Saha:
On Capacitated Set Cover Problems. 38-49 - Yair Bartal, Douglas E. Carroll, Adam Meyerson, Ofer Neiman:
Bandwidth and Low Dimensional Embedding. 50-61 - Piotr Berman, Erik D. Demaine, Morteza Zadimoghaddam:
O(1)-Approximations for Maximum Movement Problems. 62-74 - Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna:
Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs. 75-86 - Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna:
Social Welfare in One-Sided Matching Markets without Money. 87-98 - Tim Carnes, David B. Shmoys:
Primal-Dual Schema and Lagrangian Relaxation for the k-Location-Routing Problem. 99-110 - Venkatesan T. Chakaravarthy, Amit Kumar
, Vinayaka Pandit, Sambuddha Roy, Yogish Sabharwal:
Scheduling Resources for Throughput Maximization. 111-122 - Parinya Chalermsook:
Coloring and Maximum Independent Set of Rectangles. 123-134 - Maurice Cheung, David B. Shmoys:
A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems. 135-146 - Nachshon Cohen, Zeev Nutov:
A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius. 147-157 - Michael S. Crouch
Periodicity and Cyclic Shifts via Linear Sketches. 158-170 - Feodor F. Dragan, Ekkehard Köhler:
An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs. 171-183 - Chandan K. Dubey, Thomas Holenstein:
Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle. 184-193 - Adrian Dumitrescu, Minghui Jiang, János Pach:
Opaque Sets. 194-205 - Sándor P. Fekete, Tom Kamphans, Alexander Kröller, Joseph S. B. Mitchell, Christiane Schmidt:
Exploring and Triangulating a Region by a Swarm of Robots. 206-217 - Moran Feldman
Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract). 218-229 - Inge Li Gørtz
Locating Depots for Capacitated Vehicle Routing. 230-241 - Johan Håstad
Satisfying Degree-d Equations over GF[2] n. 242-253 - Zhiyi Huang
Black-Box Reductions in Mechanism Design. 254-265 - Michael Kapralov, Rina Panigrahy:
Multiplicative Approximations of Random Walk Transition Probabilities. 266-276 - Marek Karpinski, Warren Schudy:
Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems. 277-288 - Rohit Khandekar, Guy Kortsarz, Zeev Nutov:
Network-Design with Degree Constraints. 289-301 - M. Reza Khani, Mohammad R. Salavatipour:
Improved Approximation Algorithms for the Min-Max Tree Cover and Bounded Tree Cover Problems. 302-314 - Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh S. Vempala:
Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions. 315-326 - Sushant Sachdeva
Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs. 327-338 - Sagi Snir, Raphael Yuster:
A Linear Time Approximation Scheme for Maximum Quartet Consistency on Sparse Sampled Inputs. 339-350
Contributed Talks of RANDOM
- Mohammed Amin Abdullah, Colin Cooper, Moez Draief:
Viral Processes by Random Walks on Random Regular Graphs. 351-364 - Andris Ambainis, Andrew M. Childs
Quantum Property Testing for Bounded-Degree Graphs. 365-376 - Sergei Artemenko, Ronen Shaltiel:
Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification. 377-388 - Lidor Avigad, Oded Goldreich
Testing Graph Blow-Up. 389-399 - Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka
On Sums of Locally Testable Affine Invariant Properties. 400-411 - Eli Ben-Sasson, Madhu Sudan:
Limits on the Rate of Locally Testable Affine-Invariant Codes. 412-423 - Nayantara Bhatnagar, Andrej Bogdanov, Elchanan Mossel
The Computational Complexity of Estimating MCMC Convergence Time. 424-435 - Joshua Brody, David P. Woodruff:
Streaming Algorithms with One-Sided Estimation. 436-447 - Amit Chakrabarti
Everywhere-Tight Information Cost Tradeoffs for Augmented Index. 448-459 - Dana Dachman-Soled, Rocco A. Servedio
A Canonical Form for Testing Boolean Function Properties. 460-471 - Varsha Dani
Independent Sets in Random Graphs from the Weighted Second Moment Method. 472-482 - Anindya De, Thomas Watson:
Extractors and Lower Bounds for Locally Samplable Sources. 483-494 - Domingos Dellamonica Jr., Subrahmanyam Kalyanasundaram
A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma. 495-506 - Irit Dinur
Dense Locally Testable Codes Cannot Have Constant Rate and Distance. 507-518 - Andrew Drucker:
Efficient Probabilistically Checkable Debates. 519-529 - Alan Edelman, Avinatan Hassidim, Huy N. Nguyen, Krzysztof Onak:
An Efficient Partitioning Oracle for Bounded-Treewidth Graphs. 530-541 - Eldar Fischer, Eyal Rozenberg:
Inflatable Graph Properties and Natural Property Tests. 542-554 - Tobias Friedrich, Lionel Levine
Fast Simulation of Large-Scale Growth Models. 555-566 - Andreas Galanis, Qi Ge, Daniel Stefankovic
Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model. 567-578 - Oded Goldreich
Proximity Oblivious Testing and the Role of Invariances. 579-592 - Venkatesan Guruswami, Carol Wang:
Optimal Rate List Decoding via Derivative Codes. 593-604 - Brett Hemenway, Rafail Ostrovsky, Martin J. Strauss, Mary Wootters:
Public Key Locally Decodable Codes with Short Keys. 605-615 - Zhiyi Huang
On Sampling from Multivariate Distributions. 616-627 - Daniel Kane, Raghu Meka, Jelani Nelson:
Almost Optimal Explicit Johnson-Lindenstrauss Families. 628-639 - Shachar Lovett
Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 - o(1) Symmetric Gates. 640-651 - Sarah Miracle, Dana Randall, Amanda Pascoe Streib:
Clustering in Interfering Binary Mixtures. 652-663 - Dana Ron
Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity. 664-675 - Dana Ron
On Approximating the Number of Relevant Variables in a Function. 676-687 - Thomas Watson:
Query Complexity in Errorless Hardness Amplification. 688-699
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-31 21:31 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: