Image de couverture de livre

On Approximability of Steiner Tree in $\ell_p$-metrics

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Fleischmann, Henry, Gavva, Surya Teja, S, Karthik C.
Format:	Preprint
Publié:	2023
Sujets:	Computational Complexity Computational Geometry Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Impossibility of Depth Reduction in Explainable Clustering
par: Deng, Chengyuan, et autres
Publié: (2023)

Inapproximability of Maximum Diameter Clustering for Few Clusters
par: Fleischmann, Henry, et autres
Publié: (2023)

On Approximability of $\ell_2^2$ Min-Sum Clustering
par: S., Karthik C., et autres
Publié: (2024)

On connections between k-coloring and Euclidean k-means
par: Aman, Enver, et autres
Publié: (2024)

Hardness of Median and Center in the Ulam Metric
par: Fischer, Nick, et autres
Publié: (2025)

The Power of Recursive Embeddings for $\ell_p$ Metrics
par: Krauthgamer, Robert, et autres
Publié: (2025)

Near-Optimal Bounds for Parameterized Euclidean k-means
par: Cohen-Addad, Vincent, et autres
Publié: (2026)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
par: Cohen-Addad, Vincent, et autres
Publié: (2026)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
par: Makarychev, Yury, et autres
Publié: (2024)

Fast Nearest Neighbor Search for $\ell_p$ Metrics
par: Krauthgamer, Robert, et autres
Publié: (2026)

Improved Hardness of Approximation for Geometric Bin Packing
par: Ray, Arka, et autres
Publié: (2023)

Approximate Algorithms for Chamfer Distance Under Translation
par: Halevi, Gil, et autres
Publié: (2026)

On Approximating the Dynamic and Discrete Network Flow Problem
par: Manna, Bubai, et autres
Publié: (2024)

Fine-Grained Complexity of Continuous Euclidean k-Center
par: Blank, Lotte, et autres
Publié: (2026)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
par: Kisfaludi-Bak, Sándor, et autres
Publié: (2020)

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
par: Bringmann, Karl, et autres
Publié: (2024)

Efficient Algorithms for Partitioning Circulant Graphs with Optimal Spectral Approximation
par: Gavva, Surya Teja, et autres
Publié: (2025)

Structural Parameters for Steiner Orientation
par: Hanaka, Tesshu, et autres
Publié: (2025)

Universal Solvability for Robot Motion Planning on Graphs
par: Dhar, Anubhav, et autres
Publié: (2025)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
par: Khanna, Sanjeev, et autres
Publié: (2025)

Recognizing 2-Layer and Outer $k$-Planar Graphs
par: Kobayashi, Yasuaki, et autres
Publié: (2024)

Subcoloring of (Unit) Disk Graphs
par: Marin, Malory, et autres
Publié: (2025)

Beyond Bits: An Introduction to Computation over the Reals
par: Miltzow, Tillmann
Publié: (2026)

Fast and simple multiplication of bounded twin-width matrices
par: Kozma, László, et autres
Publié: (2026)

Computational Complexities of Folding
par: Eppstein, David
Publié: (2024)

Making Quickhull More Like Quicksort: A Simple Randomized Output-Sensitive Convex Hull Algorithm
par: Goodrich, Michael T., et autres
Publié: (2024)

Ideal Membership Problem for Boolean Minority and Dual Discriminator
par: Bharathi, Arpitha P., et autres
Publié: (2024)

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
par: Kisfaludi-Bak, Sándor, et autres
Publié: (2026)

Time complexity of the Analyst's Traveling Salesman algorithm
par: Ramirez, Anthony, et autres
Publié: (2022)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
par: S., Karthik C., et autres
Publié: (2024)

Self-referential instances of the dominating set problem are irreducible
par: Zhou, Guangyan
Publié: (2026)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
par: Guruswami, Venkatesan, et autres
Publié: (2024)

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
par: Bhore, Sujoy, et autres
Publié: (2024)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
par: S., Karthik C., et autres
Publié: (2023)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
par: Guruswami, Venkatesan, et autres
Publié: (2023)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
par: Dvořák, Pavel, et autres
Publié: (2017)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
par: Esmer, Barış Can, et autres
Publié: (2022)

Maximization of Approximately Submodular Functions
par: Horel, Thibaut, et autres
Publié: (2024)

Downward self-reducibility in the total function polynomial hierarchy
par: Gajulapalli, Karthik, et autres
Publié: (2025)

Online Orthogonal Vectors Revisited
par: Gajulapalli, Karthik, et autres
Publié: (2026)