4
$\begingroup$

Given an positive integer $n$, we define an order of subset sums (or simply, an order, when there is no ambiguity) to be a sequence of all subsets of $\{1,\ldots,n\}$. For example, when $n=2$, the sequence $\emptyset,\{1\},\{2\},\{1,2\}$ is an order.

We call an order $S_1,\ldots,S_{2^n}$ valid if there exist real numbers $0<x_1<\cdots<x_n$ such that $\sum_{i\in S_1}x_i<\cdots<\sum_{i\in S_{2^n}}x_i$. For example, when $n=2$, the sequence $\emptyset,\{1\},\{2\},\{1,2\}$ is a valid order, but the sequence $\emptyset,\{1\},\{1,2\},\{2\}$ is not because we cannot make $x_1+x_2<x_2$.

The question is, given $n$, how to enumerate all possible valid orders. To output an order $S_1,\ldots,S_{2^n}$, it is sufficient to output an algorithm that generates this order, i.e., an algorithm with no input (the parameter $n$ is built-in) that outputs $S_1,\ldots,S_{2^n}$ in order, as long as the algorithm runs in $O(n2^n)$ time. Even so, this problem still cannot be solved in time polynomial in $n$, because there may be exponentially many valid orders, thus an algorithm running in exponential time is welcome.

A trivial algorithm would be to iterate over all possible orders, and check for each one if it is valid. But I cannot even find an (efficient) way to check if an order is valid.

$\endgroup$
6
  • $\begingroup$ As far as I understand, you are asking about Boolean Lattice (please see: en.wikipedia.org/wiki/Boolean_algebra_(structure)), where you introduce a total order using an additional vector $X=(x_1,x_2,...,x_n)$. Your "valid order" is used to be called a chain. It's unclear why you define this total order using existence of $X$ only - it will depend on values in $X$. Also for totally ordered set there will be only one chain (provided that there are no pairwise equal elements). $\endgroup$
    – HEKTO
    Feb 23, 2020 at 23:10
  • $\begingroup$ @HEKTO Yes, I'm essentially seeking for a method to enumerate all possible chains as the values of $x_1,\ldots,x_n$ vary. However, I don't understand how this problem is related to the Boolean algebra since this problem talks about orders of subsets. $\endgroup$
    – xskxzr
    Feb 24, 2020 at 1:51
  • $\begingroup$ If you want to know what happens with chains when the vector $X$ varies - then you should clarify your question. The set of subsets of a finite set is Boolean algebra and Boolean lattice (= $n$-dimensional hypercube), where each node is a Boolean $n$-tuple $\endgroup$
    – HEKTO
    Feb 24, 2020 at 4:04
  • 1
    $\begingroup$ @HEKTO I now understand the relation between subsets and Boolean algebra, but how can this help solve the problem? I don't know how to clarify since I don't know the definition of "chain" and I have a sense that your "chain" is not equivalent to my "valid order". Maybe it is more proper to say that I'm essentially seeking for a method to enumerate all possible total orders as the values of $x_1,\ldots,x_n$ vary. I think the question statement is clear though it does not mention any concept about boolean lattice. $\endgroup$
    – xskxzr
    Feb 24, 2020 at 5:47
  • $\begingroup$ Chain is a totally ordered subset of a poset. Maximum chain is a chain, which is not contained in any other chain. Totally ordered set consists of a single maximum chain. $\endgroup$
    – HEKTO
    Feb 24, 2020 at 15:14

1 Answer 1

0
$\begingroup$

Here is one algorithm that runs in doubly exponential time -- so probably useless. In other words, this answer is probably not useful.

You can check whether an order is valid in $2^{O(n)}$ time (i.e., $\text{poly}(2^n)$ time) by reducing to linear programming: you obtain $2^n+n-2$ linear inequalities in $n$ variables, and you can test for feasibility in time polynomial in the number of inequalities and variables. Then, enumerating over all possible sums and checking if each is valid would yield a $(2^n)! 2^{O(n)} = 2^{n 2^n + O(2^n)}$ time algorithm. This will be ridiculously slow in practice.


To improve this, you could use an iterative pruning / branch-and-bound style algorithm. Given a prefix $S_1,\dots,S_k$ of an order, we can test whether it is valid using linear programming as above. If it is not, we don't consider any order that starts with this prefix. In other words, do breadth-first search: first choose $S_1$, then choose $S_2$, then choose $S_3$, and so on, at each step checking whether the prefix obtained so far is valid.

This may still be extremely slow, as there is the possibility that a prefix $S_1,\dots,S_k$ is valid but there is no way to complete it to a full order $S_1,\dots,S_{2^n}$ that is valid, so this might do a lot of wasted work.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.