Det anses allmänt att submodulära funktioner-och den mer allmänna klassen av γ-svag submodulära funktioner-kan endast optimeras under icke-negativitet antagande f (S) ≥ 0. I detta dokument visar vi att när funktionen uttrycks som skillnaden f = g − c, där g är monoton, icke-negativ, och γ-svag submodulär och c är icke-negativ modulär, då starka approximationsgarantier kan erhållas. Vi presenterar en algoritm för maximering g − c under en k-kardinalitet begränsning som producerar en slumpmässig genomförbar uppsättning S sådan att, vars körtid är O( n log 2 1 ), dvs oberoende av k. Vi utökar dessa resultat till den okonstruerade inställning genom att beskriva en algoritm med samma approximativa garantier och snabbare O ( n log 1 ) körtid. De huvudsakliga tekniker som ligger till grund för våra algoritmer är tvåfaldiga: användningen av ett surrogatmål som varierar den relativa betydelsen mellan g och c genom algoritmen, och en geometrisk svepning över möjliga γ-värden. Våra algoritmiska garantier kompletteras med ett hårdhetsresultat som visar att ingen polynom-tid algoritm som når g genom ett värde oracle kan göra bättre. Vi demonstrerar empiriskt framgången av våra algoritmer genom att tillämpa dem till experimentell design på Boston Housing dataset och riktad vertex omslag på e-post EU-datasetet.
REF studerade SG för att maximera uppsättning funktioner skrivna som f = g − c, där g är monoton svagt submodulär och c är icke-negativ modulär; medan f kan vara icke-monoton, de anser inte hela klassen av icke-monoton submodulära funktioner och deras approximation garanti kan inte skrivas med en multiplikativ faktor till skillnad från våra resultat.
Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}