För en given graf G över n hörn, låt OPT G betecknar storleken på en optimal lösning i G av en viss minimering problem (t.ex. storleken på en minsta vertex omslag). En randomiserad algoritm kommer att kallas en α- approximation algoritm med ett additivt fel för denna minimering problem, om för någon given additiv fel parameter > 0 den beräknar ett värde OPT sådan att, med sannolikhet minst 2/3, den innehar att antagandet att den maximala graden eller genomsnittliga graden av G begränsas. I detta fall visar vi en minskning från lokala distribuerade approximationsalgoritmer för vertex cover problem till sublinjär approximation algoritmer för detta problem. Denna minskning kan enkelt ändras och tillämpas på andra optimeringsproblem som har lokala distribuerade approximationsalgoritmer, såsom dominerande set problem. Vi visar också att för minimalt vertex cover problem, frågekomplex av sådana approximation algoritmer måste växa åtminstone linjärt med den genomsnittliga graded av grafen. Denna nedre gräns rymmer för varje multiplikativ faktor α och liten konstant så länge somd = O(n/α). I synnerhet innebär detta att det för täta grafer inte är möjligt att utforma en algoritm vars komplexitet är o(n).
Vi bygger på Parnas-Ron minskning, föreslås i deras papper om approximering av storleken på en minsta vertex omslag (VC) REF.
Approximating the Minimum Vertex Cover in Sublinear Time and a Connection to Distributed Algorithms
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}