Vi ger tid lägre gränser för distribuerad approximation av minsta vertex cover (MVC) och relaterade problem som minimum dominerande set (MDS). I k-kommunikationsrundor kan MVC och MDS endast approximeras med hjälp av faktorer (n c/k där n och  påvisar antalet noder och den största graden i grafen. Antalet rundor som krävs för att uppnå ett konstant eller till och med endast ett polylogaritmiskt approximationsförhållande är minst. ( - log n/ log log n) och - (log  på/ log log log.). Genom en enkel minskning, de senare nedre gränserna håller också för konstruktion av maximal matchningar och maximal oberoende uppsättningar.
Dessutom krävs rundor för att uppnå ett polylogaritmiskt approximationsförhållande för minimalt dominerande set minst max {.} ( REF ) för att uppnå en polylogaritmisk approximationsgrad.
What cannot be computed locally!
{'venue': "PODC '04", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}