Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Marek Karpinski , Warren Schudy

ABSTRACT

We study fixed parameter algorithms for three problems: Kemeny rank aggregation, feedback arc set tournament, and betweenness tournament. For Kemeny rank aggregation we give an algorithm with runtime \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O^*(2^{O(\sqrt{OPT})})$\end{document}, where n is the number of candidates, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$OPT \le \binom{n}{2}$\end{document} is the cost of the optimal ranking, and O*(·) hides polynomial factors. This is a dramatic improvement on the previously best known runtime of O*(2O(OPT)). For feedback arc set tournament we give an algorithm with runtime \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O^*(2^{O(\sqrt{OPT})})$\end{document}, an improvement on the previously best known \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O^*(OPT^{O(\sqrt{OPT})})$\end{document} [4]. For betweenness tournament we give an algorithm with runtime \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O^*(2^{O(\sqrt{OPT/n})})$\end{document}, where n is the number of vertices and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$OPT \le \binom{n}{3}$\end{document} is the optimal cost. This improves on the previously known \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O^*(OPT^{O(OPT^{1/3})})$\end{document} [28], especially when OPT is small. Unusually we can solve instances with OPT as large as n (logn)2 in polynomial time! More... »

PAGES

3-14

Book

TITLE

Algorithms and Computation

ISBN

978-3-642-17516-9
978-3-642-17517-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-17517-6_3

DOI

http://dx.doi.org/10.1007/978-3-642-17517-6_3

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1041145894


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "University of Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM T.J. Watson, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "IBM T.J. Watson, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schudy", 
        "givenName": "Warren", 
        "id": "sg:person.015153430167.81", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015153430167.81"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "We study fixed parameter algorithms for three problems: Kemeny rank aggregation, feedback arc set tournament, and betweenness tournament. For Kemeny rank aggregation we give an algorithm with runtime \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O^*(2^{O(\\sqrt{OPT})})$\\end{document}, where n is the number of candidates, \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$OPT \\le \\binom{n}{2}$\\end{document} is the cost of the optimal ranking, and O*(\u00b7) hides polynomial factors. This is a dramatic improvement on the previously best known runtime of O*(2O(OPT)). For feedback arc set tournament we give an algorithm with runtime \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O^*(2^{O(\\sqrt{OPT})})$\\end{document}, an improvement on the previously best known \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O^*(OPT^{O(\\sqrt{OPT})})$\\end{document} [4]. For betweenness tournament we give an algorithm with runtime \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O^*(2^{O(\\sqrt{OPT/n})})$\\end{document}, where n is the number of vertices and \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$OPT \\le \\binom{n}{3}$\\end{document} is the optimal cost. This improves on the previously known \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O^*(OPT^{O(OPT^{1/3})})$\\end{document} [28], especially when OPT is small. Unusually we can solve instances with OPT as large as n (logn)2 in polynomial time!", 
    "editor": [
      {
        "familyName": "Cheong", 
        "givenName": "Otfried", 
        "type": "Person"
      }, 
      {
        "familyName": "Chwa", 
        "givenName": "Kyung-Yong", 
        "type": "Person"
      }, 
      {
        "familyName": "Park", 
        "givenName": "Kunsoo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-17517-6_3", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-17516-9", 
        "978-3-642-17517-6"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "Kemeny Rank Aggregation", 
      "rank aggregation", 
      "feedback arc", 
      "parameter algorithm", 
      "algorithm", 
      "runtime", 
      "polynomial time", 
      "fast algorithm", 
      "number of candidates", 
      "optimal ranking", 
      "polynomial factor", 
      "number of vertices", 
      "optimal cost", 
      "cost", 
      "tournament", 
      "ranking", 
      "vertices", 
      "instances", 
      "aggregation", 
      "number", 
      "dramatic improvement", 
      "improvement", 
      "opt", 
      "time", 
      "arc", 
      "candidates", 
      "factors", 
      "problem"
    ], 
    "name": "Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament", 
    "pagination": "3-14", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1041145894"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-17517-6_3"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-17517-6_3", 
      "https://app.dimensions.ai/details/publication/pub.1041145894"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:53", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_428.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-17517-6_3"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-17517-6_3'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-17517-6_3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-17517-6_3'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-17517-6_3'


 

This table displays all metadata directly associated to this object as RDF triples.

107 TRIPLES      22 PREDICATES      53 URIs      46 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-17517-6_3 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N8138b629f73544dfb0f15610ecc633f4
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description We study fixed parameter algorithms for three problems: Kemeny rank aggregation, feedback arc set tournament, and betweenness tournament. For Kemeny rank aggregation we give an algorithm with runtime \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O^*(2^{O(\sqrt{OPT})})$\end{document}, where n is the number of candidates, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$OPT \le \binom{n}{2}$\end{document} is the cost of the optimal ranking, and O*(·) hides polynomial factors. This is a dramatic improvement on the previously best known runtime of O*(2O(OPT)). For feedback arc set tournament we give an algorithm with runtime \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O^*(2^{O(\sqrt{OPT})})$\end{document}, an improvement on the previously best known \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O^*(OPT^{O(\sqrt{OPT})})$\end{document} [4]. For betweenness tournament we give an algorithm with runtime \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O^*(2^{O(\sqrt{OPT/n})})$\end{document}, where n is the number of vertices and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$OPT \le \binom{n}{3}$\end{document} is the optimal cost. This improves on the previously known \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O^*(OPT^{O(OPT^{1/3})})$\end{document} [28], especially when OPT is small. Unusually we can solve instances with OPT as large as n (logn)2 in polynomial time!
7 schema:editor Ne6cb8cc514464ffab7a6a9b88d7206a7
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N46d0bff7f90a43278d02334b6d485735
11 schema:keywords Kemeny Rank Aggregation
12 aggregation
13 algorithm
14 arc
15 candidates
16 cost
17 dramatic improvement
18 factors
19 fast algorithm
20 feedback arc
21 improvement
22 instances
23 number
24 number of candidates
25 number of vertices
26 opt
27 optimal cost
28 optimal ranking
29 parameter algorithm
30 polynomial factor
31 polynomial time
32 problem
33 rank aggregation
34 ranking
35 runtime
36 time
37 tournament
38 vertices
39 schema:name Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
40 schema:pagination 3-14
41 schema:productId N8cd6cef07b33433ba53a9d7f4dbe4c5a
42 Nda0302d85b0840df9c180d3772a4d819
43 schema:publisher N7732303f2970471ca0a22dc0e90d1095
44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041145894
45 https://doi.org/10.1007/978-3-642-17517-6_3
46 schema:sdDatePublished 2022-12-01T06:53
47 schema:sdLicense https://scigraph.springernature.com/explorer/license/
48 schema:sdPublisher N2d42b8693f5f4f6b9cb0d57337fe7c46
49 schema:url https://doi.org/10.1007/978-3-642-17517-6_3
50 sgo:license sg:explorer/license/
51 sgo:sdDataset chapters
52 rdf:type schema:Chapter
53 N232ebdc9149d40529cd30cb30212c33f schema:familyName Park
54 schema:givenName Kunsoo
55 rdf:type schema:Person
56 N2d42b8693f5f4f6b9cb0d57337fe7c46 schema:name Springer Nature - SN SciGraph project
57 rdf:type schema:Organization
58 N46d0bff7f90a43278d02334b6d485735 schema:isbn 978-3-642-17516-9
59 978-3-642-17517-6
60 schema:name Algorithms and Computation
61 rdf:type schema:Book
62 N68a343c8ac6e4e65990395041fa097d9 rdf:first Ncdc48bcdd4354ccbb3f438acb86ee759
63 rdf:rest N8ac74743bb494aa1a53e4f1807b732d5
64 N7732303f2970471ca0a22dc0e90d1095 schema:name Springer Nature
65 rdf:type schema:Organisation
66 N8138b629f73544dfb0f15610ecc633f4 rdf:first sg:person.011636042271.02
67 rdf:rest Nfa80d1408efb44dfaf5f69a16f25df93
68 N819e1bd36b8f415992e974741ad211e1 schema:familyName Cheong
69 schema:givenName Otfried
70 rdf:type schema:Person
71 N8ac74743bb494aa1a53e4f1807b732d5 rdf:first N232ebdc9149d40529cd30cb30212c33f
72 rdf:rest rdf:nil
73 N8cd6cef07b33433ba53a9d7f4dbe4c5a schema:name dimensions_id
74 schema:value pub.1041145894
75 rdf:type schema:PropertyValue
76 Ncdc48bcdd4354ccbb3f438acb86ee759 schema:familyName Chwa
77 schema:givenName Kyung-Yong
78 rdf:type schema:Person
79 Nda0302d85b0840df9c180d3772a4d819 schema:name doi
80 schema:value 10.1007/978-3-642-17517-6_3
81 rdf:type schema:PropertyValue
82 Ne6cb8cc514464ffab7a6a9b88d7206a7 rdf:first N819e1bd36b8f415992e974741ad211e1
83 rdf:rest N68a343c8ac6e4e65990395041fa097d9
84 Nfa80d1408efb44dfaf5f69a16f25df93 rdf:first sg:person.015153430167.81
85 rdf:rest rdf:nil
86 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
87 schema:name Information and Computing Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
90 schema:name Computation Theory and Mathematics
91 rdf:type schema:DefinedTerm
92 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
93 schema:familyName Karpinski
94 schema:givenName Marek
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
96 rdf:type schema:Person
97 sg:person.015153430167.81 schema:affiliation grid-institutes:None
98 schema:familyName Schudy
99 schema:givenName Warren
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015153430167.81
101 rdf:type schema:Person
102 grid-institutes:None schema:alternateName IBM T.J. Watson, USA
103 schema:name IBM T.J. Watson, USA
104 rdf:type schema:Organization
105 grid-institutes:grid.10388.32 schema:alternateName University of Bonn, Germany
106 schema:name University of Bonn, Germany
107 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...