#approximation algorithms
29 papers match
Approximate sampling from decoded quantum interferometry via Markov chain Monte Carlo methods
Elies Gil-Fuster, Matan Ninio, Lennart Bittel +4
The paper investigates whether classical Markov chain Monte Carlo methods, especially block‑Gibbs sampling, can reproduce the optimization performance of decoded quantum interferom…
Optimal PSPACE-hardness of Approximating -CSP Reconfiguration
Shuichi Hirahara, Naoto Ohsaka
The paper proves that approximating the Maxmin q‑CSP Reconfiguration problem within a factor of 1/2^{q‑1}+ε is PSPACE‑hard for any q≥2, and shows that achieving a (1/2^{q‑1}‑ε)‑app…
Safe Quotes for Retroactive Liquidity Pools
Peter Bro Miltersen
The paper examines how to compute safe price quotes for retroactive liquidity pools used in cross‑chain swaps, proves that approximating the optimal safe quote is NP‑hard, and offe…
Tight UGC Thresholds for Geometric Stabbing Problems
Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray
The paper proves tight hardness thresholds under the Unique Games Conjecture for several geometric stabbing problems by linking integrality‑gap instances of covering LPs to matchin…
Approximate Dual Separation for the Cluster LP: a 1.387 approximation for Correlation Clustering
David GarcÃa-Soriano, Antoine Schohn
The paper presents a (1.3865+ε)-approximation algorithm for correlation clustering on complete graphs by introducing an efficient approximate dual separation oracle for the cluster…
Linear time approximation of the TV distance between product distributions
Konrad Anand, Alistair Benford, Heng Guo
The paper proposes a linear‑time algorithm that approximates the total variation distance between two product distributions.
Designing Pairwise-Stable Agent Seating Arrangements
Frederik Glitzner
The paper studies how a central planner can design the underlying graph on which agents with ordinal preferences are seated, aiming to achieve pairwise‑stable arrangements while ba…
A Linear Bound on the Rainbow Cycle Number and Approximate EFX
Varun Sivashankar
The paper proves that the rainbow cycle number grows linearly with the dimension, which yields a partial (1‑ε)-EFX allocation for any fair‑division instance with only O(√(n/ε)) una…
Length-Constrained Network Design in Planar Digraphs
Chandra Chekuri, Rhea Jain
The paper develops polylogarithmic bicriteria approximation algorithms for length-constrained versions of Directed Steiner Tree and Directed Steiner Forest in planar directed graph…
The Code Distortion Problem
Huck Bennett, Matthew Fox, Bryant Morrell
The paper defines a code distortion measure between linear error‑correcting codes and studies the computational problem of finding a minimum‑distortion mapping, proving NP‑hardness…
Spectral Dual Fitting for -Means
Aditya Anand, Moses Charikar, Vincent Cohen-Addad +5
The paper introduces a new dual‑fitting algorithm that achieves better approximation ratios for the k‑means clustering problem in both Euclidean and general metric spaces, using a…
Semitotal domination in unit disk graphs
Mingjun Liu, Weiping Shang
The paper studies the Minimum Semitotal Domination problem on unit disk graphs, proving it is NP‑complete and presenting a linear‑time 5‑approximation algorithm based on BFS layers…
The Complexity of Distributed Minimum Weight Cycle Approximation
Yi-Jun Chang, Yanyu Chen, Dipan Dey +4
The paper presents randomized approximation algorithms for the Minimum Weight Cycle problem in the CONGEST model, achieving a trade‑off between approximation ratio and round comple…
A Correlation-Gap Bound for Nonlinear Gaussian PCA
Minbo Gao, Zhengfeng Ji, Chenghua Liu
The paper shows that for Gaussian data, the Karhunen–Loève (KL) basis is within a factor 1 + O(1/√d) of the optimal basis when a fixed number of coordinates are adaptively retained…
Algorithmic Information Design for Searchers with Uncertain Alternatives
Zhicheng Du, Hu Fu, Ying Qin +1
The paper studies how a seller can optimally reveal information to a consumer who faces uncertain alternatives and decides whether to keep searching, providing a verification metho…
Exploiting Graph Structure for Near-Optimal Broadcasting
Rudranarayan Kar, Praneet Kumar Patra, Diya Roy +1
The paper studies faster approximation algorithms for the graph broadcasting problem, providing additive‑approximation schemes and improved exact algorithms while also showing para…
-Approximation of Fréchet Distance in Strongly Subquadratic Time
Lenny Liu, Jihan Wang
The paper presents randomized algorithms that compute a (5+ε)-approximation of both continuous and discrete Fréchet distances between polygonal curves in subquadratic time, improvi…
Approximating (Weighted) Chromatic Correlation Clustering via Cluster LP
Fateme Abbasi, Hyung-Chan An, JarosÅaw Byrka +2
The paper presents a (2+ε)-approximation algorithm for Chromatic Correlation Clustering and its weighted variant by extending the cluster linear programming formulation to handle c…
Rank-Independent Spectral Hypergraph Sparsification via Global-Dictionary Chaining
Chenghua Liu, Yuxin Zhang
The paper proposes a method to create a spectral ε‑sparsifier for any weighted hypergraph using only O(n log n / ε²) hyperedges, eliminating the dependence on the hypergraph’s rank…
Adaptive Sampling for Minimum-Norm -Clustering
Haripriya Pulyassary, Chaitanya Swamy
The paper introduces an adaptive‑sampling algorithm that provides a bicriteria constant‑factor approximation for general minimum‑norm k‑clustering, and an O(log k) approximation fo…
Approximation Algorithms for Norm-Budgeted Packing Problems
David Aleman Espinosa, Sharat Ibrahimpur, Chaitanya Swamy
The paper introduces norm-budgeted packing problems, where packing constraints are expressed via monotone symmetric norms, and provides constant-factor approximation algorithms and…
Hierarchical -Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs
MichaÅ Szyfelbein, Dariusz Dereniowski
The paper studies hierarchical clustering where the recursion stops once clusters belong to a specified graph class (trees or bounded‑diameter graphs), providing poly‑time logarith…
Graph Partitioning with Demands: Generalized Conductance and its Applications
MichaÅ Szyfelbein, Dariusz Dereniowski
The paper studies graph partitioning problems with vertex demand functions and introduces the generalized conductance measure, providing O(log n) approximation algorithms via reduc…
A Better-than- Approximation Algorithm for Nash Social Welfare under Additive Valuations
Vignesh Viswanathan
The paper proposes an algorithm that achieves a (e^{1/e} − c) approximation, improving on the previous e^{1/e} bound, for maximizing Nash social welfare with additive valuations.
One search, two signals: results blend meaning (embedding similarity, so papers that never use your words still surface) with keyword matches on titles, abstracts and summaries. Free, no sign-in needed.