کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
433767 689623 2016 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Ranking chain sum orders
ترجمه فارسی عنوان
رتبه بندی سفارشات کلی زنجیره
کلمات کلیدی
سفارشات کلی و جزئی؛ اقدامات فاصله؛ رتبه بندی؛ NPNP سختی؛ پیچیدگی پارامتر ثابت
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Ranking information is an important topic in information sciences, Internet searching, voting systems, and sports. In the full information approach, a ranking is a total order of the candidates. We compare two rankings by pairwise comparisons under the nearest neighbor Kendall tau distance and study the distance and rank aggregation problems.In many settings, the information is incomplete and a ranking is given by a partial order. A bucket order is obtained if a ranking allows ties and treats tied candidates as equivalent. Then the distance and rank aggregation problems can be solved efficiently in almost linear time. A chain sum order is complementary to a bucket order and consists of a set of disjoint total orders. Its width and height is the number and the maximum size of the total orders, respectively.We show that the distance and rank aggregation problems of a total order and a chain sum order of bounded width or of height at most two can be solved in polynomial time and are NPNP-complete for a total and a chain sum order of height at least 12. Both problems remain NPNP-complete for a total and a heap order which is the partial order obtained from a single-elimination tournament (in sports). However, the problems are fixed-parameter tractable with respect to the distance and the Ulam distance, but are fixed-parameter intractable with respect to the order dimension.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 636, 11 July 2016, Pages 66–76
نویسندگان
, ,