I detta dokument presenteras utformning, analys och genomförande av parallella och sekventiella I/O-effektiva algoritmer för set cover, som knyter samman arbetslinjen för parallell set cover och arbetslinjen för effektiva set cover algoritmer för stora, disk-bofasta instanser. Våra bidrag är tvåfaldiga: För det första utformar och analyserar vi en parallell cache-oblivious set-cover algoritm som erbjuder i huvudsak samma approximation garantier som standard girig algoritm, som har den optimala approximationen. Vår algoritm är den första effektiva externa-minne eller kakeobiös algoritm för när varken uppsättningarna eller elementen passar i minnet, vilket leder till I/O kostnad (cache komplexitet) motsvarande sortering i Cache Obligatoriska eller Parallell Cache Obligatoriska modeller. Algoritmen innebär också låga cache missar på parallella hierarkiska minnen (igen, motsvarande sortering). För det andra bygger vi på denna teori och konstruerar varianter av den teoretiska algoritmen optimerad för olika hårdvarukonfigurationer. Vi erbjuder experimentell utvärdering som visar betydande hastigheter över befintliga algoritmer utan att kompromissa med lösningens kvalitet.
Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. för I/O effektiva Set Täckande algoritmer REF.
Parallel and I/O efficient set covering algorithms
{'venue': "SPAA '12", 'journal': None, 'mag_field_of_study': ['Computer Science']}