Guess free maximization of submodular and linear sums

Moran Feldman

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים


We consider the problem of maximizing the sum of a monotone submodular function and a linear function subject to a general solvable polytope constraint. Recently, Sviridenko et al. [16] described an algorithm for this problem whose approximation guarantee is optimal in some intuitive and formal senses. Unfortunately, this algorithm involves a guessing step which makes it less clean and significantly affects its time complexity. In this work we describe a clean alternative algorithm that uses a novel weighting technique in order to avoid the problematic guessing step while keeping the same approximation guarantee as the algorithm of [16].

שפה מקוריתאנגלית
כותר פרסום המארחAlgorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings
עורכיםZachary Friggstad, Mohammad R. Salavatipour, Jörg-Rüdiger Sack
מוציא לאורSpringer Verlag
מספר עמודים15
מסת"ב (מודפס)9783030247652
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2019
אירוע16th International Symposium on Algorithms and Data Structures, WADS 2019 - Edmonton, קנדה
משך הזמן: 5 אוג׳ 20197 אוג׳ 2019

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך11646 LNCS
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349


כנס16th International Symposium on Algorithms and Data Structures, WADS 2019

הערה ביבליוגרפית

Publisher Copyright:
© Springer Nature Switzerland AG 2019.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Guess free maximization of submodular and linear sums'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי