default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDAPPROX/RANDOM 2024: London, UK
- Amit Kumar
, Noga Ron-Zewi:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024, August 28-30, 2024, London School of Economics, London, UK. LIPIcs 317, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2024, ISBN 978-3-95977-348-5 - Front Matter, Table of Contents, Preface, Conference Organization. 0:i-0:xxvi
- Susanne Armbruster, Matthias Mnich, Martin Nägele:
A (3/2 + 1/e)-Approximation Algorithm for Ordered TSP. 1:1-1:18 - Shuchi Chawla, Dimitris Christou:
Online Time-Windows TSP with Predictions. 2:1-2:21 - Michael Dinitz, Guy Kortsarz, Shi Li:
Degrees and Network Design: New Problems and Approximations. 3:1-3:17 - Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, Meirav Zehavi:
Hybrid k-Clustering: Blending k-Median and k-Center. 4:1-4:19 - Divyarthi Mohan, Pawel Pralat:
Asynchronous Majority Dynamics on Binomial Random Graphs. 5:1-5:20 - Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi:
Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3. 6:1-6:14 - Johan Håstad, Björn Martinsson, Tamio-Vesa Nakajima, Stanislav Zivný:
A Logarithmic Approximation of Linearly-Ordered Colourings. 7:1-7:6 - Josef Minarík, Jirí Sgall:
Speed-Robust Scheduling Revisited. 8:1-8:20 - Karthekeyan Chandrasekaran, Chandra Chekuri, Manuel R. Torres, Weihao Zhu:
On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms. 9:1-9:21 - Martin Böhm, Matej Lieskovský, Sören Schmitt, Jirí Sgall, Rob van Stee:
Improved Online Load Balancing with Known Makespan. 10:1-10:21 - Björn Martinsson:
On the NP-Hardness Approximation Curve for Max-2Lin(2). 11:1-11:38 - Tomer Ezra, Stefano Leonardi, Michal Pawlowski, Matteo Russo, Seeun William Umboh:
Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment. 12:1-12:24 - Kshipra Bhawalkar, Zhe Feng, Anupam Gupta, Aranyak Mehta, David Wajc, Di Wang:
The Average-Value Allocation Problem. 13:1-13:23 - Moritz Buchem, Franziska Eberle, Hugo Kooki Kasuya Rosado, Kevin Schewior, Andreas Wiese:
Scheduling on a Stochastic Number of Machines. 14:1-14:15 - Yaron Fairstein, Joseph (Seffi) Naor, Tomer Tsachor:
Distributional Online Weighted Paging with Limited Horizon. 15:1-15:15 - Diba Hashemi, Weronika Wrzos-Kaminska:
Weighted Matching in the Random-Order Streaming and Robust Communication Models. 16:1-16:26 - Evripidis Bampis, Konstantinos Dogeas, Thomas Erlebach, Nicole Megow, Jens Schlöter, Amitabh Trehan:
Competitive Query Minimization for Stable Matching with One-Sided Uncertainty. 17:1-17:21 - Hao Sun:
A Constant Factor Approximation for Directed Feedback Vertex Set in Graphs of Bounded Genus. 18:1-18:20 - Surendra Ghentiyala, Noah Stephens-Davidowitz:
More Basis Reduction for Linear Codes: Backward Reduction, BKZ, Slide Reduction, and More. 19:1-19:22 - Benjamin Moseley, Heather Newman, Kirk Pruhs:
Online k-Median with Consistent Clusters. 20:1-20:22 - Daniel Hathcock, Guy Kortsarz, R. Ravi:
The Telephone k-Multicast Problem. 21:1-21:16 - Matthew Casey, Rajmohan Rajaraman, David Stalfa, Cheng Tan:
Scheduling Splittable Jobs on Configurable Machines. 22:1-22:20 - Mayank Goswami, Riko Jacob:
On Instance-Optimal Algorithms for a Generalization of Nuts and Bolts and Generalized Sorting. 23:1-23:23 - Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah, Chen Wang:
Learning-Augmented Maximum Independent Set. 24:1-24:18 - Philip Cervenjak, Junhao Gan, Seeun William Umboh, Anthony Wirth:
Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound. 25:1-25:23 - Mridul Nandi, N. V. Vinodchandran, Arijit Ghosh, Kuldeep S. Meel, Soumit Pal, Sourav Chakraborty:
Improved Streaming Algorithm for the Klee's Measure Problem and Generalizations. 26:1-26:21 - Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai:
An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding. 27:1-27:17 - Pratik Ghosal, Syed Mohammad Meesum, Katarzyna Paluch:
Rectangle Tiling Binary Arrays. 28:1-28:17 - David Alemán Espinosa, Chaitanya Swamy:
Approximation Algorithms for Correlated Knapsack Orienteering. 29:1-29:24 - Gabriel Arpino, Daniil Dmitriev, Nicolò Grometto:
Greedy Heuristics and Linear Relaxations for the Random Hitting Set Problem. 30:1-30:22 - Amnon Ta-Shma, Ron Zadicario:
The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced. 31:1-31:22 - Xiaoyu Chen, Heng Guo, Xinyuan Zhang, Zongrui Zou:
Near-Linear Time Samplers for Matroid Independent Sets with Applications. 32:1-32:12 - Ishaq Aden-Ali, Yanjun Han, Jelani Nelson, Huacheng Yu:
On the Amortized Complexity of Approximate Counting. 33:1-33:17 - Ashish Gola, Igor Shinkar, Harsimran Singh:
Matrix Multiplication Reductions. 34:1-34:15 - Ishay Haviv, Michal Parnas:
Testing Intersectingness of Uniform Families. 35:1-35:15 - Lap Chi Lau, Dante Tjowasi:
On the Houdré-Tetali Conjecture About an Isoperimetric Constant of Graphs. 36:1-36:18 - Hadley Black:
Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions. 37:1-37:23 - Nader H. Bshouty, George Haddad:
Approximating the Number of Relevant Variables in a Parity Implies Proper Learning. 38:1-38:15 - Arnab Chatterjee, Amin Coja-Oghlan, Noëla Müller, Connor Riddlesden, Maurice Rolvien, Pavel Zakharov, Haodong Zhu:
The Number of Random 2-SAT Solutions Is Asymptotically Log-Normal. 39:1-39:15 - Monika Henzinger, A. R. Sricharan, Teresa Anna Steiner:
Private Counting of Distinct Elements in the Turnstile Model and Extensions. 40:1-40:21 - Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan:
Hilbert Functions and Low-Degree Randomness Extractors. 41:1-41:24 - Huck Bennett, Karthik Gajulapalli, Alexander Golovnev, Philip G. Warton:
Matrix Multiplication Verification Using Coding Theory. 42:1-42:13 - Eden Fargion, Ran Gelles, Meghal Gupta:
Interactive Coding with Unbounded Noise. 43:1-43:16 - Ashish Dwivedi, Zeyu Guo, Ben Lee Volk:
Optimal Pseudorandom Generators for Low-Degree Polynomials over Moderately Large Fields. 44:1-44:19 - Tomer Adar, Eldar Fischer:
Refining the Adaptivity Notion in the Huge Object Model. 45:1-45:16 - Tomer Adar, Eldar Fischer, Amit Levi:
Support Testing in the Huge Object Model. 46:1-46:16 - Evan Chang, Neel Kolhe, Youngtak Sohn:
Upper Bounds on the 2-Colorability Threshold of Random d-Regular k-Uniform Hypergraphs for k ≥ 3. 47:1-47:23 - Tomer Adar, Eldar Fischer, Amit Levi:
Improved Bounds for High-Dimensional Equivalence and Product Testing Using Subcube Queries. 48:1-48:21 - Holden Lee:
Parallelising Glauber Dynamics. 49:1-49:24 - Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii:
Towards Simpler Sorting Networks and Monotone Circuits for Majority. 50:1-50:18 - Halley Goldberg, Valentine Kabanets:
Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity. 51:1-51:19 - Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio:
Trace Reconstruction from Local Statistical Queries. 52:1-52:24 - Dean Doron, Jonathan Mosheiff, Mary Wootters:
When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound? 53:1-53:12 - Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer:
Parallel Repetition of k-Player Projection Games. 54:1-54:16 - Praneeth Kacham, David P. Woodruff:
Faster Algorithms for Schatten-p Low Rank Approximation. 55:1-55:19 - Aiya Kuchukova, Marcus Pappik, Will Perkins, Corrine Yap:
Fast and Slow Mixing of the Kawasaki Dynamics on Bounded-Degree Graphs. 56:1-56:24 - Uri Meir, Gregory Schwartzman, Yuichi Yoshida:
Stochastic Distance in Property Testing. 57:1-57:13 - Vedat Levi Alev, Shravas Rao:
Expanderizing Higher Order Random Walks. 58:1-58:24 - Elad Aigner-Horev, Dan Hefetz, Mathias Schacht:
Ramsey Properties of Randomly Perturbed Hypergraphs. 59:1-59:18 - Reut Levi, Moti Medina, Omer Tubul:
Nearly Optimal Local Algorithms for Constructing Sparse Spanners of Clusterable Graphs. 60:1-60:21 - Kuan Cheng, Minghui Ouyang, Chong Shangguan, Yuanting Shen:
When Can an Expander Code Correct Ω(n) Errors in O(n) Time? 61:1-61:23 - Yotam Dikstein, Irit Dinur:
Coboundary and Cosystolic Expansion Without Dependence on Dimension or Degree. 62:1-62:24 - Vishesh Jain, Clayton Mizgerd:
Rapid Mixing of the Down-Up Walk on Matchings of a Fixed Size. 63:1-63:13 - Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh:
On the Communication Complexity of Finding a King in a Tournament. 64:1-64:23 - Venkatesan Guruswami, Hsin-Po Wang:
Capacity-Achieving Gray Codes. 65:1-65:9 - Noam Mazor, Rafael Pass:
On Black-Box Meta Complexity and Function Inversion. 66:1-66:12 - Nicholas Harvey, Arvin Sahami:
Explicit and Near-Optimal Construction of t-Rankwise Independent Permutations. 67:1-67:12 - Inbar Ben Yaacov, Yotam Dikstein, Gal Maor:
Sparse High Dimensional Expanders via Local Lifts. 68:1-68:24 - Kuan Cheng, Ruiyang Wu:
Randomness Extractors in AC⁰ and NC¹: Optimal up to Constant Factors. 69:1-69:22 - Andreas Galanis, Alkis Kalavasis, Anthimos Vardis Kandiros:
On Sampling from Ising Models with Spectral Constraints. 70:1-70:14 - Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh:
Approximate Degree Composition for Recursive Functions. 71:1-71:17 - Tal Herman:
Public Coin Interactive Proofs for Label-Invariant Distribution Properties. 72:1-72:23 - Jakub Tetek:
Additive Noise Mechanisms for Making Randomized Approximation Algorithms Differentially Private. 73:1-73:20 - Kostas Lakis, Johannes Lengler, Kalina Petrova, Leon Schiller:
Improved Bounds for Graph Distances in Scale Free Percolation and Related Models. 74:1-74:22 - Pranjal Dutta, Amit Sinhababu, Thomas Thierauf:
Derandomizing Multivariate Polynomial Factoring for Low Degree Factors. 75:1-75:20
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 2025-03-08 00:35 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:
