import numpy as np
from scipy.optimize import minimize
import scipy
m = 10 #m parameter from paper
comp_ratio = 0.883 #The competitive ratio we claim.
def lamb(j, cs):
return 1/m * sum(cs[i] for i in range(1, j))
def fj(j, cs, l):
part1 = 1-np.exp(-lamb(j, cs))
part2 = 0
for k in range(j, m+1):
term = np.exp(- lamb(k, cs))
term *= np.exp(-1*(m+1)/m*cs[k])
inner = (m*np.exp(cs[k])*l*(np.exp(cs[k]/m)-1)*(2*cs[k]-l)
+ cs[k]*l*np.exp(k*cs[k]/m)*(l-cs[k]))
term *= inner
term /= (m*cs[k]**2)
part2 += term
return part1+part2
def verify_competitive_ratio(cs):
for i in range(1, len(cs)):
if cs[i]<cs[i-1]:
raise Exception("cs should be sorted in ascending order")
defeciency = 1 # This is the min value of f_j(c1, ..., cm, \ell') - comp_ratio*(1-e^(-\ell'))
#This needs to be >=0 by the end of execution so that the bound we claim
#Is truthful.
defeciency = min(defeciency, 1-np.exp(-1/m * float(sum(cs))) - comp_ratio)
for j in range(1, m+1):
ell_bounds = [(cs[j-1],cs[j])]
res = scipy.optimize.shgo(lambda l: fj(j, cs, l[0]) - comp_ratio*(1-np.exp(-l[0])),
iters=10,
bounds=ell_bounds, options={'disp':False, 'f_tol':1e-9})
"""As a sanity check, make sure res.fun <= some values in the middle to make sure minimization worked"""
for xx in np.linspace(ell_bounds[0][0], ell_bounds[0][1], 10000):
assert res.fun <= fj(j, cs, xx) - comp_ratio*(1-np.exp(-xx)), (j, ell_bounds, xx, res)
"""End of sanity check"""
defeciency = min(defeciency, res.fun)
if defeciency>=0:
print(f"Claimed bound of {comp_ratio} is True")
else:
print(f"Claimed bound of {comp_ratio} is False")
cs = [0., 0.35598315, 0.56202538, 0.86407969, 1.22558122, 1.65459166,
2.14361195, 2.5868228 , 3.07922161, 4.0722262 , 5.21637928]
verify_competitive_ratio(cs)
aW1wb3J0IG51bXB5IGFzIG5wCmZyb20gc2NpcHkub3B0aW1pemUgaW1wb3J0IG1pbmltaXplIAppbXBvcnQgc2NpcHkgCgptID0gMTAgI20gcGFyYW1ldGVyIGZyb20gcGFwZXIKY29tcF9yYXRpbyA9IDAuODgzICNUaGUgY29tcGV0aXRpdmUgcmF0aW8gd2UgY2xhaW0uCgpkZWYgbGFtYihqLCBjcyk6CiAgICByZXR1cm4gMS9tICogc3VtKGNzW2ldIGZvciBpIGluIHJhbmdlKDEsIGopKQoKICAgIApkZWYgZmooaiwgY3MsIGwpOgogICAgcGFydDEgPSAxLW5wLmV4cCgtbGFtYihqLCBjcykpCiAgICBwYXJ0MiA9IDAKICAgIGZvciBrIGluIHJhbmdlKGosIG0rMSk6CiAgICAgICAgdGVybSA9IG5wLmV4cCgtIGxhbWIoaywgY3MpKQogICAgICAgIHRlcm0gKj0gbnAuZXhwKC0xKihtKzEpL20qY3Nba10pCiAgICAgICAgaW5uZXIgPSAobSpucC5leHAoY3Nba10pKmwqKG5wLmV4cChjc1trXS9tKS0xKSooMipjc1trXS1sKSAKICAgICAgICAgICAgICAgICAgICArIGNzW2tdKmwqbnAuZXhwKGsqY3Nba10vbSkqKGwtY3Nba10pKQogICAgICAgIHRlcm0gKj0gaW5uZXIgCiAgICAgICAgdGVybSAvPSAobSpjc1trXSoqMikKICAgICAgICBwYXJ0MiArPSB0ZXJtCiAgICByZXR1cm4gcGFydDErcGFydDIKCgpkZWYgdmVyaWZ5X2NvbXBldGl0aXZlX3JhdGlvKGNzKToKICAgIGZvciBpIGluIHJhbmdlKDEsIGxlbihjcykpOgogICAgICAgIGlmIGNzW2ldPGNzW2ktMV06CiAgICAgICAgICAgIHJhaXNlIEV4Y2VwdGlvbigiY3Mgc2hvdWxkIGJlIHNvcnRlZCBpbiBhc2NlbmRpbmcgb3JkZXIiKQogICAgCiAgICBkZWZlY2llbmN5ID0gMSAjIFRoaXMgaXMgdGhlIG1pbiB2YWx1ZSBvZiBmX2ooYzEsIC4uLiwgY20sIFxlbGwnKSAtIGNvbXBfcmF0aW8qKDEtZV4oLVxlbGwnKSkKICAgICAgICAgICAgICAgICAgICAjVGhpcyBuZWVkcyB0byBiZSA+PTAgYnkgdGhlIGVuZCBvZiBleGVjdXRpb24gc28gdGhhdCB0aGUgYm91bmQgd2UgY2xhaW0KICAgICAgICAgICAgICAgICAgICAjSXMgdHJ1dGhmdWwuCiAgICAKICAgIGRlZmVjaWVuY3kgPSBtaW4oZGVmZWNpZW5jeSwgMS1ucC5leHAoLTEvbSAqIGZsb2F0KHN1bShjcykpKSAtIGNvbXBfcmF0aW8pCiAgICBmb3IgaiBpbiByYW5nZSgxLCBtKzEpOiAKICAgICAgICBlbGxfYm91bmRzID0gWyhjc1tqLTFdLGNzW2pdKV0KICAgICAgICAKICAgICAgICByZXMgPSBzY2lweS5vcHRpbWl6ZS5zaGdvKGxhbWJkYSBsOiBmaihqLCBjcywgbFswXSkgLSBjb21wX3JhdGlvKigxLW5wLmV4cCgtbFswXSkpLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGl0ZXJzPTEwLAogICAgICAgICAgICAgICAgICAgICAgIGJvdW5kcz1lbGxfYm91bmRzLCBvcHRpb25zPXsnZGlzcCc6RmFsc2UsICdmX3RvbCc6MWUtOX0pCiAgICAgICAgCiAgICAgICAgIiIiQXMgYSBzYW5pdHkgY2hlY2ssIG1ha2Ugc3VyZSByZXMuZnVuIDw9IHNvbWUgdmFsdWVzIGluIHRoZSBtaWRkbGUgdG8gbWFrZSBzdXJlIG1pbmltaXphdGlvbiB3b3JrZWQiIiIKICAgICAgICBmb3IgeHggaW4gbnAubGluc3BhY2UoZWxsX2JvdW5kc1swXVswXSwgZWxsX2JvdW5kc1swXVsxXSwgMTAwMDApOgogICAgICAgICAgICBhc3NlcnQgcmVzLmZ1biA8PSBmaihqLCBjcywgeHgpIC0gY29tcF9yYXRpbyooMS1ucC5leHAoLXh4KSksIChqLCBlbGxfYm91bmRzLCB4eCwgcmVzKQogICAgICAgICIiIkVuZCBvZiBzYW5pdHkgY2hlY2siIiIKICAgICAgICBkZWZlY2llbmN5ID0gbWluKGRlZmVjaWVuY3ksIHJlcy5mdW4pCiAgICAKICAgIGlmIGRlZmVjaWVuY3k+PTA6CiAgICAgICAgcHJpbnQoZiJDbGFpbWVkIGJvdW5kIG9mIHtjb21wX3JhdGlvfSBpcyBUcnVlIikKICAgIGVsc2U6CiAgICAgICAgcHJpbnQoZiJDbGFpbWVkIGJvdW5kIG9mIHtjb21wX3JhdGlvfSBpcyBGYWxzZSIpCiAgICAKICAgIApjcyA9IFswLiwgMC4zNTU5ODMxNSwgMC41NjIwMjUzOCwgMC44NjQwNzk2OSwgMS4yMjU1ODEyMiwgMS42NTQ1OTE2NiwKICAgICAgIDIuMTQzNjExOTUsIDIuNTg2ODIyOCAsIDMuMDc5MjIxNjEsIDQuMDcyMjI2MiAsIDUuMjE2Mzc5MjhdCgp2ZXJpZnlfY29tcGV0aXRpdmVfcmF0aW8oY3Mp