사이니스

Betweenness
이 기사는 제약이 있는 아이템의 주문에 관한 것입니다.소셜 네트워크의 중심성에 대해서는 betweeness centrality를 참조해 주세요.지오메트리의 간격 관계는 순서 지오메트리를 참조하십시오.

betweenness는 일부 항목이 다른 [1]항목 사이에 배치되어야 하는 제약 조건의 대상이 되는 항목의 집합을 명령하는 순서 이론의 알고리즘 문제입니다.생물 정보학에서[2] 적용되었으며 Opatrný(1979)[3]에 의해 NP-완전인 것으로 나타났다.

문제문

betweeness 문제에 대한 입력은 정렬된 3배의 항목 집합입니다.이들 트리플에 열거된 항목은 총 순서로 정렬해야 하며, 주어진 트리플 각각에 대해 트리플의 중간 항목이 다른 두 항목 사이의 출력에 나타납니다.각 트리플의 항목은 [1][3]출력에 연속될 필요가 없습니다.

예

예를 들어, 입력 트리플의 수집은

(2,1,3), (3,4,5), (1,4,5), (2,4,1), (5,2,3)

출력 순서에 의해 충족됩니다.

3, 1, 4, 2, 5

에 의해서가

3, 1, 2, 4, 5.

이들 출력순서의 첫 번째 순서에서는 5개의 입력트리플 모두에 대해 다른 2개의 항목 사이에 트리플의 중간 항목이 나타나지만, 두 번째 출력순서의 경우 항목 4는 항목 1과 항목 2 사이에 있지 않아 트리플(2,4,1)에 의해 주어진 요건에 반한다.

입력에 (1,2,3) 및 (2,3,1)와 같은 두 개의 트리플이 포함되어 있고, 세 개의 항목은 같지만 가운데 항목은 다른 경우 유효한 솔루션이 없습니다.그러나 유효한 해답이 없는 트리플 세트를 형성하는 더 복잡한 방법이 있는데, 이러한 모순된 트리플 쌍을 포함하지 않습니다.

복잡성

Opatrn ((1979)는 (알고리즘이 유효한 솔루션이 존재하는지 여부를 결정해야 하는) 사이의 문제의 결정 버전이 3가지 만족도의 감소와 하이퍼그래프 2가지 다른 [3]감소로 NP-완전함을 보여주었다.단, 순서 없는 항목의 모든 3배가 입력의 순서 있는 3배로 표시되었을 경우, 주문의 선두가 되는 2개의 항목 중 1개를 선택한 후, 이 항목을 포함한 3배를 사용하여 나머지 항목의 각 쌍의 상대 위치를 비교함으로써 쉽게 해결할 수 있다.

만족된 트리플의 수를 최대화하는 순서를 찾는 관련 문제는 MAXSNP-hard로, P =[1] NP가 아닌 한 다항 시간에서 임의로 1에 가까운 근사 비율을 달성하는 것은 불가능하다는 것을 의미한다.정렬되지 않은 각 항목의 [4]3배씩 순서가 매겨진 3배씩을 포함하는 조밀한 인스턴스에서도 해결하거나 근사하는 것은 여전히 어렵습니다.토너먼트로 제한된 문제의 최소 버전은 다항식 시간 근사 체계(PTAS)[5]가 있는 것으로 입증되었다.아이템을 랜덤하게 정렬함으로써 1/3(기대)의 근사비를 얻을 수 있으며, 이 간단한 전략은 독특한 게임 추측이 [6]참일 경우 가능한 최선의 다항 시간 근사치를 제공한다.또한 다항식 [1][7]시간에 만족할 수 있는 인스턴스의 최소 3배의 반을 만족시키는 순서를 찾기 위해 반정의 프로그래밍 또는 조합 방법을 사용할 수 있다.

파라미터화된 복잡도에서는 파라미터화된 알고리즘에 의해 구한 솔루션 품질q와 랜덤 [8]오더에 의해 예상되는 C/3 품질과의 차이 q - C/3에 의해 파라미터화된 제약조건의 집합 C에서 가능한 한 많은 제약조건을 만족시키는 문제는 고정 파라미터 처리가 가능하다.

성공을 보장하지는 않지만,[2] 탐욕스러운 휴리스틱은 실제로 발생하는 중간 문제의 많은 사례에 대한 해결책을 찾을 수 있습니다.

적용들

생물정보학에서 유전자 매핑 과정의 일부로서 betweeness의 적용 중 하나가 발생한다.특정 유형의 유전자 실험은 유전자 표지의 세 가지 순서를 결정하기 위해 사용될 수 있지만, 유전자 배열과 그것의 반전을 구별하지 않기 때문에, 그러한 실험에서 얻은 정보는 세 가지 표지의 세 가지 중 어느 것이 중간 것인지 결정한다.betweenness 문제는 이런 유형의 [1][2]실험 데이터가 주어진 단일 시퀀스로 마커 컬렉션을 조립하는 문제를 추상화한 것입니다.

또한 그 사이의 문제는 확률, 인과관계, [9]시간의 이론을 모형화하는 데 사용되어 왔다.

레퍼런스

  1. ^ a b c d e 를 클릭합니다Chor, Benny; Sudan, Madhu (1998), "A geometric approach to betweenness", SIAM Journal on Discrete Mathematics, 11 (4): 511–523 (electronic), doi:10.1137/S0895480195296221, MR 1640920.
  2. ^ a b c 를 클릭합니다Slonim, Donna; Kruglyak, Leonid; Stein, Lincoln; Lander, Eric (1997), "Building human genome maps with radiation hybrids", Journal of Computational Biology, 4 (4): 487–504, doi:10.1089/cmb.1997.4.487, PMID 9385541.
  3. ^ a b c 를 클릭합니다Opatrný, J. (1979), "Total ordering problem", SIAM Journal on Computing, 8 (1): 111–114, doi:10.1137/0208008, MR 0522973.
  4. ^ 를 클릭합니다Ailon, Nir; Alon, Noga (2007), "Hardness of fully dense problems", Information and Computation, 205 (8): 1117–1129, doi:10.1016/j.ic.2007.02.006, MR 2340896.
  5. ^ Karpinski, Marek; Schudy, Warren (2011), "Approximation schemes for the betweenness problem in tournaments and related ranking problems", in L.A. Goldberg and K. Jansen and R.Ravi and J.D.P. Rolim (ed.), Proc. APPROX 2011, RANDOM 2011, Lecture Notes in Computer Science, vol. 6845, pp. 277–288, arXiv:0911.2214, doi:10.1007/978-3-642-22935-0_24, S2CID 7180847
  6. ^ 를 클릭합니다Charikar, Moses; Guruswami, Venkatesan; Manokaran, Rajsekar (2009), "Every permutation CSP of arity 3 is approximation resistant", 24th Annual IEEE Conference on Computational Complexity, pp. 62–73, doi:10.1109/CCC.2009.29, MR 2932455, S2CID 257225.
  7. ^ 를 클릭합니다Makarychev, Yury (2012), "Simple linear time approximation algorithm for betweenness", Operations Research Letters, 40 (6): 450–452, doi:10.1016/j.orl.2012.08.008, MR 2998680.
  8. ^ 를 클릭합니다Gutin, Gregory; Kim, Eun Jung; Mnich, Matthias; Yeo, Anders (2010), "Betweenness parameterized above tight lower bound", Journal of Computer and System Sciences, 76 (8): 872–878, arXiv:0907.5427, doi:10.1016/j.jcss.2010.05.001, MR 2722353, S2CID 3408698.
  9. ^ 를 클릭합니다Chvátal, Vašek; Wu, Baoyindureng (2011), "On Reichenbach's causal betweenness", Erkenntnis, 76 (1): 41–48, arXiv:0902.1763, doi:10.1007/s10670-011-9321-z, S2CID 14123568.