태그 보관물: np-hardness

np-hardness

최소 비용 피드백 아크 세트 문제에 대한 빠른 알고리즘? 세트라고합니다. F ⊂ E G ∖

유 방향 그래프 , 에서 가 DAG (directed acyclic graph)이면 를 피드백 아크 세트라고합니다. F ⊂ E G ∖ F F

G=(V,E)

F⊂E

G∖F

F

각 에지가 가중치 와 연관된 경우 , 최소 비용 피드백 아크 세트 문제는 가 최소가 되도록 를 찾는 것이다 .F 승 ( F )

w

F

W(F)

최소 피드백 아크 세트 문제는 NP-hard이고, 최소 비용 피드백 아크 세트 문제도 잘 알려져있다. 누구나 잘 수행하는 대략적인 알고리즘과 빠른 솔버를 생성 할 수있는 가중치 함수의 속성을 알고 있는지 궁금합니다.

답변

  1. Daniel Apon은 제 논문의 컨퍼런스 버전에 연결되었습니다. 내가 대신 초안 저널 버전을 제안한다 http://www.cs.brown.edu/people/ws/papers/fast_journal.pdf를 .

  2. 토너먼트 그래프에서 일부 실험 결과에 따르면 지역 검색이 잘 수행되고 있습니다. :의 Anke 반 Zuylen와 프란스 Schalekampf의 최근 ALENEX 용지를 참조하십시오 http://www.siam.org/proceedings/alenex/2009/alx09_004_schalekampf.pdf을 .

  3. 가중치가 “확률 제약 조건”또는 “삼각형 부등식”중 하나를 만족하면 퀵 정렬을 기반으로하는 상수 팩터 근사 알고리즘이 있습니다. Ailon, Charikar 및 Newman의 최근 JACM 논문을 참조하십시오.

  4. 어떤 종류의 인스턴스를 염두에두고 실제로 또는 이론적으로 잘 작동하는 것을 찾고 있는지에 대해 좀 더 말씀해 주시겠습니까?

답변

Claire Kenyon-Mathieu와 Warren Schudy (STC 2007, Schudy 페이지의 저널 버전)의 “몇 가지 오류로 순위를 매기는 방법 : 토너먼트에 가중 피드백 아크 세트에 대한 PTAS”(Schody 페이지의 저널 버전 STOC 2007)를 참조하십시오. 유 방향 그래프가 토너먼트 인 특별한 경우.

답변