<p>How about problems that ask for specific binary relations with minimal cost.</p>
<p>These problems are typically defined in terms of a finite non-empty set <span class="math-container">$V=\{1,\dots,n\}$</span> and a cost function <span class="math-container">$c:V^2 \to \mathbb{R}$</span> that assigns a cost <span class="math-container">$c_{ij}$</span> to each pair <span class="math-container">$ij \in V^2$</span>. The objective is to find a binary relation <span class="math-container">$A \in R \subseteq V^2$</span> minimizes the total costs where <span class="math-container">$R$</span> is a subset of binary relations (e.g. total orders, partial orders, equivalence relations):
<span class="math-container">$$\min_{A \in R} \sum_{ij \in A} c_{ij}$$</span></p>
<p>Here are a few examples from the literature:</p>
<ul>
<li><strong>Linear ordering</strong> problem (asks for a total order of minimum cost) has <span class="math-container">$n!$</span> solutions.</li>
<li><strong>Partial ordering</strong> problem (asks for a partial order of minimum cost). The number of partial orders on <span class="math-container">$n$</span> elements is not known but it is greater than <span class="math-container">$n!$</span>.</li>
<li><strong>Clique partitioning</strong> problem (asks for an equivalence relation of minimum cost) has <span class="math-container">$B_n$</span> solutions where <span class="math-container">$B_n$</span> is the Bell number. This problem is equivalent to the correlation clustering problem.</li>
</ul>
<p>All of these problems have in common that their feasible solutions are transitive. Another closely related problem is the <strong>maximum transitive subdigraph</strong> problem that, given a directed graph <span class="math-container">$D$</span>, asks for a transitive subgraph of <span class="math-container">$D$</span> of maximum size that is transitive.</p>
<p>Further similar problems are the <strong>feedback arc set</strong> and <strong>maximum acyclic subdigraph</strong> problems. Here, given a directed graph, the objective is to find a an edge subset of minimum size whose removal makes the graph acyclic.</p>
<p><strong>EDIT:</strong> Actually, these problems are not super-exponential in the input size. The input is a cost function that assigns a cost to each pair. So it is quadratic in the number <span class="math-container">$n$</span> of elements. And the number of feasible solutions is less than <span class="math-container">$2^{n^2}$</span>.</p>

CC BY-SA 4.0
2024-11-19T08:29:02.517Z
2024-11-21T10:14:51.560Z
2024-11-21T10:14:51.560Z
badboul
<p>The following are examples of hard <a href="https://en.wikipedia.org/wiki/Combinatorial_optimization" rel="nofollow noreferrer">combinatorial optimization</a> (CO) problems in which the choice space is exponentially large in the natural parameters of the problem:</p>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Knapsack_problem" rel="nofollow noreferrer">Knapsack problem</a>: choice is a set of items <span class="math-container">$\Rightarrow$</span> exponential in the # of items</li>
<li><a href="https://en.wikipedia.org/wiki/Bin_packing_problem" rel="nofollow noreferrer">Bin packing problem</a>: choice is an assignment of items to bins <span class="math-container">$\Rightarrow$</span> exponential in the # of items</li>
<li><a href="https://en.wikipedia.org/wiki/Metric_k-center" rel="nofollow noreferrer">Metric k-center problem</a>: choice is a set of facility locations <span class="math-container">$\Rightarrow$</span> exponential in the # of facility locations</li>
<li><a href="https://grafo.etsii.urjc.es/optsicom/mdp.html" rel="nofollow noreferrer">Maximum diversity problem</a>: choice is a set of points <span class="math-container">$\Rightarrow$</span> exponential in the # of points</li>
<li><a href="https://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29" rel="nofollow noreferrer">Maximum independent set</a>: choice is a set of vertices <span class="math-container">$\Rightarrow$</span> exponential in the # of vertices</li>
</ul>
<p>The following are examples of hard CO problems in which the choice space is <em>super</em>-exponentially large in the natural parameters of the problem:</p>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem" rel="nofollow noreferrer">Traveling salesman problem</a> (TSP): choice is a permutation of cities <span class="math-container">$\Rightarrow$</span> factorial in the # of cities</li>
<li><a href="https://en.wikipedia.org/wiki/Vehicle_routing_problem" rel="nofollow noreferrer">Vehicle routing problem</a>: generalizes TSP</li>
</ul>
<p>What are some other prominent examples of CO problems with super-exponential choice spaces that have been studied in the literature? Natural candidates are problems for which a choice is an <em>ordered</em> tuple of elements of some set.</p>

CC BY-SA 4.0
2024-12-11T21:02:54.980Z
Note that $n! \leq \exp(n \log n)$ so it's still exponential in the sense of $\exp(n^{O(1)})$, which is what you get in the definition of EXPTIME for instance. In the examples you give, the size of a solution is polynomial but not linear in the size of the input.
Lê Thành Dũng 'Tito' Nguyễn
<reference-request><optimization><big-list><combinatorics>
Hard combinatorial optimization problems with super-exponential choice spaces
user76284
# Hard combinatorial optimization problems with super-exponential choice spaces

(Asked by: username_0 on 2024-11-19)

The following are examples of hard [combinatorial optimization](https://en.wikipedia.org/wiki/Combinatorial_optimization) (CO) problems in which the choice space is exponentially large in the natural parameters of the problem:

* [Knapsack problem](https://en.wikipedia.org/wiki/Knapsack_problem): choice is a set of items $\Rightarrow$ exponential in the # of items
* [Bin packing problem](https://en.wikipedia.org/wiki/Bin_packing_problem): choice is an assignment of items to bins $\Rightarrow$ exponential in the # of items
* [Metric k-center problem](https://en.wikipedia.org/wiki/Metric_k-center): choice is a set of facility locations $\Rightarrow$ exponential in the # of facility locations
* [Maximum diversity problem](https://grafo.etsii.urjc.es/optsicom/mdp.html): choice is a set of points $\Rightarrow$ exponential in the # of points
* [Maximum independent set](https://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29): choice is a set of vertices $\Rightarrow$ exponential in the # of vertices

The following are examples of hard CO problems in which the choice space is *super*-exponentially large in the natural parameters of the problem:

* [Traveling salesman problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem) (TSP): choice is a permutation of cities $\Rightarrow$ factorial in the # of cities
* [Vehicle routing problem](https://en.wikipedia.org/wiki/Vehicle_routing_problem): generalizes TSP

What are some other prominent examples of CO problems with super-exponential choice spaces that have been studied in the literature? Natural candidates are problems for which a choice is an *ordered* tuple of elements of some set.

**Tags:** reference-request, optimization, big-list, combinatorics

> **Comments:**
> **username_1**: Note that $n! \leq \exp(n \log n)$ so it's still exponential in the sense of $\exp(n^{O(1)})$, which is what you get in the definition of EXPTIME for instance. In the examples you give, the size of a solution is polynomial but not linear in the size of the input.  

---

## 1 answers

### Answer by username_2 on 2024-11-19. Score: 1

How about problems that ask for specific binary relations with minimal cost.

These problems are typically defined in terms of a finite non-empty set $V=\{1,\dots,n\}$ and a cost function $c:V^2 \to \mathbb{R}$ that assigns a cost $c\_{ij}$ to each pair $ij \in V^2$. The objective is to find a binary relation $A \in R \subseteq V^2$ minimizes the total costs where $R$ is a subset of binary relations (e.g. total orders, partial orders, equivalence relations):
$$\min\_{A \in R} \sum\_{ij \in A} c\_{ij}$$

Here are a few examples from the literature:

* **Linear ordering** problem (asks for a total order of minimum cost) has $n!$ solutions.
* **Partial ordering** problem (asks for a partial order of minimum cost). The number of partial orders on $n$ elements is not known but it is greater than $n!$.
* **Clique partitioning** problem (asks for an equivalence relation of minimum cost) has $B\_n$ solutions where $B\_n$ is the Bell number. This problem is equivalent to the correlation clustering problem.

All of these problems have in common that their feasible solutions are transitive. Another closely related problem is the **maximum transitive subdigraph** problem that, given a directed graph $D$, asks for a transitive subgraph of $D$ of maximum size that is transitive.

Further similar problems are the **feedback arc set** and **maximum acyclic subdigraph** problems. Here, given a directed graph, the objective is to find a an edge subset of minimum size whose removal makes the graph acyclic.

**EDIT:** Actually, these problems are not super-exponential in the input size. The input is a cost function that assigns a cost to each pair. So it is quadratic in the number $n$ of elements. And the number of feasible solutions is less than $2^{n^2}$.


---

