[HN Gopher] Historic algorithms help unlock shortest-path proble...
___________________________________________________________________
Historic algorithms help unlock shortest-path problem breakthrough
Author : nxten
Score : 75 points
Date : 2023-08-26 18:44 UTC (4 hours ago)
(HTM) web link (cacm.acm.org)
(TXT) w3m dump (cacm.acm.org)
| ozarker wrote:
| What's an application where you'd absolutely have to have a graph
| with negative weights? Couldn't you just preprocess the edges and
| normalize their weights?
| riedel wrote:
| >In finance, for example, there may be situations in currency
| or options trading where buying and selling in one sequence is
| more profitable than taking a different path, and these can be
| modeled using negative weights as long as the search algorithm
| is fast enough. But those negative weights can throw Dijkstra's
| shortest-path algorithm for a loop.
| rhelz wrote:
| Its pretty hard to give _any_ problem which you absolutely
| _have_ to solve using only one particular technique.
| Nevertheless, there are some problems which require more than
| just being able to add positive numbers together in order to
| solve.
|
| Consider, for example, the problem of moving an electric car
| with regenerative braking along a grid of very hilly roads,
| using minimal charge from the battery. When you go down a hill,
| sure, you can add energy to your battery by hitting the brakes.
| But when you go uphill again, you may have to drain your
| battery of charge.
|
| Indeed, if you can find a course which is largely downhill, you
| may very well end uo with a "negative amount of energy charged"
| to the battery :-)
| ozarker wrote:
| That's a great example. Thank you
| gnull wrote:
| > Couldn't you just preprocess the edges and normalize their
| weights?
|
| How exactly?
| bhl wrote:
| The issue with negative weighted edges is that a cycle would
| result in an infinite loop when finding shortest path, compared
| to when all edges are non-negative, cycles can be safely
| skipped.
|
| Compared to Dijkstra's original algorithm of E + V log V,
| naively pre-processing edges would require V^2 work assuming an
| edge can exist between each vertex.
|
| Edit: the algorithm you're describing exists btw
| https://en.m.wikipedia.org/wiki/Johnson%27s_algorithm
| heavenlyblue wrote:
| > The issue with negative weighted edges is that a cycle
| would result in an infinite loop when finding shortest path
|
| No it "could" result in an infinite loop. For driving
| situations negative weights would probably never yield
| infinite cycles due to negative weight. For that to happen
| some laws of physics would need to change drastically (i.e. a
| longer path yielding lower energy usage the longer it gets is
| nonsensical in any sense that is sensical in the physical
| world)
| klyrs wrote:
| I use regenerative braking as a driving application -- you
| gain energy by going downhill. A negative cycle would look
| like an Escher drawing.
| schneems wrote:
| I think the question isn't "what is the issue with negative
| weights" rather "what is a real world example of negative
| weights" which the article doesn't really explain.
|
| I don't know any off hand. I would guess its when a path has
| a benefit incurred rather than a cost. I.e. in a monopoly
| board it might be shorter to get to a destination by getting
| thrown in jail first, but the longer path around the whole
| board comes with a benefit I.e. negative weight of receiving
| $200 by crossing the start.
|
| Your reply does help clarify the "why not normalize" which is
| helpful. I'm still curious for other examples of negative
| weights.
| bhl wrote:
| > In finance, for example, there may be situations in
| currency or options trading where buying and selling in one
| sequence is more profitable than taking a different path,
| and these can be modeled using negative weights as long as
| the search algorithm is fast enough.
|
| This is a non-contrived example. You could do this as a
| mini-project where you scrape various foreign exchange or
| cryptocurrency data, and try to find some arbitrage
| opportunities by running these shortest path algorithms.
| schneems wrote:
| To try to restate that. Someone owns currency A then buys
| B which is a cost, but it has a good exchange rate with
| currency C and C has a good exchange rate with A. So the
| B-C-A move yields a profit which would be representative
| as a negative weight. Is that right?
| empath-nirvana wrote:
| If I understand correctly, if you find such a loop in a graph
| of currency exchange rates, that would represent an arbitrage
| opportunity where you can basically make "infinite money"
| (although typically those loops close quickly if they're
| exploitable in the real world).
| jll29 wrote:
| The problem lies in the non-monotonous structure of the
| sequence of weight when combining positive and negative
| weights, which is incompatible with Dijkstra's greedy search,
| which requires monotonous weight sequences in the traversal.
| klyrs wrote:
| A prototypical example today is to take battery range into
| account in navigation. You charge your battery going downhill,
| corresponding to a negative edge weight. If you're driving from
| the top of a mountain, through a valley, to the top of a hill,
| many of the available routes might end up with a negative cost!
|
| Preprocessing is certainly possible, but the result is to
| densify the graph. That densification can turn a sparse graph
| with O(n) edges into a dense graph with O(n^2) edges. When the
| goal is to keep pathfinding to a nearly-linear (roughly
| O(vertices + edges) with log factors) runtime in the presence
| of negative weight edges, naive preprocessing blows the budget
| before you even start pathfinding.
|
| The article at hand presents long-sought after algorithms which
| hit the near-linear runtime goal at the cost of a combination
| of clever preprocessing and a novel divide&conquer approach. So
| yes, preprocessing, no, not "just" preprocessing.
| thethirdone wrote:
| You can preprocess the battery range problem quite
| efficiently. If is not possible to gain more charge than the
| gravitational potential between the endpoints for any path.
| You can change all of the edge weights from battery charge
| changes into battery charge as compared to a perfectly
| efficient car.
|
| This would make a downhill edge A->B and uphill edge B->A
| both have approximately the cost of the average between them
| which should be decidedly non-negative.
| [deleted]
| bunabhucan wrote:
| I'm an uber eats driver picking up a long delivery but
| notifications comes in for grubhub and Doordash for two short
| deliveries with pickups and dropoffs along my existing route.
| thomasahle wrote:
| What kind of normalization are you thinking of? Like adding a
| constant to all edge weights?
| shoo wrote:
| A sibling comment linking to Johnson's algorithm shows a way
| to do it.
|
| To me, adding a constant to all edges seems like an obvious
| idea to try-- but one issue is that it will distort the
| ranking for paths that have different numbers of edges.
| Ideally a normalisation would preserve the ranking of paths
| so that a path with minimal unnormalised weight would also be
| a path of minimal normalised weight. But ranking won't be
| preserved by adding a constant C to all edge weights, now
| paths with more edges will be unfairly penalised.
| [deleted]
| carterschonwald wrote:
| https://arxiv.org/abs/2203.03456 And
| https://arxiv.org/abs/2203.00671 Are the relevant papers
| [deleted]
___________________________________________________________________
(page generated 2023-08-26 23:00 UTC)