Social Choice Meets Graph Drawing： How to Get Subexponential Time Algorithms for Ranking and Drawing Problems

We analyze a common feature of p-Kemeny AGGregation(p-KAGG) and p-One-Sided Crossing Minimization(p-OSCM) to provide new insights and findings of interest to both the graph drawing community and the social choice community. We obtain parameterized subexponential-time algorithms for p-KAGG—a problem in social choice theory—and for p-OSCM—a problem in graph drawing. These algorithms run in time O.2O.pk logk//,where k is the parameter, and significantly improve the previous best algorithms with running times O.1.403k/and O.1.4656k/, respectively. We also study natural "above-guarantee" versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of p-directed feedback arc set. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of "votes" in the input to p-KAGG is odd the above guarantee version can still be solved in time O.2O.pk logk//, while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails(equivalently, unless FPT D M[1]).     

Philosophy,history and sociology of science: Interdisciplinary relations and complex social identities

Sociology and philosophy of science have an uneasy relationship, while the marriage of history and philosophy of science has—on the surface at least—been more successful. I will take a sociological look at the history of the relationships between philosophy and history as well as philosophy and sociology of science. Interdisciplinary relations between these disciplines will be analysed through social identity complexity theory in order to draw out some conclusions on how the disciplines interact and how they might develop. I will use the relationships between the disciplines as a pointer for a more general social theory of interdisciplinarity which will then be used to sound a caution on how interdisciplinary relations between the three disciplines might be managed.     

Parameterized Algorithmics for Computational Social Choice：Nine Research Challenges

Computational Social Choice is an interdisciplinary research area involving Economics, Political Science,and Social Science on the one side, and Mathematics and Computer Science（including Artificial Intelligence and Multiagent Systems） on the other side. Typical computational problems studied in this field include the vulnerability of voting procedures against attacks, or preference aggregation in multi-agent systems. Parameterized Algorithmics is a subfield of Theoretical Computer Science seeking to exploit meaningful problem-specific parameters in order to identify tractable special cases of in general computationally hard problems. In this paper, we propose nine of our favorite research challenges concerning the parameterized complexity of problems appearing in this context. This work is dedicated to Jianer Chen, one of the strongest problem solvers in the history of parameterized algorithmics,on the occasion of his 60 th birthday.     

复杂性研究——转变思维模式的一个重要方向

复杂性研究针对以牛顿力学为代表的近代科学思维模式的简单化、绝对化、忽视时间作用等弊病,为思维模式的转变提供了一种新的思路和方向,本文从概念的多元化、质的多样性、视角多样性、层次多样性、时间的作用、信息的作用等6个方面切入,认识和理解复杂性。并以经济学为例,阐述了复杂性在实际工作中的运用。     

浅探战争系统复杂性概貌

结合系统论的观点,从战争系统的元素以及元素之间关系两方面讨论了战争系统的系统论模型.从组分复杂性、结构复杂性和功能复杂性三方面阐述了战争系统的复杂性本体论模型.分析了战争复杂系统不对称性、远离平衡态、自组织、不可逆不可重复性、记忆性和局域作用效应等特性表现.最后,从建模与仿真的角度对战争系统的复杂性能否被简化以及人的因...     

心率变异性的复杂性与分形维数分析

发挥非线性动力学的潜力，提出了心率变异性（ＨＲＶ）信号的复杂度分析法和分形维数分析法。由于这两种方法能从较短的ＨＲＶ信号中提取信息，因此作者又进一步把这两种分析方法发展成动态分析法。用这两种方法分别对一个改变体位的ＨＲＶ信号和一个发生心肌缺血的ＨＲＶ信号的过程进行了动态分析。分析结果表明，它们都成功地检测出了ＨＲＶ信号的生理和病理变化。可见，动态复杂度分析法和动态分形维数分析法对ＨＲＶ信号及类似于ＨＲＶ的信号是很有前途的分析方法。     

映射排序算法研究

提出了一类问题的映射排序算法，其特点是附加一定的存储开销，在内排序中关键字与数组下标作映射或链接处理，不实施反复比较与交换关键字的操作，时间复杂性达到Ｏ（Ｎ），在外排序中，文件输入／输出次数减少，提高了效率，这类算法适宜今后的大规模信息处理中广泛采用。     

关于有限平面点集的角控集

对一给定有限平面点集Ｓ与一个实数α满足０〈α〈２π，Ｓ的最大子集Ｓα满足对任ｘ∈Ｓα，存在一个以ｘ为中心且夹角不小于α的两条射线使得由两条射线为边界的无界区域内不存在Ｓ中的点，称Ｓα为Ｓ的α角控集。     

实现网络结点编号和添加虚工序的一种计算机处理方法

本文介绍一种算法,可对工程管理网络图的各个结点进行编号,并实现虚工序的自动添加。文末给出了算法的时间复杂度分析。