Parameterized Algorithmics for Voting Systems

投票系统的参数化算法

基本信息

项目摘要

Many voting problems are NP-hard, hence there is no hope for polynomial-time solutions. Among such problems we find specific cases of winner determination or the optimization of lobbying in multiple referenda. However, voting problems typically carry natural parameterizations; for instance, obvious parameters are the number of candidates or the number of votes. Depending on the concrete application behind, each of these parameters may be small. The project PAWS targets at determining the influence of various parameterizations on the computational complexity of natural voting problems. The employed methods include complexity-theoretic techniques as well as implementation and empirical testing of newly developed algorithms.
许多投票问题是NP难的,因此没有希望得到多项式时间的解决方案。在这些问题中,我们发现了赢家确定或在多次公投中优化游说的具体情况。然而,投票问题通常带有自然的参数化;例如,明显的参数是候选人的数量或投票的数量。根据后面的具体应用,这些参数中的每一个都可能很小。PAWS项目的目标是确定各种参数化对自然投票问题计算复杂性的影响。所采用的方法包括复杂性理论的技术,以及新开发的算法的实施和实证测试。

项目成果

期刊论文数量(2)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
How to Put Through Your Agenda in Collective Binary Decisions
  • DOI:
    10.1145/2837467
  • 发表时间:
    2013-11
  • 期刊:
  • 影响因子:
    0
  • 作者:
    N. Alon;Robert Bredereck;Jiehua Chen;Stefan Kratsch;R. Niedermeier;G. Woeginger
  • 通讯作者:
    N. Alon;Robert Bredereck;Jiehua Chen;Stefan Kratsch;R. Niedermeier;G. Woeginger
Theoretical and empirical evaluation of data reduction for exact Kemeny Rank Aggregation
  • DOI:
    10.1007/s10458-013-9236-y
  • 发表时间:
    2014-09
  • 期刊:
  • 影响因子:
    1.9
  • 作者:
    Nadja Betzler;Robert Bredereck;R. Niedermeier
  • 通讯作者:
    Nadja Betzler;Robert Bredereck;R. Niedermeier
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Professor Dr. Rolf Niedermeier (†)其他文献

Professor Dr. Rolf Niedermeier (†)的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Professor Dr. Rolf Niedermeier (†)', 18)}}的其他基金

Trade-offs in Parameterized Data Reduction
参数化数据缩减的权衡
  • 批准号:
    389085303
  • 财政年份:
    2017
  • 资助金额:
    --
  • 项目类别:
    Research Grants
Multivariate Algorithmics for Temporal Graph Problems (MATE)
时态图问题的多元算法 (MATE)
  • 批准号:
    382063982
  • 财政年份:
    2017
  • 资助金额:
    --
  • 项目类别:
    Research Grants
Data reduction in parameterized algorithmics: New models and methods
参数化算法中的数据缩减:新模型和方法
  • 批准号:
    218550609
  • 财政年份:
    2012
  • 资助金额:
    --
  • 项目类别:
    Research Grants
Data-driven parameterized algorithmics of graph modification problems(DAPA)
图修改问题的数据驱动参数化算法(DAPA)
  • 批准号:
    210010251
  • 财政年份:
    2011
  • 资助金额:
    --
  • 项目类别:
    Research Grants
Algorithmen zur Erzeugung quasiregulärer Strukturen in Graphen (AREG)
生成图中拟正则结构的算法(AREG)
  • 批准号:
    66926305
  • 财政年份:
    2008
  • 资助金额:
    --
  • 项目类别:
    Research Grants
Parameterized algorithmics for bioinformatics
生物信息学参数化算法
  • 批准号:
    50500304
  • 财政年份:
    2007
  • 资助金额:
    --
  • 项目类别:
    Research Grants
Parametrisierte Algorithmik
参数化算法
  • 批准号:
    65062910
  • 财政年份:
    2007
  • 资助金额:
    --
  • 项目类别:
    Research Grants
Iterative Kompression zur Lösung schwieriger Netzprobleme
迭代压缩解决网络难题
  • 批准号:
    16707968
  • 财政年份:
    2005
  • 资助金额:
    --
  • 项目类别:
    Priority Programmes
Small parameters in hard problems: Design, analysis, implementation and application of fixed-parameter algorithms
难题中的小参数:定参数算法的设计、分析、实现和应用
  • 批准号:
    5401637
  • 财政年份:
    2003
  • 资助金额:
    --
  • 项目类别:
    Independent Junior Research Groups
Optimal solutions for hard problems in computational biology
计算生物学难题的最佳解决方案
  • 批准号:
    5292128
  • 财政年份:
    2000
  • 资助金额:
    --
  • 项目类别:
    Research Grants

相似海外基金

NeTS: Small: Revisiting Network Algorithmics using the CRAM Model
NeTS:小型:使用 CRAM 模型重新审视网络算法
  • 批准号:
    2333587
  • 财政年份:
    2024
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
Multilayer Algorithmics to Leverage Graph Structure (MultilayerALGS)
利用图结构的多层算法 (MultilayerALGS)
  • 批准号:
    EP/T004878/1
  • 财政年份:
    2020
  • 资助金额:
    --
  • 项目类别:
    Research Grant
Behavioural-based mathematical programming: algorithmics and applications
基于行为的数学规划:算法和应用
  • 批准号:
    RGPIN-2017-05073
  • 财政年份:
    2019
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
AF: Small: Foundations for Data-driven Algorithmics
AF:小:数据驱动算法的基础
  • 批准号:
    1816874
  • 财政年份:
    2018
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
Behavioural-based mathematical programming: algorithmics and applications
基于行为的数学规划:算法和应用
  • 批准号:
    RGPIN-2017-05073
  • 财政年份:
    2018
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
Multivariate Algorithmics for Temporal Graph Problems (MATE)
时态图问题的多元算法 (MATE)
  • 批准号:
    382063982
  • 财政年份:
    2017
  • 资助金额:
    --
  • 项目类别:
    Research Grants
Behavioural-based mathematical programming: algorithmics and applications
基于行为的数学规划:算法和应用
  • 批准号:
    RGPIN-2017-05073
  • 财政年份:
    2017
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
Expressivity and Algorithmics of Higher-Order Horn Clauses
高阶 Horn 子句的表达性和算法
  • 批准号:
    1893570
  • 财政年份:
    2017
  • 资助金额:
    --
  • 项目类别:
    Studentship
Social Choice in a Social Context: A Multivariate Algorithmics Perspective
社会背景下的社会选择:多元算法视角
  • 批准号:
    317459980
  • 财政年份:
    2016
  • 资助金额:
    --
  • 项目类别:
    Research Fellowships
Multivariate Algorithmics for Graph and String Problems in Bioinformatics
生物信息学中图和字符串问题的多元算法
  • 批准号:
    289297972
  • 财政年份:
    2015
  • 资助金额:
    --
  • 项目类别:
    Research Grants
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了