한국어 초록
후보가 균일하게 무작위인 순서로 도착하고 총 가치를 최대화하도록 최대 $k$명의 후보를 선택하는 것이 목표인 다중 선택 비서 문제를 연구한다. 어떤 후보도 도착하기 전에 개별 후보 가치의 예측이 주어지는 설정을 고려한다. Fujii와 Yoshida의 Learned Kleinberg 알고리즘은 경쟁 손실 $O(\min\{\log k/\sqrt{k},\eps\})$을 달성하며, 여기서 $k$는 선택 용량이고 $\eps$는 최대 승법 예측 오차이다. 우리는 임계값을 재조정한 동일한 전환 알고리즘에 대한 더 정밀한 분석을 통해 로그 인자를 제거한다. 그 결과로 얻은 경쟁비는 최소 $\max\{0,1-\min\{32/\sqrt{k},4\eps\}\}$이다. 특히 정확한 예측($\eps=0$)은 모든 도착 순서에서 오프라인 최적값을 달성한다.
원문 초록
We study the multiple-choice secretary problem, in which candidates arrive in uniformly random order and the goal is to select at most $k$ candidates to maximize their total value. We consider a setting where predictions of individual candidate values are available before any candidate arrives. Fujii and Yoshida's Learned Kleinberg algorithm achieves competitive loss $O(\min\{\log k/\sqrt{k},\eps\})$, where $k$ is the selection capacity and $\eps$ is the maximum multiplicative prediction error. We remove the logarithmic factor through a sharper analysis of the same switching algorithm with a retuned threshold. The resulting competitive ratio is at least $\max\{0,1-\min\{32/\sqrt{k},4\eps\}\}$. In particular, exact predictions ($\eps=0$) achieve the offline optimum on every arrival order.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2611.14651v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.