Problemen med kantdominerande set (EDS) och kantskydd (EC) är klassiska grafer som täcker problem där man söker en minimikostnadsinsamling av kanter som täcker kanterna respektive hörnen på en graf. Vi anser att den generaliserade partiella omslagsversionen av dessa problem, där underlåtenhet att täcka en kant, i EDS-fallet, eller vertex, i EG-fallet, leder till en påföljd. Målet är att begränsa det totala sanktionsbelopp som man har rätt att betala för att finna en minimikostnadstäckning som respekterar detta. Vi ges en 8/3- approximation för generaliserade partiella EDS Detta resultat matchar den mest kända garantin för {0, 1}-EDS-problemet, en specialisering i endast som en specificerad uppsättning av kanter behöver täckas. Dessutom motsvarar 8/3 integrality gapet i den naturliga formuleringen av {0, 1}-EDS-problemet. Våra tekniker kan också användas för att härleda ett approximationssystem för det generaliserade partiella kantskyddet problem, vilket är NP-hård även om standard kantskydd problem är i P.
Denna 8/3- approximation utvidgades till den prissamlande EDS-problemet av Parekh REF.
Approximation algorithms for partially covering with edges
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}