fork download
  1. import numpy as np
  2. from scipy.optimize import minimize
  3. import scipy
  4.  
  5. m = 10 #m parameter from paper
  6. comp_ratio = 0.883 #The competitive ratio we claim.
  7.  
  8. def lamb(j, cs):
  9. return 1/m * sum(cs[i] for i in range(1, j))
  10.  
  11.  
  12. def fj(j, cs, l):
  13. part1 = 1-np.exp(-lamb(j, cs))
  14. part2 = 0
  15. for k in range(j, m+1):
  16. term = np.exp(- lamb(k, cs))
  17. term *= np.exp(-1*(m+1)/m*cs[k])
  18. inner = (m*np.exp(cs[k])*l*(np.exp(cs[k]/m)-1)*(2*cs[k]-l)
  19. + cs[k]*l*np.exp(k*cs[k]/m)*(l-cs[k]))
  20. term *= inner
  21. term /= (m*cs[k]**2)
  22. part2 += term
  23. return part1+part2
  24.  
  25.  
  26. def verify_competitive_ratio(cs):
  27. for i in range(1, len(cs)):
  28. if cs[i]<cs[i-1]:
  29. raise Exception("cs should be sorted in ascending order")
  30.  
  31. defeciency = 1 # This is the min value of f_j(c1, ..., cm, \ell') - comp_ratio*(1-e^(-\ell'))
  32. #This needs to be >=0 by the end of execution so that the bound we claim
  33. #Is truthful.
  34.  
  35. defeciency = min(defeciency, 1-np.exp(-1/m * float(sum(cs))) - comp_ratio)
  36. for j in range(1, m+1):
  37. ell_bounds = [(cs[j-1],cs[j])]
  38.  
  39. res = scipy.optimize.shgo(lambda l: fj(j, cs, l[0]) - comp_ratio*(1-np.exp(-l[0])),
  40. iters=10,
  41. bounds=ell_bounds, options={'disp':False, 'f_tol':1e-9})
  42.  
  43. """As a sanity check, make sure res.fun <= some values in the middle to make sure minimization worked"""
  44. for xx in np.linspace(ell_bounds[0][0], ell_bounds[0][1], 10000):
  45. assert res.fun <= fj(j, cs, xx) - comp_ratio*(1-np.exp(-xx)), (j, ell_bounds, xx, res)
  46. """End of sanity check"""
  47. defeciency = min(defeciency, res.fun)
  48.  
  49. if defeciency>=0:
  50. print(f"Claimed bound of {comp_ratio} is True")
  51. else:
  52. print(f"Claimed bound of {comp_ratio} is False")
  53.  
  54.  
  55. cs = [0., 0.35598315, 0.56202538, 0.86407969, 1.22558122, 1.65459166,
  56. 2.14361195, 2.5868228 , 3.07922161, 4.0722262 , 5.21637928]
  57.  
  58. verify_competitive_ratio(cs)
Success #stdin #stdout 1.76s 66048KB
stdin
Standard input is empty
stdout
Claimed bound of 0.883 is True