Data Structures and Algorithms

Authors and titles for cs.DS in Oct 2021

[1]  arXiv:2110.00074 [pdf, other]

Title: Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs

Authors: Jacob Evald, Viktor Fredslund-Hansen, Christian Wulff-Nilsen

Comments: 15 pages, 3 figures

Subjects: Data Structures and Algorithms (cs.DS)

[2]  arXiv:2110.00287 [pdf, other]

Title: An Exact, Linear Time Barabási-Albert Algorithm

Authors: Giorgos Stamatelatos, Pavlos S. Efraimidis

Subjects: Data Structures and Algorithms (cs.DS)

[3]  arXiv:2110.00391 [pdf, ps, other]

Title: Online Primal-Dual Algorithms with Predictions for Packing Problems

Authors: Nguyen Kim Thang, Christoph Durr

Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)

[4]  arXiv:2110.00495 [pdf, ps, other]

Title: Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree

Authors: Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, Minshen Zhu

Comments: Accepted by IPEC 2020. arXiv admin note: substantial text overlap with arXiv:1909.07915

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)

[5]  arXiv:2110.00504 [pdf, other]

Title: Adwords with Unknown Budgets and Beyond

Authors: Rajan Udwani

Comments: To appear in Management Science

Subjects: Data Structures and Algorithms (cs.DS)

[6]  arXiv:2110.00548 [pdf, other]

Title: Spirality and Rectilinear Planarity Testing of Independent-Parallel SP-Graphs

Authors: Walter Didimo, Michael Kaufmann, Giuseppe Liotta, Giacomo Ortali

Subjects: Data Structures and Algorithms (cs.DS)

[7]  arXiv:2110.00744 [pdf, ps, other]

Title: Random Subgraph Detection Using Queries

Authors: Wasim Huleihel, Arya Mazumdar, Soumyabrata Pal

Comments: 27 pages

Subjects: Data Structures and Algorithms (cs.DS); Information Theory (cs.IT); Machine Learning (cs.LG); Statistics Theory (math.ST)

[8]  arXiv:2110.00827 [pdf, ps, other]

Title: Deterministic Algorithms for the Hidden Subgroup Problem

Authors: Zekun Ye, Lvzhou Li

Journal-ref: Information and Computation.Available online 14 October 2022, 104975

Subjects: Data Structures and Algorithms (cs.DS)

[9]  arXiv:2110.01030 [pdf, other]

Title: A Recursive Algorithm for Solving Simple Stochastic Games

Authors: Xavier Badin de Montjoye

Subjects: Data Structures and Algorithms (cs.DS); Computer Science and Game Theory (cs.GT)

[10]  arXiv:2110.01111 [pdf, ps, other]

Title: Is this the simplest (and most surprising) sorting algorithm ever?

Authors: Stanley P. Y. Fung

Comments: 7 pages, 0 figures

Subjects: Data Structures and Algorithms (cs.DS)

[11]  arXiv:2110.01181 [pdf, other]

Title: FM-Indexing Grammars Induced by Suffix Sorting for Long Patterns

Authors: Jin Jie Deng, Wing-Kai Hon, Dominik Köppl, Kunihiko Sadakane

Subjects: Data Structures and Algorithms (cs.DS)

[12]  arXiv:2110.01213 [pdf, other]

Title: Clique percolation method: memory efficient almost exact communities

Authors: Alexis Baudin, Maximilien Danisch, Sergey Kirgizov, Clémence Magnien, Marwan Ghanem

Comments: 15 pages, 5 figures, 1 table

Subjects: Data Structures and Algorithms (cs.DS); Information Retrieval (cs.IR); Social and Information Networks (cs.SI); Physics and Society (physics.soc-ph)

[13]  arXiv:2110.01868 [pdf, other]

Title: Preprocessing for Outerplanar Vertex Deletion: An Elementary Kernel of Quartic Size

Authors: Huib Donkers, Bart M. P. Jansen, Michał Włodarczyk

Subjects: Data Structures and Algorithms (cs.DS)

[14]  arXiv:2110.01901 [pdf, ps, other]

Title: Inferring Hidden Structures in Random Graphs

Authors: Wasim Huleihel

Comments: 43 pages

Subjects: Data Structures and Algorithms (cs.DS); Information Theory (cs.IT); Machine Learning (cs.LG); Statistics Theory (math.ST)

[15]  arXiv:2110.02387 [pdf, other]

Title: Approximate $\mathrm{CVP}$ in time $2^{0.802 \, n}$ -- now in any norm!

Authors: Thomas Rothvoss, Moritz Venzin

Subjects: Data Structures and Algorithms (cs.DS)

[16]  arXiv:2110.02400 [pdf, other]

Title: Periodic Reranking for Online Matching of Reusable Resources

Authors: Rajan Udwani

Comments: ACM EC 2022

Subjects: Data Structures and Algorithms (cs.DS)

[17]  arXiv:2110.02503 [pdf, other]

Title: More on Change-Making and Related Problems

Authors: Timothy M. Chan, Qizheng He

Comments: This is the full version of our ESA 2020 paper

Subjects: Data Structures and Algorithms (cs.DS)

[18]  arXiv:2110.02555 [pdf, ps, other]

Title: Profile-based optimal stable matchings in the Roommates problem

Authors: Sofia Simola, David Manlove

Comments: 27 pages, 11 tables, 3 figures

Subjects: Data Structures and Algorithms (cs.DS)

[19]  arXiv:2110.02688 [pdf, ps, other]

Title: Towards Non-Uniform k-Center with Constant Types of Radii

Authors: Xinrui Jia, Lars Rohwedder, Kshiteej Sheth, Ola Svensson

Comments: Accepted in SOSA 2022

Subjects: Data Structures and Algorithms (cs.DS)

[20]  arXiv:2110.02709 [pdf, ps, other]

Title: Subquadratic-time algorithm for the diameter and all eccentricities on median graphs

Authors: Pierre Bergé, Guillaume Ducoffe, Michel Habib

Comments: 43 pages, extended abstract in STACS 2022

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)

[21]  arXiv:2110.02730 [pdf, other]

Title: Tight bounds for counting colorings and connected edge sets parameterized by cutwidth

Authors: Carla Groenland, Jesper Nederlof, Isja Mannens, Krisztina Szilágyi

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)

[22]  arXiv:2110.02750 [pdf, other]

Title: Extensions of Karger's Algorithm: Why They Fail in Theory and How They Are Useful in Practice

Authors: Erik Jenner, Enrique Fita Sanmartín, Fred A. Hamprecht

Comments: Oral at ICCV 2021; added acknowledgements

Subjects: Data Structures and Algorithms (cs.DS); Computer Vision and Pattern Recognition (cs.CV); Machine Learning (cs.LG); Machine Learning (stat.ML)

[23]  arXiv:2110.02807 [pdf, other]

Title: Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor

Authors: Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup

Comments: 46 pages, Accepted to FOCS 2021 (Full version)

Subjects: Data Structures and Algorithms (cs.DS)

[24]  arXiv:2110.02830 [pdf, other]

Title: Parameterized Algorithms for the Steiner Arborescence Problem on a Hypercube

Authors: Sugyani Mahapatra, Manikandan Narayanan, N S Narayanaswamy

Subjects: Data Structures and Algorithms (cs.DS)

[25]  arXiv:2110.02898 [pdf, other]

Title: Coresets for Kernel Clustering

Authors: Shaofeng H.-C. Jiang, Robert Krauthgamer, Jianing Lou, Yubo Zhang

Subjects: Data Structures and Algorithms (cs.DS)

[26]  arXiv:2110.03122 [pdf, ps, other]

Title: Faster algorithm for Unique $(k,2)$-CSP

Authors: Or Zamir

Subjects: Data Structures and Algorithms (cs.DS)

[27]  arXiv:2110.03836 [pdf, other]

Title: On the Complexity of Triangle Counting using Emptiness Queries

Authors: Arijit Bishnu, Arijit Ghosh, Gopinath Mishra

Comments: 29 pages

Subjects: Data Structures and Algorithms (cs.DS)

[28]  arXiv:2110.04190 [pdf, other]

Title: On Explicit Constructions of Extremely Depth Robust Graphs

Authors: Jeremiah Blocki, Mike Cinkoske, Seunghoon Lee, Jin Young Son

Comments: 12 pages, 1 figure. This is the full version of the paper published at STACS 2022. We noticed a mistake in the references for the computational intractability of the depth robustness of the graphs and fixed it

Subjects: Data Structures and Algorithms (cs.DS); Cryptography and Security (cs.CR); Combinatorics (math.CO)

[29]  arXiv:2110.04574 [src]

Title: A Faster Algorithm for Max Cut in Dense Graphs

Authors: Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury, Sayantan Sen

Comments: The proof of the main claim in the paper is incomplete, and because of this reason, we are withdrawing the paper

Subjects: Data Structures and Algorithms (cs.DS)

[30]  arXiv:2110.04606 [pdf, other]

Title: Linear-time algorithm for vertex 2-coloring without monochromatic triangles on planar graphs

Authors: Michał Karpiński, Krzysztof Piecuch

Subjects: Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)

[31]  arXiv:2110.04667 [pdf, other]

Title: Competitive Perimeter Defense of Conical Environments

Authors: Shivam Bajaj, Eric Torng, Shaunak D. Bopardikar, Alexander Von Moll, Isaac Weintraub, Eloy Garcia, David W. Casbeer

Comments: Version 2 has additional images

Subjects: Data Structures and Algorithms (cs.DS); Systems and Control (eess.SY)

[32]  arXiv:2110.04933 [pdf, other]

Title: A Faster Algorithm for Maximum Independent Set on Interval Filament Graphs

Authors: Darcy Best, Max Ward

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)

[33]  arXiv:2110.05168 [pdf, other]

Title: On Solving the Minimum Common String Partition Problem by Decision Diagrams

Authors: Miloš Chromý, Markus Sinnl

Comments: 11 pages, 2 tables, 5 graphs, submitted to ICORES'22

Subjects: Data Structures and Algorithms (cs.DS)

[34]  arXiv:2110.05746 [pdf, other]

Title: Improved Analysis of EDCS via Gallai-Edmonds Decomposition

Authors: Soheil Behnezhad

Subjects: Data Structures and Algorithms (cs.DS)

[35]  arXiv:2110.05901 [pdf, ps, other]

Title: Popular matchings with weighted voters

Authors: Klaus Heeger, Ágnes Cseh

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)

[36]  arXiv:2110.06146 [pdf, other]

Title: A SAT Approach to Twin-Width

Authors: André Schidler, Stefan Szeider

Comments: Preprint of a paper to appear at ALENEX'22

Subjects: Data Structures and Algorithms (cs.DS); Logic in Computer Science (cs.LO); Combinatorics (math.CO)

[37]  arXiv:2110.06163 [pdf, other]

Title: Finding Relevant Points for Nearest-Neighbor Classification

Authors: David Eppstein

Comments: 15 pages, 3 figures, to appear at the SIAM Symposium on Simplicity in Algorithms (SOSA22)

Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG); Machine Learning (cs.LG)

[38]  arXiv:2110.06336 [pdf, other]

Title: The VLSAT-2 Benchmark Suite

Authors: Pierre Bouvier (CONVECS ), Hubert Garavel (CONVECS )

Comments: arXiv admin note: substantial text overlap with arXiv:2011.11049

Subjects: Data Structures and Algorithms (cs.DS); Symbolic Computation (cs.SC)

[39]  arXiv:2110.06656 [pdf, other]

Title: Parameterized Complexity of Minimum Membership Dominating Set

Authors: Akanksha Agrawal, Pratibha Choudhary, N. S. Narayanaswamy, K. K. Nisha, Vijayaragunathan Ramamoorthi

Subjects: Data Structures and Algorithms (cs.DS)

[40]  arXiv:2110.07084 [pdf, other]

Title: Online Bipartite Matching with Reusable Resources

Authors: Steven Delong, Alireza Farhadi, Rad Niazadeh, Balasubramanian Sivan, Rajan Udwani

Comments: This paper is a merged version of two ACM EC 2022 papers: (i) "Online Bipartite Matching of Reusable Resources" by Steven Delong, Alireza Farhadi, Rad Niazadeh and Balu Sivan (ii) "Periodic Reranking for Online Matching of Reusable Resources" By Rajan Udwani Journal version: Under submission in Mathematics of Operations Research

Subjects: Data Structures and Algorithms (cs.DS)

[41]  arXiv:2110.07753 [pdf, other]

Title: On Efficient Range-Summability of Ideally IID Random Variables in Two or Higher Dimensions

Authors: Jingfan Meng, Huayi Wang, Jun Xu, Mitsunori Ogihara

Subjects: Data Structures and Algorithms (cs.DS)

[42]  arXiv:2110.08106 [pdf, other]

Title: Compact representation for matrices of bounded twin-width

Authors: Michał Pilipczuk, Marek Sokołowski, Anna Zych-Pawlewicz

Comments: 24 pages, 2 figures

Subjects: Data Structures and Algorithms (cs.DS)

[43]  arXiv:2110.08691 [pdf, other]

Title: Terminal Embeddings in Sublinear Time

Authors: Yeshwanth Cherapanamjeri, Jelani Nelson

Journal-ref: TheoretiCS (March 14, 2024) theoretics:9167

Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG); Machine Learning (cs.LG); Machine Learning (stat.ML)

[44]  arXiv:2110.08782 [pdf, ps, other]

Title: Faster Algorithms for Bounded-Difference Min-Plus Product

Authors: Shucheng Chi, Ran Duan, Tianle Xie

Comments: 13 pages

Subjects: Data Structures and Algorithms (cs.DS)

[45]  arXiv:2110.08840 [pdf, other]

Title: Online Facility Location with Predictions

Authors: Shaofeng H.-C. Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang, Yubo Zhang

Comments: Updated the comparison to a previous work

Subjects: Data Structures and Algorithms (cs.DS)

[46]  arXiv:2110.08886 [pdf, ps, other]

Title: On Monotonicity of Number-Partitioning Algorithms

Authors: Erel Segal-Halevi

Comments: I needed this lemma for something else, and could not find it anywhere, so I wrote a short proof. Is it already known?

Subjects: Data Structures and Algorithms (cs.DS)

[47]  arXiv:2110.08961 [pdf, ps, other]

Title: Algorithms Using Local Graph Features to Predict Epidemics

Authors: Yeganeh Alimohammadi, Christian Borgs, Amin Saberi

Subjects: Data Structures and Algorithms (cs.DS); Combinatorics (math.CO); Probability (math.PR)

[48]  arXiv:2110.08991 [pdf, other]

Title: Dimensionality Reduction for Wasserstein Barycenter

Authors: Zachary Izzo, Sandeep Silwal, Samson Zhou

Comments: Published as a conference paper in NeurIPS 2021

Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Probability (math.PR)

[49]  arXiv:2110.09069 [pdf, other]

Title: Diameter constrained Steiner tree and related problems

Authors: Prashanth Amireddy, Chetan Sai Digumarthi

Comments: 13 pages, 4 figures

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)

[50]  arXiv:2110.09102 [pdf, other]

Title: Data structure for node connectivity and cut queries

Authors: Zeev Nutov

Subjects: Data Structures and Algorithms (cs.DS)