컴퓨터 과학 (Computer Science) > 계산 복잡도 (Computational Complexity)

제목: 이차 다항식에 대한 Min-Max 최적화의 복잡성

PDF HTML 보기 (실험적)
초록: 우리는 하이퍼큐브 (hypercube) 상에서의 min-max 최적화 (min-max optimization)에 대한 근사 정지점 (approximate stationary points)을 계산하는 것이 이차 다항식 (quadratic polynomials)에 대해 PPAD-hard임을 증명합니다. 이는 다항식이 다중선형 (multilinear)이고, 각 변수가 최대 3개의 단항식 (monomials)에 나타나며, 근사 인자 (approximation factor)가 역다항식 (inverse polynomial)인 경우에도 성립합니다. 그 직접적인 결과로, 우리는 2인 팀 제로섬 폴리매트릭스 게임 (two-team zero-sum polymatrix games)에 대한 최초의 PPAD-hardness 결과를 얻었습니다.

현재 탐색 문맥:

서지 및 인용 도구

이 논사와 관련된 코드, 데이터 및 미디어

데모

추천 및 검색 도구

arXivLabs: 커뮤니티 협력자와 함께하는 실험적 프로젝트

arXivLabs는 협력자들이 우리 웹사이트에서 직접 새로운 arXiv 기능을 개발하고 공유할 수 있도록 하는 프레임워크입니다.

arXivLabs와 함께하는 개인 및 조직 모두 개방성, 커뮤니티, 탁월함, 그리고 사용자 데이터 프라이버시라는 우리의 가치를 수용하고 받아들였습니다. arXiv는 이러한 가치에 전념하며, 이를 준수하는 파트너와만 협력합니다.

arXiv 커뮤니티에 가치를 더할 프로젝트 아이디어가 있습니까? arXivLabs에 대해 더 알아보기.