Neural Information Processing Systems http://nips.cc/

Cascading portfolio scheduling is a static algorithm selection strategy which uses a sample of test instances to compute an optimal ordering (a cascading schedule) of a portfolio of available algorithms. The algorithms are then applied to each future instance according to this cascading schedule, until some algorithm in the schedule succeeds. Cascading algorithm scheduling has proven to be effective in several applications, including QBF solving and the generation of ImageNet classification models. It is known that the computation of an optimal cascading schedule in the offline phase is NP-hard. In this paper we study the parameterized complexity of this problem and establish its fixed-parameter tractability by utilizing structural properties of the success relation between algorithms and test instances. Our findings are significant as they reveal that in spite of the intractability of the problem in its general form, one can indeed exploit sparseness or density of the success relation to obtain non-trivial runtime guarantees for finding an optimal cascading schedule.

" cascading portfolio scheduling ", is simpler to implement than per-instance selection methods and

W e only accept 1 out of 20 papers that do not cite any other paper from our own journal.

We study parameterized approximability of three optimization problems related to stable matching: (1) Min-BP-SMI: Given a stable marriage instance and a number k, find a size-at-least-k matching that minimizes the number $β$ of blocking pairs; (2) Min-BP-SRI: Given a stable roommates instance, find a matching that minimizes the number $β$ of blocking pairs; (3) Max-SMTI: Given a stable marriage instance with preferences containing ties, find a maximum-size stable matching. The first two problems are known to be NP-hard to approximate to any constant factor and W[1]-hard with respect to $β$, making the existence of an EPTAS or FPT-algorithms unlikely. We show that they are W[1]-hard with respect to $β$ to approximate to any function of $β$. This means that unless FPT=W[1], there is no FPT-approximation scheme for the parameter $β$. The last problem (Max-SMTI) is known to be NP-hard to approximate to factor-29/33 and W[1]-hard with respect to the number of ties. We complement this and present an FPT-approximation scheme for the parameter "number of agents with ties".

Decision trees are a fundamental tool in machine learning for representing, classifying, and generalizing data. It is desirable to construct ``small'' decision trees, by minimizing either the \textit{size} ($s$) or the \textit{depth} $(d)$ of the \textit{decision tree} (\textsc{DT}). Recently, the parameterized complexity of \textsc{Decision Tree Learning} has attracted a lot of attention. We consider a generalization of \textsc{Decision Tree Learning} where given a \textit{classification instance} $E$ and an integer $t$, the task is to find a ``small'' \textsc{DT} that disagrees with $E$ in at most $t$ examples. We consider two problems: \textsc{DTSO} and \textsc{DTDO}, where the goal is to construct a \textsc{DT} minimizing $s$ and $d$, respectively. We first establish that both \textsc{DTSO} and \textsc{DTDO} are W[1]-hard when parameterized by $s+δ_{max}$ and $d+δ_{max}$, respectively, where $δ_{max}$ is the maximum number of features in which two differently labeled examples can differ. We complement this result by showing that these problems become \textsc{FPT} if we include the parameter $t$. We also consider the kernelization complexity of these problems and establish several positive and negative results for both \textsc{DTSO} and \textsc{DTDO}.

Hedonic games model settings in which a set of agents have to be partitioned into groups which we call coalitions. In the enemy aversion model, each agent has friends and enemies, and an agent prefers to be in a coalition with as few enemies as possible and, subject to that, as many friends as possible. A partition should be stable, i.e., no subset of agents prefer to be together rather than being in their assigned coalition under the partition. We look at two stability concepts: core stability and strict core stability. This yields several algorithmic problems: determining whether a (strictly) core stable partition exists, finding such a partition, and checking whether a given partition is (strictly) core stable. Several of these problems have been shown to be NP-complete, or even beyond NP. This motivates the study of parameterized complexity. We conduct a thorough computational study using several parameters: treewidth, number of friends, number of enemies, partition size, and coalition size. We give polynomial algorithms for restricted graph classes as well as FPT algorithms with respect to the number of friends an agent may have and the treewidth of the graph representing the friendship or enemy relations. We show W[1]-hardness or para-NP-hardness with respect to the other parameters. We conclude this paper with results in the setting in which agents can have neutral relations with each other, including hardness-results for very restricted cases.

We survey two key problems-Multi-Winner Determination and Hedonic Games in Computational Social Choice, with a special focus on their parameterized complexity, and propose some research challenges in the field.

Cascading portfolio scheduling is a static algorithm selection strategy which uses a sample of test instances to compute an optimal ordering (a cascading schedule) of a portfolio of available algorithms. The algorithms are then applied to each future instance according to this cascading schedule, until some algorithm in the schedule succeeds. Cascading algorithm scheduling has proven to be effective in several applications, including QBF solving and the generation of ImageNet classification models. It is known that the computation of an optimal cascading schedule in the offline phase is NP-hard. In this paper we study the parameterized complexity of this problem and establish its fixed-parameter tractability by utilizing structural properties of the success relation between algorithms and test instances.

In Coordinated Motion Planning (CMP), we are given a rectangular-grid on which $k$ robots occupy $k$ distinct starting gridpoints and need to reach $k$ distinct destination gridpoints. In each time step, any robot may move to a neighboring gridpoint or stay in its current gridpoint, provided that it does not collide with other robots. The goal is to compute a schedule for moving the $k$ robots to their destinations which minimizes a certain objective target - prominently the number of time steps in the schedule, i.e., the makespan, or the total length traveled by the robots. We refer to the problem arising from minimizing the former objective target as CMP-M and the latter as CMP-L. Both CMP-M and CMP-L are fundamental problems that were posed as the computational geometry challenge of SoCG 2021, and CMP also embodies the famous $(n^2-1)$-puzzle as a special case. In this paper, we settle the parameterized complexity of CMP-M and CMP-L with respect to their two most fundamental parameters: the number of robots, and the objective target. We develop a new approach to establish the fixed-parameter tractability of both problems under the former parameterization that relies on novel structural insights into optimal solutions to the problem. When parameterized by the objective target, we show that CMP-L remains fixed-parameter tractable while CMP-M becomes para-NP-hard. The latter result is noteworthy, not only because it improves the previously-known boundaries of intractability for the problem, but also because the underlying reduction allows us to establish - as a simpler case - the NP-hardness of the classical Vertex Disjoint and Edge Disjoint Paths problems with constant path-lengths on grids.