Abstract Facility Dispersion Problem, som ursprungligen studerades i Operations Research, har nyligen funnit viktiga nya tillämpningar i Resultat Diversifiering i informationsvetenskap. Detta optimeringsproblem består i att välja ut en liten uppsättning p-objekt av en stor uppsättning kandidater för att maximera en viss objektiv funktion. Funktionen uttrycker begreppet spridning av en uppsättning utvalda objekt i form av ett parvis avståndsmått mellan objekt. I de flesta kända formuleringar problemet är NP-hård, men det finns 2- approximation algoritmer för vissa fall om avståndet uppfyller triangeln ojämlikhet. Vi presenterar generella 2/α approximationsgarantier för Facility Dispersion Problem i dess två vanligaste varianter: Max Sum och Max Min, när den underliggande olikhet åtgärd uppfyller parameteriserad triangel ojämlikhet med parameter α. Resultaten gäller både avslappnade och starkare varianter av triangeln ojämlikhet. Vi demonstrerar också potentiella tillämpningar av våra resultat i resultatdiversifieringsproblem, inklusive webbsökning eller enhetssammanfattning i semantiska kunskapsgrafer, samt i praktiska beräkningar av finita datamängder. Nyckelord och fraser: mångfald, maxsumma och max min anläggning spridning, approximation algoritmer, parameteriserad triangel ojämlikhet.
Studien av påverkan av egenskaperna hos den parvisa olikhet funktion på approximationsfaktorn i Facility Dispersion Problem studeras nyligen i REF.
Approximation Guarantees for Max Sum and Max Min Facility Dispersion with Parameterised Triangle Inequality and Applications in Result Diversification
{'venue': None, 'journal': 'Mathematica Applicanda', 'mag_field_of_study': ['Mathematics']}