×

zbMATH — the first resource for mathematics

Non-approximability results for optimization problems on bounded degree instances. (English) Zbl 1323.90059
Proceedings of the thirty-third annual ACM symposium on theory of computing, STOC 2001. Hersonissos, Crete, Greece, July 6–8, 2001. New York, NY: ACM Press (ISBN 1-581-13349-9). 453-461 (2001).

MSC:
90C27 Combinatorial optimization
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
68W25 Approximation algorithms
90C35 Programming involving graphs or networks
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] [1]Y.Bartal,M.Charikar,andD.Raz.Approximating min-sumk-lusteringinmetrispaes.InProffdings ofthf33rdAnnualACMSymposiumonThforyof Computing,2001.
[2] [2]M.Charikar,C.Chekuri,T.Feder,andR.Motwani. Inrementallusteringanddynamiinformation retrieval.InProffdingsofthf29thAnnualACM SymposiumonThforyofComputing,pages626.635, 1997.
[3] [3]M.CharikarandS.Guha.Improvedombinatorial algorithmsforthefailityloationandk-median problems.InProffdingsofthf40thAnnual SymposiumonFoundationsofComputfrSifnf, pages378.388,1999.
[4] [4]M.Charikar,S.Guha,E.Tardos,andD.Shmoys.A onstantfatorapproximationalgorithmforthe k-medianproblem.InProffdingsofthf31stAnnual ACMSymposiumonThforyofComputing,pages 1.10,1999. · Zbl 1346.68253
[5] [5]F.Chudak.Improvedapproximationalgorithmsfor unapaitatedfailityloation.InE.A.B. R.E.BixbyandR.Z.REios-Merado,editors, Proffdingsofthf6thConffrfnfonIntfgfr ProgrammingandOptimization,volume1412of LfturfNotfsinComputfrSifnf,pages180.194. Springer,1998.
[6] [6]F.A.ChudakandD.Shmoys.Improved approximationalgorithmsfortheapaitatedfaility loationproblem.InProffdingsofthf10thAnnual ACM­SIAMSymposiumonDisrftfAlgorithms,pages S875.S876,1999.
[7] [7]G.CornuEejols,G.L.Nemhauser,andL.A.Wolsey. DisrftfLoationThfory,hapterTheunapaitated failityloationproblem.ohnWileyandSons,In., NewYork,1990.
[8] [8]S.R.Doddi,M..Marathe,S.S.Ravi,D.S.Taylor, andP.Widmayer.Approximationalgorithmsfor lusteringtominimizethesumofdiameters.In Proffdingsofthf7thSandinavianWorkshopon AlgorithmThfory,pages237.250,2000.
[9] [9]M.DyerandA.M.Frieze.Asimpleheuristiforthe p-enterproblem.OpfrationsRfsfarhLfttfrs, 3:285.288,1985.
[10] [10]S.GuhaandS.Khuller.Greedystrikesbak: Improvedfailityloationalgorithms.InProffdings ofthf9thAnnualACM­SIAMSymposiumonDisrftf Algorithms,pages649.657,1998.
[11] [11]N.Guttman-BekandR.Hassin.Approximation algorithmsformin-sump-lustering.DisrftfApplifd Mathfmatis,89:125.142,1998.
[12] [12]P.HansenandB.aumard.Clusteranalysisand mathematialprogramming.Mathfmatial Programming,pages191.215,1997.
[13] [13]D.S.HohbaumandD.B.Shmoys.Abestpossible approximationalgorithmforthek-enterproblem. MathfmatisofOpfrationsRfsfarh,10:180.184, 1985.
[14] [14]K.ainand.azirani.Primal-dualapproximation algorithmsformetrifailityloationandk-median problems.InProffdingsofthf40thAnnual SymposiumonFoundationsofComputfrSifnf, pages2.13,1999.toappearinournaloftheACM.
[15] [15]O.KarivandS.L.Hakimi.Analgorithmiapproah tonetworkloationproblems,partii:p-medians. SIAMJournalofApplifdMathfmatis,37:539.560, 1979.
[16] [16]M.Korupolu,C.G.Plaxton,andR.Rajaraman. Analysisofaloalsearhheuristiforfailityloation problems.InProffdingsofthf9thAnnual ACM­SIAMSymposiumonDisrftfAlgorithms,pages 1.10,1998.
[17] [17].-H.Linand.S.itter.Approximationalgorithms forgeometrimedianproblems.Information ProfssingLfttfrs,44:245.249,1992.
[18] [18]C.L.MonmaandS.Suri.Partitioningpointsand graphstominimizethemaximumorthesumof diameters.GraphThfory,Combinatorisand Appliations,pages880.912,1991.
[19] [19]D.B.Shmoys,ETardos,andK.I.Aardal. E.Approximationalgorithmsforfailityloation problems.InProffdingsofthf29thAnnualACM SymposiumonThforyofComputing,pages265.274, 1997.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.