archive
Every paper Pith has read. Search by title, abstract, or pith.
867 papers in cs.DS · page 6
-
n/log n approximation for MaxMin Independent Set Reconfiguration
On (In)approximability of MaxMin Independent Set Reconfiguration
-
Fat object graphs allow 2 to n to the 1-1/(d+1) algorithms for some hard problems
Small Independent Sets versus Small Separator in Geometric Intersection Graphs
-
Path-reporting oracles for vertex-labeled graphs reach stretch (4k-5)(1+ε)
Path-Reporting Distance Oracles for Vertex-Labeled Graphs
-
Buffer algorithm stays √3-competitive even with bad predictions
Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management
-
Flashback pairs first and last runs to decompose any string
Flashback: A Reversible Bilateral Run-Peeling Decomposition of Strings
-
The paper introduces spectral sparsification to edge bundling
Fast and Faithful Edge Bundling using Spectral Sparsification
-
Predicted edge order speeds SCC maintenance
Incremental Strongly Connected Components with Predictions
-
SIMD method converts integers to decimal strings 2-4x faster
Converting an Integer to a Decimal String in Under Two Nanoseconds
-
Max Cut needs n^{2^{o(k)}} f(k) time on multi-clique-width k graphs
Tight Bounds for some W[1]-hard Problems Parameterized by Multi-clique-width
-
Ulam k-center on permutations is FPT for k+d
Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
-
SimdQuickHeap doubles priority-queue speed with adjacent pivots and SIMD buckets
SimdQuickHeap: The QuickHeap Reconsidered
-
Exclusive scans finish in log p rounds with bounded operator uses
Two Efficient Message-passing Exclusive Scan Algorithms
-
Deadline interval separators proven NP-hard in temporal networks
Testing Robustness of Temporal Transportation Networks via Interval Separators
-
SCSS solved in 17^tw time given tree decomposition
New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph
-
Deleting k colors yields Lasserre exactness at level k+r
Grouped Color Deletion, Lasserre Exactness and Clique-Sum Locality for Rainbow Matching
-
Streaming sampler approximates graphlets in constant passes
An Efficient Streaming Algorithm for Approximating Graphlet Distributions
-
Dynamic (1+ε)-spanner for disk graphs uses polylog updates
A dynamic $(1+\varepsilon)$-spanner for disk intersection graphs
-
Bounded treewidth makes DPP inference polynomial
Fixed-parameter tractable inference for discrete probabilistic programs, via string diagram algebraisation
-
Coherent rollout oracles achieve O(sqrt(k)/eps) scaling
Coherent Rollout Oracles for Finite-Horizon Sequential Decision Problems
-
Greedy exceeds 1-1/e bound in random coverage models
On the Average-Case Performance of Greedy for Maximum Coverage
-
Strongly polynomial algorithm computes Arctic Auction equilibria
A Strongly Polynomial Algorithm for Arctic Auctions
-
Polynomial kernels for leaf-constrained diverse spanning trees
Polynomial Kernels for Spanning Tree with Diversity Requirements
-
Low-rank updates speed up feasible trust-region optimization
Scalable First-Order Interior Point Trust Region Algorithms for Linearly Constrained Optimization
-
MWIS on ordered graphs is quasi-polynomial or NP-hard except for one family of H
Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
-
Complexity map for vertex merges to chordal subclasses
Identification to Subclasses of Chordal Graphs
-
LSF structure hits optimal bounds for angular nearest neighbors
A Tour of Locality Sensitive Filtering on the Sphere
-
Polynomial-time algorithm for 2-anticlustering
Coloring for dispersion: A polynomial-time algorithm for cardinality-constrained 2-anticlustering
-
DP solves interval ordering in O(2^n poly(n)) oracle calls
Computational Complexity of the Interval Ordering Problem
-
Dynamic programming solves interval ordering in O(2^n) time
Computational Complexity of the Interval Ordering Problem
-
Subdivision to H-free graphs is polynomial only for star and bistar H
On the complexity of edge subdivision to $H$-free graphs
-
Minimum temporal spanners NP-hard even on happy graphs
Minimum Temporal Spanners in Happy Graphs
-
7-vertex tree detectable as induced minor in polynomial time
On Detecting $H$-Induced Minors for Small $H$
-
Pointer machines get near-optimal heaps for Dijkstra
Near-Optimal Heaps and Dijkstra on Pointer Machines
-
Fréchet distance in dD grids approximated in (n/ε)^{2-2/d} time
Near-tight Bounds for Computing the Fr\'echet Distance in d-Dimensional Grid Graphs and the Implications for {\lambda}-low Dense Curves
-
NP-hard to find shortest independent set reconfigurations on planar graphs
Finding Shortest Reconfiguration Sequences on Independent Set Polytopes
-
Compact LP matches optimal Nash welfare approximation
New Convex Programming Technique for Nash Social Welfare and Scheduling
-
Dynamic index reaches optimal space for repetitive texts
Dynamic Grammar-Compressed Self-Index in $\delta$-Optimal Space
-
Cycle detection in colored grids requires reading every cell
A Tight Lower Bound for Cycle Detection in Grid Graphs
-
Admissible objectives characterized for sum-type and max-type hierarchical clustering
Characterizations of Admissible Objective Functions for Hierarchical Clustering
-
Projection algorithm clusters Bernoulli mixtures via low-rank k-means
A Simple Algorithm for Clustering Discrete Distributions
-
PD kernels generalize Vertex Cover enumeration results
A more versatile model for enumerative kernelization: a case study for Vertex Cover
-
Interdiction witness is strict 2-approx minimizer of reweighted problem
A Note on Interdiction of Linear Minimization Problems
-
O(n) random numbers condition any matrix to O(n)
Well-Conditioned Oblivious Perturbations in Linear Space
-
Shortest paths in pseudodisk graphs run in near-linear time
Single-Source Shortest Paths and Almost Exact Diameter in Pseudodisk Graphs
-
Linear-time algorithm finds odd cycle through two vertices
A Linear-Time Algorithm for Finding an Odd Cycle Through Two Specified Vertices
-
Refined histogram approximates max subarray sum in sliding windows with O(ε^{-1} log² n)空间
Approximate Maintenance of Maximum Subarray Sum in the Sliding Window Model
-
Drone packing problem approximated to 4+ψ of optimum
Approximating Energy-Constrained Drone Delivery Packing Problem for Last-Mile Logistics
-
Convex hierarchy delivers first PTAS for entrywise low-rank approximation
Entrywise Low-Rank Approximation and Matrix $p \rightarrow q$ Norms via Global Correlation Rounding
-
Peer-to-peer grids obey transport lower bounds and monoid reduction rules
Mathematical Foundations for Peer-to-Peer Lattice Computation
-
Branchwidth approximates submodular width to within 3/2
Cuts and Gauges for Submodular Width