☆

0

Nice paper building on top of [the WebGraph framework](https://papers-gamma.link/paper/31) and [Chierichetti et al.](https://papers-gamma.link/paper/126) to compress graphs.
### Approximation guarantee
I read: "our algorithm is inspired by a theoretical approach
with provable guarantees on the final quality, and it is designed to directly optimize the resulting compression ratio.".
I misunderstood initially, but the proposed algorithm actually does not have any provable approximation guarantee other than the $\log(n)$ one (which is also obtained by a random ordering of the nodes).
Designing an algorithm with (a better) approximation guarantee for minimizing "MLogA", "MLogGapA" or "BiMLogA" seems to be a nice open problem.
### Objectives
Is there any better objective than "MLogA", "MLogGapA" or "BiMLogA" to have a proxy of the compression obtained by the BV-framework?
Is it possible to directly look for an ordering that minimizes the size of the output of BV compression algorithm?

☆

1

Hello, I need the key point of your algorithm is not really clear
> • We start with the root such that all edges are possibly
> here or not. The upper bound is the sum of the $n \choose 2$
> heaviest edges, while the associated solution is the empty
> subgraph, the lower bound is thus 0.
>
> • Then at each iteration we create two children for the node
> with maximum lower bound (i.e. density of the associated
> solution). Suppose the node is at depth $i$ in the tree, we
> keep the decisions made on the first $i-1$ edges and create
> two children, one where the $i^\text{th}$ edge is included and one
> where it is not.
I need to understand this part in clear way if that is possible please

> I need to understand this part in clear way if that is possible please
I see. I agree it is not perfectly clear, sorry about that.
Can you try to understand it with the branch and bound [wikipedia page](https://en.wikipedia.org/wiki/Branch_and_bound), [the slides](https://drive.google.com/file/d/0B6cGK503Ibt0Qlg3bUVKRnFBTG8/view) and [the code](https://github.com/maxdan94/HkS)?
If it is still not clear after that, please come back and I'll try to phrase a better explanation ASAP.

## Comments: