Highway Dimension: a Metric View
이 논문은 그리드 그래프와 유클리드 평면과 같은 자연스러운 거리 공간도 포함하도록 고속도로 차원 (highway dimension) 의 정의를 근사 최단 경로에 기반하여 완화하고, 이를 바탕으로 TSP 에 대한 PTAS 를 제시하며 패딩 분해 및 트리 커버 등 다양한 메트릭 툴킷을 구축하여 폭넓은 응용 가능성을 제시합니다.
💻 Category
cs.DS
88 편의 논문
On the Inversion Modulo a Power of an Integer
이 논문은 소수 거듭제곱에 대한 역수 계산 알고리즘을 일반 정수 거듭제곱으로 확장하여 컴퓨터 아키텍처의 연산 특성을 활용한 효율적인 알고리즘을 제안하고, 소수 거듭제곱에 대한 기존 역수 계산 방법도 일반 정수 거듭제곱으로 일반화한 결과를 담고 있습니다.
Even Faster Kernel Matrix Linear Algebra via Density Estimation
이 논문은 커널 밀도 추정을 활용하여 커널 행렬의 행렬-벡터 곱, 행렬-행렬 곱, 스펙트럼 노름, 그리고 모든 요소의 합을 계산하는 기존 알고리즘의 실행 시간을 개선하고, 특히 데이터 점 수 과 오차 에 대한 의존성을 줄였으며 관련 문제에 대한 하한을 제시했습니다.
Deterministic Coreset for Lp Subspace
이 논문은 및 임의의 에 대해 인자를 제거하고 최적 크기를 갖는 최초의 결정론적 서브스페이스 임베딩 코어셋을 구성하는 반복 알고리즘을 제시합니다.
Submodular Maximization over a Matroid -Intersection: Multiplicative Improvement over Greedy
이 논문은 개의 매트로이드 교집합 제약 하에서 단조 서브모듈러 함수 최대화 문제에 대해 그리디 알고리즘의 -근사율을 개선한 최초의 배수적 향상 () 을 제공하는 새로운 하이브리드 알고리즘을 제안합니다.
Skirting Additive Error Barriers for Private Turnstile Streams
이 논문은 프라이버시 보호 하의 턴스타일 스트림에서 기존에 필수적이었던 다항식 크기의 가법 오차 한계를, 가법 및 승법 오차를 모두 허용하는 알고리즘을 통해 다항식 로그 크기로 줄일 수 있음을 보여줍니다.
Bounding the Average Move Structure Query for Faster and Smaller RLBWT Permutations
이 논문은 긴 구간을 길이로 제한하는 단순한 분할 방식을 통해 RLBWT(런 길이 인코딩된 BWT) 의 평균 이동 구조 쿼리 시간을 최적화하고, 구성 시간을 단축하며, LF 매핑 및 접미사 배열 열거와 같은 알고리즘의 공간 효율성을 크게 개선하는 방법론과 그 유효성을 실험을 통해 입증합니다.
DRESS: A Continuous Framework for Structural Graph Refinement
이 논문은 그래프 구조의 유사성을 반복적으로 정제하여 동형 불변의 고유한 지문 (DRESS) 을 생성하는 결정론적 프레임워크를 제안하고, 이를 다양한 변형 (Motif-DRESS, -DRESS 등) 으로 확장하여 2-WL 테스트보다 높은 표현력을 낮은 비용으로 달성함을 보여줍니다.