Arrow Research search

Author name cluster

Iyad Kanj

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers
1 author row

Possible papers

12

AAMAS Conference 2025 Conference Paper

Parameterized Algorithms for Multiagent Pathfinding on Trees

  • Argyrios Deligkas
  • Eduard Eiben
  • Robert Ganian
  • Iyad Kanj
  • M. S. Ramanujan

The classical Multiagent Pathfinding problem has been extensively studied not only within the artificial intelligence research community, but also by scholars in the areas of theoretical computer science and computational geometry. The problem asks for a minimum-makespan schedule that routes 𝑘 agents (or robots) from their starting points to their destinations in a graph, while avoiding collisions, and is known to be NP-hard even on the fundamental class of trees. In this article we present two fixed parameter algorithms parameterized by 𝑘: the first yields a collision-free schedule on trees whose makespan deviates from the optimum by at most an additive polynomial function of 𝑘, and the second solves Multiagent Pathfinding optimally on the class of irreducible trees, i. e. , trees with no vertices of degree 2. Both results rely on novel tools and insights into the properties of optimal schedules.

PDF

AAAI Conference 2021 Conference Paper

The Parameterized Complexity of Clustering Incomplete Data

  • Eduard Eiben
  • Robert Ganian
  • Iyad Kanj
  • Sebastian Ordyniak
  • Stefan Szeider

We study fundamental clustering problems for incomplete data. Specifically, given a set of incomplete d-dimensional vectors (representing rows of a matrix), the goal is to complete the missing vector entries in a way that admits a partitioning of the vectors into at most k clusters with radius or diameter at most r. We give tight characterizations of the parameterized complexity of these problems with respect to the parameters k, r, and the minimum number of rows and columns needed to cover all the missing entries. We show that the considered problems are fixed-parameter tractable when parameterized by the three parameters combined, and that dropping any of the three parameters results in parameterized intractability. A byproduct of our results is that, for the complete data setting, all problems under consideration are fixed-parameter tractable parameterized by k + r.

PDF Details

AAAI Conference 2020 Conference Paper

On the Parameterized Complexity of Clustering Incomplete Data into Subspaces of Small Rank

  • Robert Ganian
  • Iyad Kanj
  • Sebastian Ordyniak
  • Stefan Szeider

We consider a fundamental matrix completion problem where we are given an incomplete matrix and a set of constraints modeled as a CSP instance. The goal is to complete the matrix subject to the input constraints and in such a way that the complete matrix can be clustered into few subspaces with low rank. This problem generalizes several problems in data mining and machine learning, including the problem of completing a matrix into one with minimum rank. In addition to its ubiquitous applications in machine learning, the problem has strong connections to information theory, related to binary linear codes, and variants of it have been extensively studied from that perspective. We formalize the problem mentioned above and study its classical and parameterized complexity. We draw a detailed landscape of the complexity and parameterized complexity of the problem with respect to several natural parameters that are desirably small and with respect to several well-studied CSP fragments.

PDF Details

AAAI Conference 2020 Conference Paper

On the Problem of Covering a 3-D Terrain

  • Eduard Eiben
  • Isuru Godage
  • Iyad Kanj
  • Ge Xia

We study the problem of covering a 3-dimensional terrain by a sweeping robot that is equipped with a camera. We model the terrain as a mesh in a way that captures the elevation levels of the terrain; this enables a graph-theoretic formulation of the problem in which the underlying graph is a weighted plane graph. We show that the associated graph problem is NP-hard, and that it admits a polynomial time approximation scheme (PTAS). Finally, we implement two heuristic algorithms based on greedy approaches and report our findings.

PDF Details

NeurIPS Conference 2019 Conference Paper

The Parameterized Complexity of Cascading Portfolio Scheduling

  • Eduard Eiben
  • Robert Ganian
  • Iyad Kanj
  • Stefan Szeider

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.

PDF Details

AAAI Conference 2018 Conference Paper

Improved Results for Minimum Constraint Removal

  • Eduard Eiben
  • Jonathan Gemmell
  • Iyad Kanj
  • Andrew Youngdahl

Given a set of obstacles and two designated points in the plane, the MINIMUM CONSTRAINT REMOVAL problem asks for a minimum number of obstacles that can be removed so that a collision-free path exists between the two designated points. It is a well-studied problem in both robotic motion planning and wireless computing that has been shown to be NP-hard in various settings. In this work, we extend the study of MINIMUM CONSTRAINT REMOVAL. We start by presenting refined NP-hardness reductions for the two cases: (1) when all the obstacles are axes-parallel rectangles, and (2) when all the obstacles are line segments such that no three intersect at the same point. These results improve on existing results in the literature. As a byproduct of our NP-hardness reductions, we prove that, unless the Exponential-Time Hypothesis (ETH) fails, MIN- IMUM CONSTRAINT REMOVAL cannot be solved in subexponential time 2o(n), where n is the number of obstacles in the instance. This shows that significant improvement on the brute-force 2O(n) -time algorithm is unlikely. We then present a subexponential-time algorithm for instances of MINIMUM CONSTRAINT REMOVAL in which the number of obstacles that overlap at any point is constant; the algorithm runs in time 2O( √ N), where N is the number of the vertices in the auxiliary graph associated with the instance of the problem. We show that significant improvement on this algorithm is unlikely by showing that, unless ETH fails, MIN- IMUM CONSTRAINT REMOVAL with bounded overlap number cannot be solved in time 2o( √ N). We describe several exact algorithms and approximation algorithms that leverage heuristics and discuss their performance in an extensive empirical simulation.

PDF Details

JAIR Journal 2015 Journal Article

On the Subexponential-Time Complexity of CSP

  • Ronald de Haan
  • Iyad Kanj
  • Stefan Szeider

Not all NP-complete problems share the same practical hardness with respect to exact computation. Whereas some NP-complete problems are amenable to efficient computational methods, others are yet to show any such sign. It becomes a major challenge to develop a theoretical framework that is more fine-grained than the theory of NP-completeness, and that can explain the distinction between the exact complexities of various NP-complete problems. This distinction is highly relevant for constraint satisfaction problems under natural restrictions, where various shades of hardness can be observed in practice. Acknowledging the NP-hardness of such problems, one has to look beyond polynomial time computation. The theory of subexponential-time complexity provides such a framework, and has been enjoying increasing popularity in complexity theory. An instance of the constraint satisfaction problem with n variables over a domain of d values can be solved by brute-force in d n steps (omitting a polynomial factor). In this paper we study the existence of subexponential-time algorithms, that is, algorithms running in d o(n) steps, for various natural restrictions of the constraint satisfaction problem. We consider both the constraint satisfaction problem in which all the constraints are given extensionally as tables, and that in which all the constraints are given intensionally in the form of global constraints. We provide tight characterizations of the subexponential-time complexity of the aforementioned problems with respect to several natural structural parameters, which allows us to draw a detailed landscape of the subexponential-time complexity of the constraint satisfaction problem. Our analysis provides fundamental results indicating whether and when one can significantly improve on the brute-force search approach for solving the constraint satisfaction problem.

PDF Details DOI

AAAI Conference 2013 Conference Paper

On the Subexponential Time Complexity of CSP

  • Iyad Kanj
  • Stefan Szeider

A Constraint Satisfaction Problem (CSP) with n variables ranging over a domain of d values can be solved by brute-force in dn steps (omitting a polynomial factor). With a more careful approach, this trivial upper bound can be improved for certain natural restrictions of the CSP. In this paper we establish theoretical limits to such improvements, and draw a detailed landscape of the subexponential-time complexity of CSP. We first establish relations between the subexponentialtime complexity of CSP and that of other problems, including CNF-SAT. We exploit this connection to provide tight characterizations of the subexponential-time complexity of CSP under common assumptions in complexity theory. For several natural CSP parameters, we obtain threshold functions that precisely dictate the subexponential-time complexity of CSP with respect to the parameters under consideration. Our analysis provides fundamental results indicating whether and when one can significantly improve on the brute-force search approach for solving CSP.

PDF Details