Att hitta en maximal täckning av k-uppsättningar från en given samling (Max-k-Cover), att hitta ett minsta antal uppsättningar med en nödvändig täckning (Partial-Cover) är båda viktiga kombinatoriska optimeringsproblem. Olika problem från datautvinning, maskininlärning, analys av sociala nätverk, operativ forskning m.m. kan generaliseras som en uppsättning täckning problem. Standarden girig algoritm är effektiv som en in-minne algoritm. Men när vi står inför mycket storskaliga dataset eller i en online-miljö söker vi en ny algoritm som gör att bara en passerar genom hela datasetet. Tidigare en-pass algoritmer för Max-k-Cover problemet kan inte utvidgas till Partial-Cover problem och inte njuta av prefix-optimal egendom. I detta dokument föreslår vi en ny onepass streaming algoritm som producerar en prefix-optimal beställning av uppsättningar, som lätt kan användas för att lösa Max-k-Cover och Partial-Cover problem. Vår algoritm förbrukar rymden linjär till storleken av universum av element. Processtiden för en uppsättning är linjär till storleken på denna uppsättning. Vi visar också med hjälp av datorsimulering att approximationen av Max-k-Cover-problemet är omkring 0,3. Vi utför experiment på omfattande dataset för att jämföra vår algoritm med befintliga one-pass algoritmer på Max-k-Cover problemet, och med standard girig algoritm på Partial-Cover problemet. Vi visar vår algoritms effektivitet och kvalitet.
Yu och Yuan REF hävdade ett Õ(n) utrymme, engångs algoritm med en approximationsfaktor runt 0,3 baserat på hjälp av datorsimulering.
Set Coverage Problems in a One-Pass Data Stream.
{'venue': 'SDM', 'journal': None, 'mag_field_of_study': ['Computer Science']}