Article

Free access

An O(log^*n) approximation algorithm for the asymmetric p-center problem

Author:

Sundar VishwanathanAuthors Info & Claims

SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms

Pages 1 - 5

Published: 28 January 1996 Publication History

PDF eReader

References

[1]

A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison- Wesley, Reading, MA, 1974.

Digital Library

Google Scholar

[2]

B. Bollobas, Combinatorics, Cambridge University Press, 1986.

Google Scholar

[3]

V. Chvatal, A greedy heuristic /or the set covering problem, Mathematics of Operations Research, 4 (1979), pp. 233-235.

Google Scholar

[4]

M. Dyer and A. Frieze, A simple heuristic/or the p-center problem, Oper. Res. Lett., 3 (1991), pp. 285- 288.

Google Scholar

[5]

M. R. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP- Completeness, Freeman, San Fransisco, 1979.

Digital Library

Google Scholar

[6]

D. S. Hochbaum and D. B. Shmoys, A best possible approximation algorithm/or the k-center problem, Math. Oper. Res. l0 (1985), pp. 180-184.

Google Scholar

[7]

W. L. Hsu and G. L. Nemhauser, Easy and hard bottleneck location problems, Discrete Appl. Math., 1 (1979), pp. 209-216.

Google Scholar

[8]

D. S. Johnson, Approximation Algorithms/or Combinatorial Problems, JCSS, 9 (1978), pp. 256-278.

Google Scholar

[9]

L. Lovasz, On the ratio of optimal integral and/factional covers, Discrete Mathematics, 13 (1975), pp. 383-390.

Google Scholar

[10]

C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, Proceedings of ACM STOG, pages 286-293, 1993.

Digital Library

Google Scholar

[11]

Rina Panigrahy, An O(log n) approximation algorithm for the asymmetric p-center problem, Submitted.

Google Scholar

[12]

D.B. Shmoys, Computing Near-Optimal Solutions to Combinatorial Optimization Problems, Manuscript.

Google Scholar

[13]

R. E. Tarjan, Data $tt'uctures and Network Algorithms, SIAM, Pittsburgh, PA, 1983.

Digital Library

Google Scholar

Cited By

View all

Goyal DJaiswal R(2023)Tight FPT approximation for constrained k-center and k-supplierTheoretical Computer Science10.1016/j.tcs.2022.11.001940:PA(190-208)Online publication date: 9-Jan-2023
https://dl.acm.org/doi/10.1016/j.tcs.2022.11.001
Li Gørtz IWirth A(2006)Asymmetry in k-center variantsTheoretical Computer Science10.1016/j.tcs.2006.05.009361:2(188-199)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.1016/j.tcs.2006.05.009

Index Terms

An O(log^*n) approximation algorithm for the asymmetric p-center problem
1. Mathematics of computing
  1. Discrete mathematics
  2. Mathematical analysis
    1. Functional analysis
      1. Approximation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
  2. Randomness, geometry and discrete structures

Recommendations

An Olog n/log log n-Approximation Algorithm for the Asymmetric Traveling Salesman Problem

We present a randomized O log n /log log n -approximation algorithm for the asymmetric traveling salesman problem ATSP. This provides the first asymptotic improvement over the long-standing Îï log n -approximation bound stemming from the work of ...
An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

We obtain a 1.5-approximation algorithm for the metric uncapacitated facility location (UFL) problem, which improves on the previously best known 1.52-approximation algorithm by Mahdian, Ye, and Zhang. Note that the approximability lower bound by Guha ...
Asymmetric k-center is log^* n-hard to approximate

In the ASYMMETRIC k-CENTER problem, the input is an integer k and a complete digraph over n points together with a distance function obeying the directed triangle inequality. The goal is to choose a set of k points to serve as centers and to assign all ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms

January 1996

586 pages

ISBN:0898713668

Chairman:
Éva Tardos

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 28 January 1996

Check for updates

Qualifiers

Article

Conference

SODA96

Sponsor:

SIGACT
SIAM

SODA96: Conference on Discrete Algorithms

January 28 - 30, 1996

Georgia, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
487
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)12

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Goyal DJaiswal R(2023)Tight FPT approximation for constrained k-center and k-supplierTheoretical Computer Science10.1016/j.tcs.2022.11.001940:PA(190-208)Online publication date: 9-Jan-2023
https://dl.acm.org/doi/10.1016/j.tcs.2022.11.001
Li Gørtz IWirth A(2006)Asymmetry in k-center variantsTheoretical Computer Science10.1016/j.tcs.2006.05.009361:2(188-199)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.1016/j.tcs.2006.05.009

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

An Olog n/log log n-Approximation Algorithm for the Asymmetric Traveling Salesman Problem

An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

Asymmetric k-center is log^* n-hard to approximate