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.

Adaptive backtracking search optimization algorithm with pattern search for numerical optimization

The backtracking search optimization algorithm（BSA） is one of the most recently proposed population-based evolutionary algorithms for global optimization. Due to its memory ability and simple structure, BSA has powerful capability to find global optimal solutions. However, the algorithm is still insufficient in balancing the exploration and the exploitation. Therefore, an improved adaptive backtracking search optimization algorithm combined with modified Hooke-Jeeves pattern search is proposed for numerical global optimization. It has two main parts： the BSA is used for the exploration phase and the modified pattern search method completes the exploitation phase. In particular, a simple but effective strategy of adapting one of BSA＇s important control parameters is introduced. The proposed algorithm is compared with standard BSA, three state-of-the-art evolutionary algorithms and three superior algorithms in IEEE Congress on Evolutionary Computation 2014（IEEE CEC2014） over six widely-used benchmarks and 22 real-parameter single objective numerical optimization benchmarks in IEEE CEC2014. The results of experiment and statistical analysis demonstrate the effectiveness and efficiency of the proposed algorithm.

Inversion of source process and related studies of the Taiwan Strait earthquake using genetic algorithm

pplying genetic algorithm to inversion of seismic moment tensor solution and using the data of P waveform from digital network and initial motion directions of P waves of Taiwan network stations, we studied the moment tensor solutions and focal parameters of the earthquake of M=7.3 on 16 September of 1994 in Taiwan Strait and other four quakes of ML5.8 in the near region (21°～26°N, 115°～120°E). Among the five earthquakes, the quake of M=7.3 on September 16, 1994 in Taiwan Strait is the strongest one in the southeastern coast area since Nan′ao earthquake of M=7.3 in 1918. The results show that moment tensor solution of M=7.3 earthquake is mainly doublecouple component, and is normal fault whose fault plane is near NW. The strike of the fault plane resembles that of the distributive bands of earthquakes before the main event and fracture pattern shown by aftershocks. The tension stress axis of focal mechanism is about horizontal, near in NE strike, the compressive stress axis is approximately vertical, near in NWW strike. It seems that this quake is controlled by the force of Philippine plate′s pressing Eurasian plate in NW direction. But from the viewpoint of P axis of near vertical and T axis of near horizontal, it is a normal fault of strong tensibility. There are relatively big difference between focal mechanism solution of this quake and those of the four other strong quakes. The complexity of source mechanism solution of these quakes represents the complexity of the process of the strait earthquake sequences.

Parrondo's paradox for chaos control and anticontrol of fractional-order systems

We present the generalized forms of Parrondo＇s paradox existing in fractional-order nonlinear systems. The gener- alization is implemented by applying a parameter switching （PS） algorithm to the corresponding initial value problems associated with the fractional-order nonlinear systems. The PS algorithm switches a system parameter within a specific set of N 〉 2 values when solving the system with some numerical integration method. It is proven that any attractor of the concerned system can be approximated numerically. By replacing the words ＂winning＂ and ＂loosing＂ in the classical Parrondo＇s paradox with ＂order＂ and ＂chaos＂, respectively, the PS algorithm leads to the generalized Parrondo＇s paradox： chaos1 ＋ chaos2 ＋..- ＋ chaosN = order and order1 ＋ order2 ＋.-. ＋ orderN = chaos. Finally, the concept is well demon- strated with the results based on the fractional-order Chen system.

Kernelization in Parameterized Computation: A Survey

Parameterized computation is a new method dealing with NP-hard problems, which has attracted a lot of attentions in theoretical computer science. As a practical preprocessing method for NP-hard problems, kernelizaiton in parameterized computation has recently become an active research area. In this paper, we discuss several kernelizaiton techniques, such as crown decomposition, planar graph vertex partition, randomized methods, and kernel lower bounds, which have been used widely in the kernelization of many hard problems.

Some Open Problems in Parameterized Complexity Related to the Work of Jianer Chen

This short paper highlights some open problems related to the work of Jianer Chen in the area of parameterized/multivariate algorithmics.

A method for aircraft magnetic interference compensation based on small signal model and LMS algorithm

Aeromagnetic interference could not be compensated effectively if the precision of parameters which are solved by the aircraft magnetic field model is low. In order to improve the compensation effect under this condition, a method based on small signal model and least mean square（LMS） algorithm is proposed. According to the method, the initial values of adaptive filter＇s weight vector are calculated with the solved model parameters through small signal model at first,then the small amount of direction cosine and its derivative are set as the input of the filter, and the small amount of the interference is set as the filter＇s expected vector. After that, the aircraft magnetic interference is compensated by LMS algorithm. Finally, the method is verified by simulation and experiment. The result shows that the compensation effect can be improved obviously by the LMS algorithm when original solved parameters have low precision. The method can further improve the compensation effect even if the solved parameters have high precision.

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（√k log k））,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（√k log k））, 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]）.

Dynamic Dominating Set and Turbo-Charging Greedy Heuristics

The main purpose of this paper is to exposit two very different, but very general, motivational schemes in the art of parameterization and a concrete example connecting them. We introduce a dynamic version of the DOMINATING SET problem and prove that it is fixed-parameter tractable（FPT）. The problem is motivated by settings where problem instances evolve. It also arises in the quest to improve a natural greedy heuristic for the DOMINATING SET problem.

Real-time fault detection method based on belief rule base for aircraft navigation system

Real-time and accurate fault detection is essential to enhance the aircraft navigation system’s reliability and safety. The existent detection methods based on analytical model draws back at simultaneously detecting gradual and sudden faults. On account of this reason, we propose an online detection solution based on non-analytical model. In this article, the navigation system fault detection model is established based on belief rule base （BRB）, where the system measuring residual and its changing rate are used as the inputs of BRB model and the fault detection function as the output. To overcome the drawbacks of current parameter optimization algorithms for BRB and achieve online update, a parameter recursive estimation algorithm is presented for online BRB detection model based on expectation maximization （EM） algorithm. Furthermore, the proposed method is verified by navigation experiment. Experimental results show that the proposed method is able to effectively realize online parameter evaluation in navigation system fault detection model. The output of the detection model can track the fault state very well, and the faults can be diagnosed in real time and accurately. In addition, the detection ability, especially in the probability of false detection, is superior to offline optimization method, and thus the system reliability has great improvement.