Seven problems: so different yet close
The paper considers seven problems from linear algebra, combinatorics and a calendar-planning problem. Despite the apparent difference between these problems, the author shows that they have close connections. In Section 2, the seven problems are stated and extremum functions, which characterize the performance of the optimal solution in the worst case are presented. In Section 3, connections between the problems and relationships between the functions are analysed. In Section 4, further bounds on the functions are summarized, many of those referring to the literature, where the results originate. Section 5 provides concluding remarks, noting that problem P4 is central in the list of problems and three conjectures for further research are offered. For the entire collection see [Zbl 1476.68010].
- The problem of intractability and analysis of heuristics in discrete optimization. I
- Optimality conditions in discrete optimization problems
- A special class of problems of geometric optimization
- scientific article; zbMATH DE number 203962
- Minimax problems of discrete optimization invariant under majority operators
- Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches
- A special class of problems of geometric optimization
- scientific article; zbMATH DE number 1187135 (Why is no real title available?)
- Scheduling Conflict-Free Parties for a Dating Service
- The Number of Solutions Sufficient for Solving a Family of Problems
- Estimates of the deviation of approximate solutions from an optimal solution in certain problems of discrete optimization
This page was built for publication: Seven problems: so different yet close
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q826117)
