Yuzhong Qu Nanjing University

Presentation on theme: "Yuzhong Qu Nanjing University"— Presentation transcript:

1 Yuzhong Qu Nanjing University
Order of elements Yuzhong Qu Nanjing University

2 Topological ordering Directed Acyclic Graph (DAG)
Kahn, Arthur B. (1962), Topological sorting of large networks, Communications of the ACM 5 (11): 558–562. Tarjan, Robert E. (1976), Edge-disjoint spanning trees and depth-first search, Acta nformatica 6 (2): 171–185

3 Depth-First Search (DFS)
Undirected graph: No cross edges DAG: No backward edges

4 竞赛图（Tournament） 竞赛图：底图为Kn的有向图 A B C 4个选手参加的循环赛，比赛结果图

5 竞赛图与有向哈密尔顿通路 竞赛图含有向哈密尔顿通路（归纳证明）

6 循环赛排名 一条有向Hamilton通路（排名） C A B D E F 另一条有向Hamilton通路（排名） A B D E F C

7 循环赛排名 按照得胜的竞赛场次(得分)排名： A(胜4) B,C(胜3) D, E(胜2) F(胜1)
问题：很难说B,C并列第二名是否公平，毕竟C战胜的对手比B战胜的对手的总得分更高(9比5)。 E D

8 循环赛排名 当竞赛图满足某种条件下，这个序列收敛于一个固定的排列，这可以作为排名：A C B E D F。 建立对应与每个对手得分的向量
s1 = (a1, b2, c3, d4, e5, f6) 然后逐次求第k级的得分向量sk, 每个选手的第k级得分是其战胜的对手在第k-1级得分的总和。 A B F C 对应于左图所示的竞赛结果，得分向量： s1=(4,3,3,2,2,1) s2=(8,5,9,3,4,3) s3=(15,10,16,7,12,9) s4=(38,28,32,21,25,16) s5=(90,62,87,41,48,32) E D 当竞赛图满足某种条件下，这个序列收敛于一个固定的排列，这可以作为排名：A C B E D F。

9 循环赛排名（FAS） A’: Feedback Arc Set (FAS) (V, A-A’) becomes acyclic (DAG)
Minimum Feedback Arc set {FC, EC} C A B D E F A B  F C  E D

10 It’s difficult to decide who is the winner
References [BTT1989] Bartholdi, J. and C. Tovey, and M. Trick, Voting schemes for which it can be difficult to tell who won the election, Social Choice and Welfare 6 (1989) [Younger1963] D. Younger. Minimum Feedback Arc Sets for a Directed Graph. IEEE Transactions on Circuit Theory, Vol. 10, No. 2. (1963), pp [Kemeny1959] J. G. Kemeny. Mathematics without numbers. Daedalus, 88: , 1959.

11 Adjacent matrix representation for digraph

12 FAS and MAS Weighted digraph Minimum Feedback Arc Set (最小反馈弧集)
Maximum Acyclic subgraph (最大无环子图)

13 MST (undirected graph)
Weighted graph Minimum spanning tree (Prim, Kruskal) Maximum spanning tree (-wij)

14 Approximation algorithms for FAS
Maximal (may not be Maximum) Fast VS approximation ratio

15 Approximation algorithms for FAS
Heuristics [ELS1993] Ordering vertices by degree (outdegree-indegree) Result O(m) worst-case time on a digraph m arcs Approximation ratio bounded by O((n)) [ELS1993] Eades, P.; Lin, X.; Smyth, W. F. (1993), A fast and effective heuristic for the feedback arc set problem, Information Processing Letters 47: 319–323.

16 Approximation algorithms for FAS
Heuristics [CF2003] Breaking cycles by removing arcs: Arcs with small weight in cycles VS arcs belonging to a large number of cycles //the weight of all arcs in C is decreased Result O(mn) worst-case time on a digraph with n vertices and m arcs Approximation ratio bounded by the length of a longest simple cycle of the digraph. [CF2003] Camil Demetrescu, Irene Finocchi: Combinatorial algorithms for feedback problems in directed graphs. Inf. Process. Lett. 86(3): (2003)

17 An Example

18 Maximum Acyclic Subgraph (MAS)
References [BW1997] B. Berger and P. W. Shor. Tight bounds for the Maximum Acyclic Subgraph problem. J. Algorithms, 25(1):1–18, 1997. [HR1994] R. Hassin and S. Rubinstein. Approximations for the Maximum Acyclic Subgraph Problem. Information Processing Letters, 51: , 1994.

19 Rank aggregation a special case of the weighted feedback arc set problem Fig. 4 (Kemeny, 1959)

20 Partial Ranking Reference
[Ailon2010] Nir Ailon: Aggregation of Partial Rankings, p-Ratings and Top-m Lists. Algorithmica 57(2): (2010) [FKMSV2006] Ronald Fagin, Ravi Kumar, Mohammad Mahdian, D. Sivakumar, Erik Vee: Comparing Partial Rankings. SIAM J. Discrete Math. 20(3): (2006) [BFB2009] Mukul S. Bansal, David Fernandez-Baca. Computing distances between partial rankings. Inf. Process. Lett. 109(4): (2009) [DKNS2001] Cynthia Dwork, Ravi Kumar, Moni Naor, D. Sivakumar: Rank aggregation methods for the Web. WWW 2001:

21 Other references [ACN2008] Nir Ailon, Moses Charikar, Alantha Newman: Aggregating inconsistent information: Ranking and clustering. J. ACM 55(5) (2008) Frans Schalekamp, Anke van Zuylen: Rank Aggregation: Together We're Strong. ALENEX 2009: 38-51

22 Websoft Research Group
Acknowledgement Websoft Research Group

23 Related NP-hard problem
Minimum path cover problem Longest path problem

24 有向无环图的极小路径覆盖（Minimum path cover of a directed acyclic graph）
有向无环图的路径覆盖 有向无环图的极小路径覆盖（Minimum path cover of a directed acyclic graph） 2 5 1 4 3

25 有向无环图的路径覆盖（二部图匹配） G’ X1 Y1 X2 Y2 R L Y3 X3 X4 Y4 X5 Y5

26 有向无环图的路径覆盖（二部图匹配） G’ X1 Y1 X2 Y2 R L Y3 X3 X4 Y4 X5 Y5

27 由二部图的匹配生成路径覆盖 覆盖路径的个数=顶点个数-匹配对个数 2 5 1 4 3

28 由二部图的匹配生成路径覆盖