Cover Image

Faster algorithms for k-Orthogonal Vectors in low dimension

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dürr, Anita, Kipouridis, Evangelos, Węgrzycki, Karol
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
by: Bringmann, Karl, et al.
Published: (2026)

Dynamic data structures for twin-ordered matrices
by: Bosek, Bartłomiej, et al.
Published: (2026)

A Faster Algorithm for Constrained Correlation Clustering
by: Fischer, Nick, et al.
Published: (2025)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
by: Georgiadis, Loukas, et al.
Published: (2026)

Space-Efficient Algorithm for Integer Programming with Few Constraints
by: Rohwedder, Lars, et al.
Published: (2024)

Fitting Tree Metrics and Ultrametrics in Data Streams
by: Carmel, Amir, et al.
Published: (2025)

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
by: Bringmann, Karl, et al.
Published: (2024)

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
by: Eisenbrand, Friedrich, et al.
Published: (2024)

Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach
by: Joux, Antoine, et al.
Published: (2024)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
by: Rohwedder, Lars, et al.
Published: (2024)

Improved Bounds for Rectangular Monotone Min-Plus Product and Applications
by: Dürr, Anita
Published: (2022)

Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM
by: Randolph, Tim, et al.
Published: (2024)

Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime
by: Aggarwal, Divesh, et al.
Published: (2024)

Faster ED-String Matching with $k$ Mismatches
by: Gawrychowski, Paweł, et al.
Published: (2025)

A Broader View on Clustering under Cluster-Aware Norm Objectives
by: Herold, Martin G., et al.
Published: (2025)

Clustering to Minimize Cluster-Aware Norm Objectives
by: Herold, Martin G., et al.
Published: (2024)

Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems
by: Alman, Josh, et al.
Published: (2024)

Beating Meet-in-the-Middle for Subset Balancing Problems
by: Randolph, Tim, et al.
Published: (2025)

On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
by: Bhore, Sujoy, et al.
Published: (2025)

Hitting Meets Packing: How Hard Can it Be?
by: Focke, Jacob, et al.
Published: (2024)

Faster Combinatorial k-Clique Algorithms
by: Abboud, Amir, et al.
Published: (2024)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Kisfaludi-Bak, Sándor, et al.
Published: (2020)

Faster parameterized algorithm for 3-Hitting Set
by: Tsur, Dekel
Published: (2025)

Faster two-dimensional pattern matching with $k$ mismatches
by: Ellert, Jonas, et al.
Published: (2024)

Faster algorithms for packing forests in graphs and related problems
by: Arkhipov, Pavel, et al.
Published: (2024)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
by: Kadria, Avi, et al.
Published: (2025)

Faster Approximation Algorithms for k-Center via Data Reduction
by: Filtser, Arnold, et al.
Published: (2025)

Faster exact learning of k-term DNFs with membership and equivalence queries
by: Alman, Josh, et al.
Published: (2025)

Parameterized algorithms for $k$-Inversion
by: Antony, Dhanyamol, et al.
Published: (2026)

Insights into $(k,ρ)$-shortcutting algorithms
by: Leonhardt, Alexander, et al.
Published: (2024)

Online Orthogonal Vectors Revisited
by: Gajulapalli, Karthik, et al.
Published: (2026)

A Faster $k$-means++ Algorithm
by: Liang, Jiehao, et al.
Published: (2022)

Faster and Simpler Greedy Algorithm for $k$-Median and $k$-Means
by: la Tour, Max Dupré, et al.
Published: (2024)

Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than $3^k$
by: Liu, Yuxi, et al.
Published: (2024)

Faster Approximation Scheme for Euclidean $k$-TSP
by: van Wijland, Ernest, et al.
Published: (2023)

An $2\sqrt{k}$-approximation algorithm for minimum power $k$ edge disjoint $st$ -paths
by: Nutov, Zeev
Published: (2022)

Round-efficient Fully-scalable MPC algorithms for k-Means
by: Jiang, Shaofeng H. -C., et al.
Published: (2026)

Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum
by: Alman, Josh, et al.
Published: (2025)

An Optimal $3$-Fault-Tolerant Connectivity Oracle
by: Kosinas, Evangelos
Published: (2025)

Scenario-Based Robust Optimization of Tree Structures
by: Angelopoulos, Spyros, et al.
Published: (2024)