AnO(log*n) Approximation Algorithm for the Asymmetricp-Center Problem

DOI10.1006/JAGM.1997.0921MaRDI QIDQ4216137zbMATH OpenOpenAlexFDO

Authors Rina Panigrahy, Sundar Vishwanathan

Publication date 2 December 1998

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1997.0921

zbMATH Keywords

asymmetric \(p\)-center problem

Mathematics Subject Classification ID

Recommendations

• scientific article; zbMATH DE number 871893
• scientific article; zbMATH DE number 1757943
• Approximating the asymmetric \(p\)-center problem in parameterized complete digraphs
• Asymmetric k -center is log ^* n -hard to approximate
• Asymmetric \(k\)-center is \(\log{^*}{n}\)-hard to approximate
• Generalized p-center problems: Complexity results and approximation algorithms
• scientific article; zbMATH DE number 1285629
• Un nuevo resultado sobre la complejidad del problema delP-centro
• A scalable exact algorithm for the vertex \(p\)-center problem
• Optimal algorithms for the \(\alpha\)-neighbor \(p\)-center problem

Cited in

(25)

• The weighted \(k\)-center problem in trees for fixed \(k\)
• Approximating the asymmetric \(p\)-center problem in parameterized complete digraphs
• Asymmetric \(k\)-center with minimum coverage
• Structural parameters, tight bounds, and approximation for \((k, r)\)-center
• Client assignment problems for latency minimization
• Discrete sensor placement problems in distribution networks
• Asymmetry in \(k\)-center variants
• Efficiently computing succinct trade-off curves
• A simple greedy approximation algorithm for the minimum connected k-center problem
• Insertion heuristics for central cycle problems
• Optimal lower bounds for universal and differentially private Steiner trees and TSPs
• Asymmetric k -center is log ^* n -hard to approximate
• Asymmetric \(k\)-center is \(\log{^*}{n}\)-hard to approximate
• The connected p-center problem on block graphs with forbidden vertices
• scientific article; zbMATH DE number 1757943 (Why is no real title available?)
• scientific article; zbMATH DE number 871893 (Why is no real title available?)
• Ant colony optimization for finding medians of weighted graphs
• Approximating Distance Measures for the Skyline
• The Euclidean k-supplier problem
• scientific article; zbMATH DE number 7278055 (Why is no real title available?)
• Asymmetry in \(k\)-center variants
• Min-Max-Min Optimization with Smooth and Strongly Convex Objectives
• Constant-factor greedy algorithms for the asymmetric \(p\)-center problem in parameterized complete digraphs
• The parameterized complexity of terminal monitoring set
• An improved two-stage approximation algorithm for the k-supplier problem with parameterized triangle inequality

This page was built for publication: AnO(log*n) Approximation Algorithm for the Asymmetricp-Center Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4216137)