I detta dokument anser vi att det minsta oviktade Vertex Cover problemet med hård kapacitet begränsningar (VCHC) på multigrafer och hypergrafer. Med tanke på en graf, målet med VCHC är att hitta en minsta multiset av hörn som täcker alla kanter, under de begränsningar som varje vertex bara kan täcka ett begränsat antal incidenter kanter, och antalet tillgängliga kopior av varje vertex begränsas. Detta problem generaliserar det klassiska oviktade vertex cover problemet. Här begränsar vi vår uppmärksamhet till oviktade instanser, eftersom den viktade versionen av VCHC är lika svår som det set cover problemet, som visas av Chuzhoy och Naor (FOCS 2002). Vi får förbättrade approximationsalgoritmer för VCHC på multigrafer och hypergrafer. Detta problem har först undersökts av Saha och Khuller (ICAP 2012). De föreslog en 38-uppskattning för multigrafer, och en max {6f, 65}-uppskattning för hypergrafer, där f är storleken på den största hyperkanten. I det här dokumentet förbättrar vi dessa approximationskvoter avsevärt till 1 + 2/ 3 < 2.155 respektive 2f. När det gäller multigrafer, vår approximation förhållande är mycket nära den långvariga gränsen av 2 för den klassiska vertex cover problem. Våra algoritmer består av en tvåstegsprocess, var och en baserad på avrundning ett lämpligt linjärt program. När det gäller multigrafer är analysen i det andra steget särskilt beroende av att man identifierar en matchningsstruktur inom alla extrema punktlösningar. Dessutom anser vi att det partiella VCHC-problemet där man bara behöver täcka alla utom kanter. Vi föreslår en generell minskning från partiell VCHC på f-hypergrafer till VCHC på (f + 1)-hypergrafer, med en liten förlust i approximationsfaktorn. I synnerhet presenterar vi en (2f + 2) (1 + ) - approximation algoritm för partiell VCHC på f -hypergraphs.
För partiell VC-HC, som syftar till att täcka ett visst antal kanter, Cheung et al REF tillhandahöll en (1+ ) (2f +2)-approximation, baserad på en minskning till (f + 1)-hypergrafer och deras 2f - approximation för VC-HC presenteras i samma arbete.
Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}