Concurrent Deterministic Skiplist and Other Data Structures
이 논문은 많은 코어 NUMA 노드 환경에서 동시성 결정적 스킵리스트, 락 프리 큐, 멀티 리더/라이터 해시 테이블의 설계와 성능을 분석하고, 메모리 관리 전략과 계층적 데이터 구조 활용을 통해 메모리 지연을 줄이는 방법을 제안합니다.
💻 Category
cs.DS
87 편의 논문
Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
이 논문은 모든 고정된 그래프 H 에 대해 P5-자유 그래프에서 최대 부분 리스트 H-채색 문제가 다항 시간에 해결 가능함을 증명하여, Agrawal 등 (SODA 2024) 의 열린 문제를 해결하고 Chudnovsky 등 (SIDMA 2021) 의 기존 알고리즘을 다항 시간 알고리즘으로 개선했습니다.
Differentially Private and Scalable Estimation of the Network Principal Component
이 논문은 실제 그래프의 민감도 특성을 활용하여 제안 - 테스트 - 공개 (PTR) 프레임워크를 기반으로 사생활 보호를 보장하면서도 기존 방법 대비 180 배 빠른 실행 속도와 높은 정확도로 네트워크 주성분 및 밀집 서브그래프를 추정하는 확장 가능한 차분 프라이버시 알고리즘을 제안합니다.
Bounds for the Permutation Flowshop Scheduling Problem: New Framework and Theoretical Insights
본 논문은 퍼뮤테이션 플로우샵 스케줄링 문제 (PFSP) 에 대한 행렬 형식을 기반으로 새로운 상한선 및 하한선 도출 프레임워크를 제안하여 태일러드 및 VRF 벤치마크 instance 의 대부분에서 기존 경계를 개선하고, Taillard 의 추측 및 알고리즘의 점근적 근사비에 관한 이론적 통찰을 제공했습니다.
No exponential quantum speedup for anymore
이 논문은 Chen, Liu, Zhandry 가 제안한 양자 알고리즘이 이득을 보였던 것으로 알려진 및 관련 문제에 대해 효율적인 고전 알고리즘을 제시함으로써 더 이상 지수적 양자 가속이 존재하지 않음을 증명합니다.
An Algorithm for Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices
이 논문은 가격이 비증가하는 단기간 계획에서 1-분할점 전량 할인을 적용한 단일 품목 로트 사이징 문제를 해결하기 위해, 최적 해의 새로운 성질을 규명하고 시간 복잡도를 가진 기존 최선 알고리즘보다 향상된 시간 복잡도의 하이브리드 동적 계획법 알고리즘을 제안합니다.
Towards an algebraic approach to the reconfiguration CSP
이 논문은 고전적 CSP 복잡도 분석 기법에서 영감을 받아, 불리언 도메인에서 일반적 설정으로 확장 가능한 재구성 CSP 의 새로운 대수적 접근법을 제시하며, 특히 부분 연산을 사용하여 등식 제약을 포착하고 해결 가능한 사례를 식별하는 방법을 탐구합니다.
Approximation Algorithms for the -Matching and List-Restricted Variants of MaxQAP
이 논문은 최대 이차 할당 문제 (MaxQAP) 의 두 가지 일반화인 리스트 제한 변형과 -매칭 변형에 대해 각각 및 근사 알고리즘을 제안하여 기존에 알려진 최상의 근사 인자와 점근적으로 일치하는 최초의 근사 해법을 제시합니다.
Robust Permutation Flowshops Under Budgeted Uncertainty
본 논문은 예산 제약 하의 불확실성 모델을 적용한 강건한 순차적 플로우샵 문제에 대해, 다항식 개수의 명목 문제 (nominal problem) 를 해결함으로써 다항식 시간 내에 최적 해를 구할 수 있음을 증명하고, 특히 2 대의 기계에 대해서는 다항식 시간 해법이 존재하며 고정된 수의 기계에 대해서는 다항식 시간 근사 알고리즘이 가능함을 보여줍니다.
Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions
이 논문은 예측 정보를 활용하여 예측의 정확도에 따라 적응적으로 샘플 복잡도를 줄이면서도 최악의 경우 유효성을 보장하는 최적의 독립성 검정 알고리즘을 제안하고, 이에 대한 하한을 증명합니다.
Generalizing Fair Top- Selection: An Integrative Approach
이 논문은 다수의 보호 집단을 고려한 공정한 상위-k 선택 문제를 다루며, 기존 연구의 한계를 극복하기 위해 계산 복잡성 분석을 통해 효율성 회복 가능성을 규명하고, 편차 최소화를 넘어 더 안정적인 유틸리티 손실 지표를 도입하여 실세계 데이터에서 우수한 성능을 보이는 통합적 알고리즘을 제안합니다.
Quantum Algorithms for Network Signal Coordination
이 논문은 NP-완전 문제인 네트워크 신호 조정 (NSC) 문제를 해결하기 위해 그로버 알고리즘을 적용하고, 시스템 지연 임계값을 만족하는 해의 비율 (α) 에 무관하게 2 차 속도 향상을 제공하는 강건한 NSC 문제 및 다항식 정밀도 확장 알고리즘을 개발하여 시뮬레이션과 실제 양자 컴퓨터를 통해 검증했습니다.
Revisiting Graph Modification via Disk Scaling: From One Radius to Interval-Based Radii
본 논문은 단위 원판 그래프의 기하학적 구조를 반영하여 수정된 원판의 반경을 고정값이 아닌 주어진 구간 내에서 선택할 수 있도록 일반화한 '그래프 스케일링' 문제를 연구하며, 다양한 그래프 클래스에 대한 매개변수화 복잡도 분석을 통해 기존 연구의 미해결 문제를 해결하고 새로운 경계 조건을 제시합니다.
Generalized matching decoders for 2D topological translationally-invariant codes
이 논문은 2 차원 위상적 병진 불변 (TTI) 양자 부호를 토포로 코드 (TC) 의 여기 상태로 매핑하여 그래프 매칭 기법으로 디코딩하는 방법을 제안하고, 이 방식이 오류 정정 능력과 코드 용량 임계값을 보장하며 실제적인 이변수 자전거 (BB) 부호에서도 높은 성능을 보임을 증명합니다.
ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
이 논문은 유한 정규 CW 복합체에서 최적 모스 매칭 문제를 $2^{O(k \log k)} n2^{o(k \log k)} n^{O(1)}k$ 에 대한 정확한 복잡도 하한을 확립했습니다.
Finding Short Paths on Simple Polytopes
이 논문은 단순 다면체에서 선형 계획법의 최적해로 가는 최단 단조 경계 및 최단 피벗 시퀀스 계산이 NP-난해임을 증명하여 관련 오픈 문제를 해결하고, 다면체의 지름 계산의 NP-난해성을 입증한 반면, 특정 확장 형식을 통해 다항 시간 내에 경로를 찾을 수 있음을 보여줍니다.
Dynamic Kernel Graph Sparsifiers
이 논문은 점의 위치가 동적으로 변경되는 기하학적 그래프에 대해 시간 내에 스펙트럼 스파스파이어를 유지하는 풀리-다이나믹 데이터 구조를 제안하고, 이를 통해 반복적 최적화 알고리즘에 적용 가능한 적응적 적대자 견고성과 행렬 - 벡터 곱셈 및 투영을 위한 랜덤화된 스케치를 제시합니다.
An Objective Improvement Approach to Solving Discounted Payoff Games
이 논문은 할인된 보상 게임의 해를 구하기 위해 기존 전략 개선이나 가치 반복 방식과 구별되는, 모든 에지를 활용한 제약 시스템과 오차 최소화 기반의 새로운 대칭적 개선 접근법을 제시합니다.
A computational transition for detecting correlated stochastic block models by low-degree polynomials
이 논문은 상관관계가 있는 두 개의 희소 확률적 블록 모델 (Stochastic Block Model) 과 독립적인 Erdős-Rényi 모델을 구별하는 문제에서 저차 다항식 (low-degree polynomials) 기반 검정의 계산적 임계값을 Otter 상수와 Kesten-Stigum 임계값 중 더 작은 값으로 결정하고, 이를 통해 해당 조건 이하에서의 부분 복원 및 검출 문제의 계산적 난이도를 증명합니다.
Highway Dimension: a Metric View
이 논문은 그리드 그래프와 유클리드 평면과 같은 자연스러운 거리 공간도 포함하도록 고속도로 차원 (highway dimension) 의 정의를 근사 최단 경로에 기반하여 완화하고, 이를 바탕으로 TSP 에 대한 PTAS 를 제시하며 패딩 분해 및 트리 커버 등 다양한 메트릭 툴킷을 구축하여 폭넓은 응용 가능성을 제시합니다.