Approximation Algorithms for the -Matching and List-Restricted Variants of MaxQAP
이 논문은 최대 이차 할당 문제 (MaxQAP) 의 두 가지 일반화인 리스트 제한 변형과 -매칭 변형에 대해 각각 및 근사 알고리즘을 제안하여 기존에 알려진 최상의 근사 인자와 점근적으로 일치하는 최초의 근사 해법을 제시합니다.
💻 Category
cs.DM
48 편의 논문
Robust Permutation Flowshops Under Budgeted Uncertainty
본 논문은 예산 제약 하의 불확실성 모델을 적용한 강건한 순차적 플로우샵 문제에 대해, 다항식 개수의 명목 문제 (nominal problem) 를 해결함으로써 다항식 시간 내에 최적 해를 구할 수 있음을 증명하고, 특히 2 대의 기계에 대해서는 다항식 시간 해법이 존재하며 고정된 수의 기계에 대해서는 다항식 시간 근사 알고리즘이 가능함을 보여줍니다.
Positional s-of-k games
이 논문은 승리를 위한 요소 개수 임계값을 일반화한 's-of-k 게임'이라는 새로운 프레임워크를 제안하고, 최적 전략과 짝짓기 전략 제한 하에서 삼각형, 정사각형, 마름모, 육각형 격자 보드에서 달성 가능한 점수를 분석합니다.
Minimal toughness in subclasses of weakly chordal graphs
이 논문은 약한 조화 그래프의 여러 하위 클래스 (여기 조화 그래프, 네트-프리 여조화 그래프, 숲의 여집합, -프리 그래프, 완전 다분할 그래프 등) 에 대한 최소 강인성 그래프를 완전히 분류하고, 이를 통해 기존 연구 결과에 대한 간단한 증명을 제시합니다.
Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees
이 논문은 평면 점 집합의 스패닝 트리 간 재구성 (플립) 과정에서 최단 시퀀스의 구조적 특성을 연구하며, 기존에 제안된 '해피 엣지', '파킹 엣지', '리파킹'에 관한 세 가지 주요 추측 중 일부는 특정 조건에서 성립하지만 일반적인 경우에는 반증됨을 보여줍니다.
Algebraic Characterization of Reversible First Degree Cellular Automata over
이 논문은 임의의 격자 크기와 상태 수를 가진 1 차 셀룰러 오토마타 (FDCA) 의 가역성을 상수 시간에 판별하고 모든 가역적 규칙을 생성할 수 있도록 하는 세 가지 필요충분 조건을 대수적으로 제시합니다.
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$ 에 대한 정확한 복잡도 하한을 확립했습니다.
Submodular Maximization over a Matroid -Intersection: Multiplicative Improvement over Greedy
이 논문은 개의 매트로이드 교집합 제약 하에서 단조 서브모듈러 함수 최대화 문제에 대해 그리디 알고리즘의 -근사율을 개선한 최초의 배수적 향상 () 을 제공하는 새로운 하이브리드 알고리즘을 제안합니다.