default search action
30th SODA 2019: San Diego, California, USA
- Timothy M. Chan:
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019. SIAM 2019, ISBN 978-1-61197-548-2 - Front Matter. i-ix
- Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein:
Fine-grained Complexity Meets IP = PSPACE. 1-20 - Lijie Chen, Ryan Williams:
An Equivalence Class for Orthogonal Vectors. 21-40 - Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay:
SETH-Based Lower Bounds for Subset Sum and Bicriteria Path. 41-57 - Kyriakos Axiotis, Arturs Backurs, Ce Jin, Christos Tzamos
, Hongxun Wu:
Fast Modular Subset Sum using Linear Sketching. 58-69 - Marcin Mucha, Karol Wegrzycki
A Subquadratic Approximation Scheme for Partition. 70-88 - Sébastien Bubeck, Michael B. Cohen, James R. Lee, Yin Tat Lee:
Metrical task systems on trees via mirror descent and unfair gluing. 89-97 - Niv Buchbinder, Anupam Gupta, Marco Molinaro, Joseph (Seffi) Naor:
k-Servers with a Smile: Online Algorithms via Projections. 98-116 - C. J. Argue, Sébastien Bubeck, Michael B. Cohen, Anupam Gupta, Yin Tat Lee:
A Nearly-Linear Bound for Chasing Nested Convex Bodies. 117-122 - Pavel Veselý
A ϕ-Competitive Algorithm for Scheduling Packets with Deadlines. 123-142 - Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar
Elastic Caching. 143-156 - Santiago R. Balseiro, Vahab S. Mirrokni, Renato Paes Leme, Song Zuo:
Dynamic Double Auctions: Towards First Best. 157-172 - Yuan Deng, Debmalya Panigrahi:
Multi-unit Supply-monotone Auctions with Bayesian Valuations. 173-192 - Xiaohui Bei
Correlation-Robust Analysis of Single Item Auction. 193-208 - Yaonan Jin, Pinyan Lu
Tight Revenue Gaps among Simple Mechanisms. 209-228 - Itai Ashlagi, Amin Saberi, Ali Shameli:
Assignment Mechanisms under Distributional Constraints. 229-240 - Niv Buchbinder, Moran Feldman, Mohit Garg:
Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid. 241-254 - Matthew Fahrbach, Vahab S. Mirrokni, Morteza Zadimoghaddam:
Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity. 255-273 - Alina Ene, Huy L. Nguyen:
Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time. 274-282 - Eric Balkanski, Aviad Rubinstein, Yaron Singer:
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. 283-302 - Chandra Chekuri, Kent Quanrud:
Submodular Function Maximization in Parallel via the Multilinear Relaxation. 303-322 - Arpit Agarwal, Sepehr Assadi, Sanjeev Khanna:
Stochastic Submodular Cover with Limited Adaptivity. 323-342 - Marco Molinaro:
Stochastic ℓp Load Balancing and Moment Problems via the L-Function Method. 343-354 - Ahmed Abdelkader, Sunil Arya, Guilherme Dias da Fonseca, David M. Mount
Approximate Nearest Neighbor Searching with Non-Euclidean and Weighted Distances. 355-372 - Jie Xue
Colored range closest-pair problem under general distance functions. 373-390 - Eunjin Oh:
Optimal Algorithm for Geodesic Nearest-point Voronoi Diagrams in Simple Polygons. 391-409 - Adrian Dumitrescu, Ritankar Mandal:
New Lower Bounds for the Number of Pseudoline Arrangements. 410-425 - Jie Han, Yoshiharu Kohayakawa
Extremal and probabilistic results for order types. 426-435 - Joshua Brakensiek, Venkatesan Guruswami:
An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. 436-455 - Monaldo Mastrolilli:
The Complexity of the Ideal Membership Problem for Constrained Problems Over the Boolean Domain. 456-475 - Jin-Yi Cai, Artem Govorov:
Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms. 476-495 - Matti Karppa, Petteri Kaski:
Probabilistic Tensors and Opportunistic Boolean Matrix Multiplication. 496-515 - Huy L. Nguyen:
Fast greedy for linear matroids. 516-524 - Robert Krauthgamer, James R. Lee, Havana Rika
Flow-Cut Gaps and Face Covers in Planar Graphs. 525-534 - Ario Salmasi, Anastasios Sidiropoulos, Vijay Sridhar:
On Constant Multi-Commodity Flow-Cut Gaps for Families of Directed Minor-Free Graphs. 535-553 - Yipu Wang:
Maximum Integer Flows in Directed Planar Graphs with Vertex Capacities and Multiple Sources and Sinks. 554-568 - Nathaniel Lahn
A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs. 569-588 - David Eppstein, Bruce A. Reed:
Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time. 589-605 - Ofer Grossman, Yang P. Liu:
Reproducibility and Pseudo-Determinism in Log-Space. 606-620 - Rocco A. Servedio
Pseudorandomness for read-k DNF formulas. 621-638 - Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse
Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits. 639-646 - Vishwas Bhargava
A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials. 647-661 - Mark Bun, Robin Kothari, Justin Thaler:
Quantum algorithms and approximating polynomials for composed functions with shared inputs. 662-678 - Gautam Kamath
Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing. 679-693 - Nathaniel Harms:
Testing Halfspaces over Rotation-Invariant Distributions. 694-713 - Hendrik Fichtenberger
Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty. 714-726 - Maria-Florina Balcan, Yi Li, David P. Woodruff, Hongyang Zhang:
Testing Matrix Rank, Optimally. 727-746 - Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff:
A PTAS for ℓp-Low Rank Approximation. 747-766 - Sepehr Assadi, Yu Chen, Sanjeev Khanna
Sublinear Algorithms for (Δ + 1) Vertex Coloring. 767-786 - Shiri Chechik, Doron Mukhtar:
Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model. 787-804 - Mohsen Ghaffari:
Distributed Maximal Independent Set using Small Messages. 805-820 - Yi-Jun Chang
Distributed Triangle Detection via Expander Decomposition. 821-840 - David G. Harris:
Oblivious resampling oracles and parallel algorithms for the Lopsided Lovász Local Lemma. 841-860 - Rohit Gurjar, Nisheeth K. Vishnoi:
On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes). 861-880 - Kyle Fox, Debmalya Panigrahi, Fred Zhang:
Minimum Cut and Minimum k-Cut in Hypergraphs via Branching Contractions. 881-896 - Ali Bibak, Charles Carlson, Karthekeyan Chandrasekaran:
Improving the smoothed complexity of FLIP for max cut problems. 897-916 - Max Klimm, Philipp Warode
Computing all Wardrop Equilibria parametrized by the Flow Demand. 917-934 - Leon Sering
Nash Flows Over Time with Spillback. 935-945 - Colin Cooper, Alan M. Frieze, Wesley Pegden:
On the rank of a random binary matrix. 946-955 - Varun Kanade, Frederik Mallmann-Trenn, Thomas Sauerwald:
On coalescence time in graphs: When is coalescing as fast as meeting?: Extended Abstract. 956-965 - Georgios Amanatidis
Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences and 2-Class Joint Degree Matrices. 966-985 - Andrej Bogdanov, Manuel Sabin, Prashant Nalini Vasudevan:
XOR Codes and Sparse Learning Parity with Noise. 986-1004 - Elchanan Mossel, Jiaming Xu:
Seeded Graph Matching via Large Neighborhood Statistics. 1005-1014 - Sándor Kisfaludi-Bak
Nearly ETH-tight algorithms for Planar Steiner Tree with Terminals on Few Faces. 1015-1034 - Fahad Panolan
Contraction Decomposition in Unit Disk Graphs and Algorithmic Applications in Parameterized Complexity. 1035-1054 - MohammadHossein Bateni, Alireza Farhadi, MohammadTaghi Hajiaghayi:
Polynomial-time Approximation Scheme for Minimum k-cut in Planar and Minor-free Graphs. 1055-1068 - Eli Fox-Epstein, Philip N. Klein, Aaron Schild:
Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems. 1069-1088 - Antonios Antoniadis, Krzysztof Fleszar
A PTAS for Euclidean TSP with Hyperplane Neighborhoods. 1089-1105 - Raphaël Clifford, Tomasz Kociumaka, Ely Porat:
The streaming k-mismatch problem. 1106-1125 - Karl Bringmann, Marvin Künnemann, Philip Wellnitz
Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts. 1126-1145 - Vincent Cohen-Addad, Laurent Feuilloley
Lower bounds for text indexing with mismatches and differences. 1146-1164 - William Kuszmaul:
Efficiently Approximating Edit Distance Between Pseudorandom Strings. 1165-1180 - MohammadTaghi Hajiaghayi, Masoud Seddighin
Approximating LCS in Linear Time: Beating the √n Barrier. 1181-1200 - Günter Rote:
The Maximum Number of Minimal Dominating Sets in a Tree. 1201-1214 - Zilin Jiang, Nikita Polyanskii:
How to guess an n-digit number. 1215-1220 - Raphael Yuster:
Vector clique decompositions. 1221-1238 - Sophie Spirkl, Maria Chudnovsky, Mingxian Zhong:
Four-coloring P6-free graphs. 1239-1256 - Andrzej Grzesik
Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs. 1257-1271 - Sam Buss, Alexander Knop:
Strategies for Stable Merge Sorting. 1272-1290 - Haim Kaplan, Or Zamir, Uri Zwick:
A sort of an adversary. 1291-1310 - Caleb C. Levy, Robert E. Tarjan:
A New Path from Splay to Dynamic Optimality. 1311-1330 - Shunhua Jiang, Kasper Green Larsen:
A Faster External Memory Priority Queue with DecreaseKeys. 1331-1343 - Dominik Kempa:
Optimal Construction of Compressed Indexes for Highly Repetitive Texts. 1344-1357 - Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee
Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness. 1358-1368 - Aleksandar Nikolov, Mohit Singh, Uthaipon Tao Tantipongpipat:
Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design. 1369-1386 - AmirMahdi Ahmadinejad, Arun Jambulapati, Amin Saberi, Aaron Sidford:
Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications. 1387-1404 - Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva:
Iterative Refinement for ℓp-norm Regression. 1405-1424 - András Gilyén, Srinivasan Arunachalam, Nathan Wiebe:
Optimizing quantum optimization algorithms via faster quantum gradient computation. 1425-1444 - Julia Chuzhoy, Zihan Tan
Towards Tight(er) Bounds for the Excluded Grid Theorem. 1445-1464 - Meike Hatzel, Ken-ichi Kawarabayashi, Stephan Kreutzer:
Polynomial Planar Directed Grid Theorem. 1465-1484 - Wouter Cames van Batenburg
A tight Erdős-Pósa function for planar minors. 1485-1500 - Michal Pilipczuk, Sebastian Siebertz
Polynomial bounds for centered colorings on proper minor-closed graph classes. 1501-1520 - Vida Dujmovic, Fabrizio Frati
Every Collinear Set in a Planar Graph Is Free. 1521-1538 - Rico Zenklusen:
A 1.5-Approximation for Path TSP. 1539-1549 - Martin Nägele
A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond. 1550-1569 - Shashwat Garg, Janardhan Kulkarni, Shi Li:
Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time. 1570-1584 - Uriel Feige, Janardhan Kulkarni, Shi Li:
A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time. 1585-1595 - Chandra Chekuri, Kent Quanrud:
On Approximating (Sparse) Covering Integer Programs. 1596-1615 - Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, Cliff Stein:
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. 1616-1635 - Mohsen Ghaffari, Jara Uitto
Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation. 1636-1653 - MohammadTaghi Hajiaghayi, Saeed Seddighin, Xiaorui Sun:
Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence. 1654-1672 - Merav Parter, Eylon Yogev:
Low Congestion Cycle Covers and Their Applications. 1673-1692 - Merav Parter, Eylon Yogev:
Distributed Algorithms Made Secure: A Graph Theoretic Approach. 1693-1710 - Akanksha Agrawal
Interval Vertex Deletion Admits a Polynomial Kernel. 1711-1730 - Anupam Gupta, Euiwoong Lee
Losing Treewidth by Separating Subsets. 1731-1749 - Gregory Z. Gutin, Magnus Wahlström
On r-Simple k-Path and Related Problems Parameterized by k/r. 1750-1769 - André Berger, László Kozma, Matthias Mnich
A time- and space-optimal algorithm for the many-visits TSP. 1770-1782 - Andris Ambainis, Kaspars Balodis, Janis Iraids, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs:
Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. 1783-1793 - Alexander Wei:
Optimal Las Vegas Approximate Near Neighbors in ℓp. 1794-1813 - Subhash Khot, Assaf Naor:
The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics. 1814-1824 - Ruosong Wang, David P. Woodruff:
Tight Bounds for ℓp Oblivious Subspace Embeddings. 1825-1843 - Jelani Nelson, Huacheng Yu:
Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation. 1844-1860 - Madhu Sudan, Badih Ghazi, Noah Golowich, Mitali Bafna:
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation. 1861-1871 - Sayan Bhattacharya, Janardhan Kulkarni:
Deterministically Maintaining a (2 + ∊)-Approximate Minimum Vertex Cover in O(1/∊2) Amortized Update Time. 1872-1885 - Fabrizio Grandoni
(1 + ε)-Approximate Incremental Matching in Constant Deterministic Amortized Time. 1886-1898 - Aaron Bernstein, Sebastian Forster, Monika Henzinger
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching. 1899-1918 - Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon:
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time. 1919-1936 - Ran Duan, Haoqing He, Tianyi Zhang:
Dynamic Edge Coloring with Improved Approximation. 1937-1945 - José Correa, Raimundo Saona
Prophet Secretary Through Blind Strategies. 1946-1961 - Shuchi Chawla, J. Benjamin Miller, Yifeng Teng:
Pricing for Online Resource Allocation: Intervals and Paths. 1962-1981 - Rebecca Reiffenhäuser
An Optimal Truthful Mechanism for the Online Weighted Bipartite Matching Problem. 1982-1993 - Eshwar Ram Arunachaleswaran, Siddharth Barman, Nidhi Rathi:
Fully Polynomial-Time Approximation Schemes for Fair Rent Division. 1994-2013 - Benjamin Plaut, Tim Roughgarden:
Communication Complexity of Discrete Fair Division. 2014-2033 - Gianfranco Bilardi, Lorenzo De Stefani:
The I/O complexity of Toom-Cook integer multiplication. 2034-2052 - Nairen Cao, Jeremy T. Fineman, Katina Russell, Eugene Yang
I/O-Efficient Algorithms for Topological Sort and Related Problems. 2053-2070 - Greg Bodwin:
On the Structure of Unique Shortest Paths in Graphs. 2071-2089 - Shiri Chechik, Sarel Cohen:
Near Optimal Algorithms For The Single Source Replacement Paths Problem. 2090-2109 - Panagiotis Charalampopoulos, Shay Mozes
Exact Distance Oracles for Planar Graphs with Failing Vertices. 2110-2123 - Irit Dinur
Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests: [Extended abstract]. 2124-2133 - Irit Dinur
List Decoding with Double Samplers. 2134-2153 - Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin:
Maximally Recoverable LRCs: A field size lower bound and constructions for few heavy parities. 2154-2170 - Yeow Meng Chee
Binary Robust Positioning Patterns with Low Redundancy and Efficient Locating Algorithms. 2171-2184 - Kuan Cheng, Bernhard Haeupler, Xin Li, Amirbehshad Shahrasbi
Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets. 2185-2204 - Jacob Focke, Leslie Ann Goldberg, Stanislav Zivný:
The Complexity of Approximately Counting Retractions. 2205-2215 - Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau, Luke Postle:
Improved Bounds for Randomly Sampling Colorings via Linear Programming. 2216-2234 - Matthew Jenssen
Algorithms for #BIS-hard problems on expander graphs. 2235-2247 - Jin-Yi Cai, Tianyu Liu, Pinyan Lu
Approximability of the Six-vertex Model. 2248-2261 - Heng Guo, Chao Liao, Pinyan Lu
Zeros of Holant problems: locations and algorithms. 2262-2278 - Shi Li:
On Facility Location with General Lower Bounds. 2279-2290 - Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh:
Hierarchical Clustering better than Average-Linkage. 2291-2304 - Yash Deshpande, Andrea Montanari, Ryan O'Donnell, Tselil Schramm, Subhabrata Sen:
The threshold for SDP-refutation of random regular NAE-3SAT. 2305-2321 - Prasad Raghavendra, Nick Ryder, Nikhil Srivastava, Benjamin Weitz:
Exponential Lower Bounds on Spectrahedral Representations of Hyperbolicity Cones. 2322-2332 - Wojciech Czerwinski, Laure Daviaud
Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games. 2333-2349 - Karim A. Adiprasito
Theorems of Carathéodory, Helly, and Tverberg without dimension. 2350-2360 - Prosenjit Bose, Jean-Lou De Carufel, Darryl Hill, Michiel H. M. Smid:
On the Spanning and Routing Ratio of Theta-Four. 2361-2370 - Glencora Borradaile, Hung Le, Christian Wulff-Nilsen:
Greedy spanners are optimal in doubling metrics. 2371-2379 - Amir Nayyeri, Benjamin Raichel:
Viewing the Rings of a Tree: Minimum Distortion Embeddings into Trees. 2380-2399 - Daniel Busto, William S. Evans, David G. Kirkpatrick:
Minimizing Interference Potential Among Moving Entities. 2400-2418 - Wei-Kai Lin, Elaine Shi, Tiancheng Xie:
Can We Overcome the n log n Barrier for Oblivious Sorting? 2419-2438 - Riko Jacob, Kasper Green Larsen, Jesper Buus Nielsen:
Lower Bounds for Oblivious Data Structures. 2439-2447 - T.-H. Hubert Chan, Kai-Min Chung, Bruce M. Maggs, Elaine Shi:
Foundations of Differentially Oblivious Algorithms. 2448-2467 - Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, Abhradeep Thakurta:
Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity. 2468-2479 - Jaroslaw Blasiok
Towards Instance-Optimal Private Query Release. 2480-2497 - Anders Aamand, Mikkel Thorup
Non-empty Bins with Simple Tabulation Hashing. 2498-2512 - Xue Chen:
Derandomized Balanced Allocation. 2513-2526 - Michael A. Bender, Jake Christensen, Alex Conway, Martin Farach-Colton
Optimal Ball Recycling. 2527-2546 - Rebecca Hoberg, Thomas Rothvoss:
A Fourier-Analytic Approach for the Discrepancy of Random Set Systems. 2547-2556 - Nikhil Bansal, Raghu Meka:
On the discrepancy of random low degree set systems. 2557-2564 - Charles Carlson, Alexandra Kolla, Nikhil Srivastava, Luca Trevisan
Optimal Lower Bounds for Sketching Graph Cuts. 2565-2569 - Tasuku Soma
Spectral Sparsification of Hypergraphs. 2570-2581 - Yuichi Yoshida:
Cheeger Inequalities for Submodular Transformations. 2582-2601 - Yang P. Liu, Sushant Sachdeva, Zejun Yu:
Short Cycles via Low-Diameter Decompositions. 2602-2615 - Thatchaphol Saranurak
Expander Decomposition and Pruning: Faster, Stronger, and Simpler. 2616-2635 - Boris Aronov, Esther Ezra, Joshua Zahl:
Constructive Polynomial Partitioning for Algebraic Curves in R3 with Applications. 2636-2648 - Tamal K. Dey:
Computing Height Persistence and Homology Generators in R3 Efficiently. 2649-2662 - Ulrich Bauer
Hardness of Approximation for Morse Matching. 2663-2674 - Aruni Choudhary, Michael Kerber, Sharath Raghvendra:
Improved Topological Approximations by Digitization. 2675-2688 - Jose Balanza-Martinez, Austin Luchsinger, David Caballero, Rene Reyes, Angel A. Cantu, Robert T. Schweller, Luis Angel Garcia, Tim Wylie:
Full Tilt: Universal Constructors for General Shapes with Uniform External Forces. 2689-2708 - Michael Kapralov
Dimension-independent Sparse Fourier Transform. 2709-2728 - Akshay Kamath, Eric Price:
Adaptive Sparse Recovery with Limited Adaptivity. 2729-2744 - Ilias Diakonikolas, Weihao Kong, Alistair Stewart:
Efficient Algorithms and Lower Bounds for Robust Linear Regression. 2745-2754 - Yu Cheng
High-Dimensional Robust Mean Estimation in Nearly-Linear Time. 2755-2771 - Zhao Song, David P. Woodruff, Peilin Zhong:
Relative Error Tensor Low Rank Approximation. 2772-2789 - Yuri Faenza, Telikepalli Kavitha, Vladlena Powers, Xingyu Zhang:
Popular Matchings and Limits to Tractability. 2790-2809 - Sushmita Gupta, Pranabendu Misra, Saket Saurabh, Meirav Zehavi:
Popular Matching in Roommates Setting is NP-hard. 2810-2822 - Chi-Kit Lam, C. Gregory Plaxton:
A (1 + 1/e)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete Lists. 2823-2840 - Buddhima Gamlath, Sagar Kale, Ola Svensson:
Beating Greedy for Stochastic Bipartite Matching. 2841-2854 - Soheil Behnezhad, Alireza Farhadi, MohammadTaghi Hajiaghayi, Nima Reyhani:
Stochastic Matching with Few Queries: New Algorithms and Tools. 2855-2874 - Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang, Runzhou Tao
Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model. 2875-2886 - Kevin Buchin
SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension. 2887-2901 - Karl Bringmann, Marvin Künnemann, André Nusser:
Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability. 2902-2921 - Kevin Buchin
Approximating (k, ℓ)-center clustering for curves. 2922-2938 - Anna Großwendt, Heiko Röglin
Analysis of Ward's Method. 2939-2957 - Zachary Friggstad, Kamyar Khodamoradi
Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-MEANS. 2958-2972
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-11-04 20:29 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: