Changes between Initial Version and Version 1 of Ticket #23798, comment 30


Ignore:
Timestamp:
Jul 13, 2021, 10:49:22 PM (19 months ago)
Author:
dimpase
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #23798, comment 30

    initial v1  
    11I don’t see how one can make the oracle (the inner LP) inexact, without potentially returning a very wrong answer.
    22
    3 The oracle checks that there is no maximum weight matching of weight >1. Say, we let it error by epsilon, i.e we terminate with oracle returning 1+epsilon. Potentially, there could be K maximum matchings with this weight, if they are disjoint this means that the final error K times epsilon, oops…
     3The oracle checks that there is no maximum weight matching of weight >1. Say, we let it error by epsilon, i.e we terminate with oracle returning 1+epsilon. Potentially, there could be K maximum matchings with this weight, if they are disjoint this means that the final error is K times epsilon, oops…
    44