Good morning everyone,
with regards to zerobasefee, I think that the argument that HTLCs are
costly doesn't quite hold up because they are always free to an
attacker as it stands. However, I fully agree with Zmn's opinion that
it's not necessary to bang our head against any opposition to this
because we can simply follow his excellent method for overweighing
base fee. I believe this is a very natural approach to let the market
decide on the relative importance of optimized routing vs base fees.
As to Martin's approximation research, I have asked myself similar
questions. Unfortunately, the paper you cite is paywalled and not
available at sci-hub, so I haven't read it. FWIW, I believe I have a
simple proof that minimum cost flow preserves approximation FACTORS:
Let O be the original problem and A the approximated problem such that
every flow in O can be mapped 1:1 to a flow in A and vice versa. Let
every edge e in O be represented by a set of edges in A whose total
cost is within a factor (1+epsilon) for every possible flow (could be
over- or underestimating). Note that this means that every flow in O
has cost within a factor (1+epsilon) for the corresponding flow in A
and vice versa.
Now let f_a be the min cost flow in A and f_o the min cost flow in O.
Assume that c(f_o)(1+epsilon):
>
> Dear Carsten, Rene and fellow lightning developers,
>
> Regarding the approximation quality of the minimum convex cost flow
> formulation for multi-part payments on the lightning network [1] and
> Carsten's discussion points on Twitter [2] and on the mailing list:
>
> > 8) Quality of Approximation
> >
> > There are some problems in computer science that are hard/impossible to
> > approximate, in the sense that any kind of deviation from the optimum
> > could cause the computed results to be extremely bad. Do you have some
> > idea (or proof) that your kind of approximation isn't causing a major
> > issue? I guess a piece-wise linearization with an infinite number of
> > pieces corresponds to the optimal result. Given a finite number of
> > pieces, how large is the difference to the optimum?
>
> I did some literature research and came across an insightful paper [3] by
> Dorit Hochbaum from 1993, that proves proximity results for integer and
> continuous optimal solutions of the minimum convex cost flow as well as
> proximity results of the optimal solutions for a piecewise linear
> approximation and the original problem.
>
> Admittedly theoretical results, however, it further underpins that a
> piecewise linear approximation is a reasonable approach to find optimal flows
> and even shows that searching for optimal solutions on the continuous domain
> (e.g. with descent methods from convex optimization) also gives near-optimal
> solutions on the integer domain.
>
> Cheers,
> Martin
>
> [1] https://arxiv.org/abs/2107.05322
> [2] https://twitter.com/renepickhardt/status/1502293438498234371
> [3] https://www.worldscientific.com/doi/abs/10.1142/9789812798190_0005
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
