상수 리코스를 갖는 기수 제약 하 비단조 부분모듈러 최대화의 타이트한 경계
Tight Bounds for Non-Monotone Submodular Maximization under a Cardinality Constraint with Constant Recourse
한국어 초록
우리는 원소가 하나씩 도착하고 알고리즘이 도착할 때마다 실행 가능한 집합을 보고해야 하는 상황에서, 기수 제약 하의 비음수 부분모듈러 함수 최대화를 연구한다. 알고리즘의 리코스는 한 번의 도착에서 보고된 집합에 대해 수행하는 삽입과 삭제의 최대 횟수이다. 모든 $\epsilon>0$에 대해, 우리는 리코스가 $O(\epsilon^{-2})$이고 보고된 집합이 매 시점마다 도착한 원소들로 이루어진 실행 가능 집합의 최댓값의 $1/4-\epsilon$배 이상의 기댓값을 갖는 알고리즘을 제시한다. 이 알고리즘은 함수를 다항 횟수만큼만, 그리고 도착한 원소들의 집합에 대해서만 평가한다. 또한 함수와 도착 순서를 미리 알고 있고 계산량에 제한이 없더라도, 상수 리코스를 갖는 어떤 알고리즘도 $1/4$을 넘는 비율을 달성할 수 없음을 보이며, $1/4$을 넘는 임의의 고정된 비율은 기수 예산의 양의 거듭제곱으로 증가하는 리코스를 요구함을 보인다. 따라서 $1/4$은 상수 리코스에서의 최적 극한 비율이다. 상수 리코스에서의 기존 최고 비율은 $3-2\sqrt2\approx0.172$였다. 우리의 알고리즘은 최대 2분의 1의 선택 확률을 할당하고, 원소가 도착함에 따라 모든 실행 가능 집합의 값을 이 확률로 추출한 무작위 집합의 기댓값의 배수로 제한하는 부등식을 유지하며, 보고되는 집합은 점진적인 교체를 통해 이 확률의 반올림 결과로 이동한다. 상한은 정점이 크기가 감소하는 그룹으로 도착하는 가중 유향 그래프를 사용한다.
원문 초록
We study the maximization of a nonnegative submodular function under a cardinality constraint when elements arrive one at a time and an algorithm must report a feasible set after every arrival. The recourse of an algorithm is the largest number of insertions and deletions that it makes to the reported set at a single arrival. For every $\epsilon>0$, we give an algorithm with recourse $O(\epsilon^{-2})$ whose reported set has, at every time, expected value at least $1/4-\epsilon$ times the largest value of a feasible set of arrived elements. The algorithm evaluates the function polynomially often, and only on sets of arrived elements. We also show that no algorithm with constant recourse achieves a ratio above $1/4$, even if it knows the function and the arrival order in advance and has unlimited computation, and that any fixed ratio above $1/4$ requires recourse that grows as a positive power of the cardinality budget. Thus $1/4$ is the optimal limiting ratio with constant recourse. The previous best ratio with constant recourse was $3-2\sqrt2\approx0.172$. Our algorithm assigns selection probabilities of at most one half and maintains, as elements arrive, an inequality bounding the value of every feasible set by a multiple of the expected value of a random set drawn with these probabilities; the reported set moves to a rounding of these probabilities through gradual replacements. The upper bound uses a weighted directed graph whose vertices arrive in groups of decreasing sizes.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.