I detta papper föreslår och studerar vi problemet med bana-driven inflytelserik affischtavla placering: med tanke på en uppsättning affischtavlor U (var och en med en plats och en kostnad), en databas över banor T och en budget L, hitta en uppsättning affischtavlor inom budgeten för att påverka det största antalet banor. En central utmaning är att identifiera och minska överlappningen av påverkan från olika affischtavlor till samma banor, samtidigt som budgetrestriktionerna beaktas. Vi visar att detta problem är NP-hård och presenterar en uppräkningsbaserad algoritm med (1 −1/e) approximationsförhållande. Den uppräkningsbaserade metoden är dock kostsam när den är stor. Genom att utnyttja den lokala egenskapen hos affischtavlors inflytande föreslår vi ett partitionerat ramverk PartSel. PartSel delar upp U i en uppsättning små kluster, beräknar de lokalt inflytelserika affischtavlorna för varje kluster, och slår samman dem för att generera den globala lösningen. Eftersom de lokala lösningarna kan erhållas mycket effektivare än den globala, kan PartSel minska beräkningskostnaden kraftigt; samtidigt uppnår den en icke-trivial approximation förhållande garanti. Sedan föreslår vi en LazyProbe-metod för att ytterligare beskära affischtavlor med lågt marginellt inflytande, samtidigt som man uppnår samma approximationsförhållande som PartSel. Experiment på verkliga dataset verifierar effektiviteten och effektiviteten i våra metoder.
Och arbetet i REF föreslår och studerar problemet med bana-driven inflytelserik affischtavla placering.
Trajectory-driven Influential Billboard Placement
{'venue': None, 'journal': 'Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining', 'mag_field_of_study': ['Computer Science']}