arXiv:2611.20257v1 cs.DS

상수 리코스를 갖는 기수 제약 하 비단조 부분모듈러 최대화의 타이트한 경계

Tight Bounds for Non-Monotone Submodular Maximization under a Cardinality Constraint with Constant Recourse

Vaneet Aggarwal

제출 2026-11-15

한국어 초록

우리는 원소가 하나씩 도착하고 알고리즘이 도착할 때마다 실행 가능한 집합을 보고해야 하는 상황에서, 기수 제약 하의 비음수 부분모듈러 함수 최대화를 연구한다. 알고리즘의 리코스는 한 번의 도착에서 보고된 집합에 대해 수행하는 삽입과 삭제의 최대 횟수이다. 모든 $\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 원문에서 확인하세요.

  1. arXiv:2611.20257v1

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.