15 papers · ranked by Valyu relevance
Robin Eßmann, Tobias Nipkow, Simon Robillard, Ujkan Sulejmani
Approximation algorithms for NP-complete problems [Vaz03] are a rich area of research untouched by automated verification. We present the first formal verifications of five classical and one lesser known approximation algorithm. Three of these algorithms had been verified on paper by program verification experts [BM03…
Barış Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen + 1 more
'Roohani Sharma'] We generalize the monotone local search approach of Fomin, Gaspers, Lokshtanov and Saurabh [J.ACM 2019], by establishing a connection between parameterized approximation and exponentialtime approximation algorithms for monotone subset minimization problems. In a monotone subset minimization problem…
Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
Let X be a centrally symmetric convex body in R d . We say that an ellipsoid E is an α-ellipsoidal approximation for X if E/ α ⊆ X ⊆ E (where α ≥ 1). Calculating ellipsoidal approximations has applications to problems in machine learning and data science, including sampling and volume estimation (see, e.g., [CV15] and…
Jingyang Zhao, Zimo Sheng, Mingyu Xiao
TSP is a classic and extensively studied problem with numerous real-world applications in artificial intelligence and operations research. It is wellknown that TSP admits a constant approximation ratio on metric graphs but becomes NP-hard to approximate within any computable function f(n) on general graphs. This…
Antonios Antoniadis, Marek Eliáš, Adam Polak, Moritz Venzin
We initiate a systematic study of utilizing predictions to improve over approximation guarantees of classic algorithms, without increasing the running time. We propose a systematic method for a wide class of optimization problems that ask to select a feasible subset of input items of minimal (or maximal) total weight.…
Yuki Amano
The maximization for the independence systems defined on graphs is a generalization of combinatorial optimization problems such as the maximum b-matching, the unweighted MAX-SAT, the matchoid, and the maximum timed matching problems. In this paper, we consider the problem under the local oracle model to investigate the…
Michal Dory, Sebastian Förster, Yael Kirkpatrick, Yasamin Nazari + 2 more
'Virginia Vassilevska Williams' 'Tijn de Vos'] In this paper, we revisit the classic approximate All-Pairs Shortest Paths (APSP) problem in undirected graphs. For unweighted graphs, we provide an algorithm for 2-approximate APSP in ˜ ( 2.5− + () ) time, for any ∈ [0, 1]. This is ( 2.032) time, using known bounds for…
Yael Kirkpatrick, Liam Roditty, Richard Qi, Virginia Vassilevska Williams
Computing the diameter of a graph is a problem of great interest both in general algorithms research and specifically within fine-grained complexity, where it is a cornerstone hard problem. Recent work has achieved a full conditional lower bound tradeoff curve for both directed and undirected graphs. However, the best…
Benjamin Qi, Richard Qi, Xin-Yang Chen
Our main result is an O √n log 1 + 1 -time algorithm for touring disjoint disks. We also give an O min n , n 2 √ -time algorithm for touring disjoint two-dimensional convex fat bodies. Both of these results naturally generalize to larger dimensions; we obtain O n d−1 log2 1 + 1 2d−2 and O n 2d−2 -time algorithms for…
Evripidis Bampis, Bruno Escoffier, Michalis Xefteris
In the Traveling Salesperson Problem (TSP) we are given a list of locations and the distances between each pair of them. The goal is to find the shortest possible tour that visits each location exactly once and returns to the starting location. Inspired by the fact that general TSP cannot be approximated in polynomial…
Moritz Buchem, Katja Ettmayr, Hugo Kooki Kasuya Rosado, Andreas Wiese
'Andreas Wiese'] Clustering is a fundamental problem setting with applications in many different areas. For a given set of points in a metric space and an integer k, we seek to partition the given points into k clusters. For each computed cluster, one typically defines one point as the center of the cluster. A natural…
Peng Pan, Christian Sohler, Yi Xu
Single-linkage clustering is a fundamental method for data analysis. It proceeds iteratively by merging the two clusters with the smallest inter-cluster distance, starting from singleton clusters, until all points are combined into a single cluster. The distance between two clusters is defined as the minimum distance…
Yossi Azar, Danny Vainstein
We present a new multi-layer peeling technique to cluster points in a metric space. A well-known non-parametric objective is to embed the metric space into a simpler structured metric space such as a line (i.e., Linear Arrangement) or a binary tree (i.e., Hierarchical Clustering). Points which are close in the metric…
Alex Conway, Laxman Dhulipala, Martı́n Farach-Colton, Rob Johnson + 5 more
Graph-based nearest neighbor search methods have seen a surge of popularity in recent years, offering state-of-the-art performance across a wide variety of applications. Central to these methods is the task of constructing a sparse navigable search graph for a given dataset endowed with a distance function.…
Raffaele Marino
This chapter delves into the realm of computational complexity, exploring the world of challenging combinatorial problems and their ties with statistical physics. Our exploration starts by delving deep into the foundations of combinatorial challenges, emphasizing their nature. We will traverse the class P, which…