×

zbMATH — the first resource for mathematics

Provisioning a virtual private network: a network design problem for multicommodity flow. (English) Zbl 1323.68014
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). 389-398 (2001).

MSC:
68M10 Network design and communication in computer systems
05C21 Flows in graphs
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
68W25 Approximation algorithms
90B10 Deterministic network models in operations research
90B18 Communication networks in operations research
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.