An Introduction to Inverse Combinatorial Problems
Marc Demange, Jérôme Monnot · 2014
This chapter is divided into two parts: firstly, it evokes polynomial inverse problems and discusses the solution methods associated with them, and, secondly, the chapter discusses various hard inverse problems. The chapter also allows us to tackle the general question of comparing, from an algorithmic complexity point of view, the initial problem and its inverse versions. It aims to be an introduction to inverse combinatorial problems. Rather than making a list of currently known results, the objective is to select a range that is representative of the different types of problems and results for the case of the L1 norm.