**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Person# François Margot

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related units

Loading

Courses taught by this person

Loading

Related research domains

Loading

Related publications

Loading

People doing similar research

Loading

Related publications (17)

Loading

Loading

Loading

Related research domains (7)

Backtracking

Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandon

Linear programming

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented

NP-completeness

In computational complexity theory, a problem is NP-complete when:
# It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no".

# When the answer is "ye

Courses taught by this person

No results

Related units (2)

People doing similar research (109)

Thomas Liebling, François Margot

In this paper, we investigate the applicability of backtrack technique to solve the vertex enumeration problem and the face enumeration problem for a convex polyhedron given by a system of linear inequalities. We show that there is a linear-time backtrack algorithm for the face enumeration problem whose space complexity is polynomial in the input size, but the vertex enumeration problem requires a backtrack algorithm to solve a decision problem, called the restricted vertex problem, for each output, which is shown to be NP-complete. Some related NP-complete problems associated with a system of linear inequalities are also discussed, including the optimal vertex problems for polyhedra and arrangements of hyperplanes.

1997This paper describes a backtracking algorithm for the enumeration of nonisomorphic minimally nonideal (n2n) matrices that are not degenerate projective planes. The application of this algorithm for nh12 yielded 20 such matrices, adding 5 matrices to the 15 previously known. For greater dimensions, n=14 and n=17, 13 new matrices are given. For nonsquare matrices, 38 new minimally nonideal matrices are described.

19982002