fork download
  1. import numpy as np
  2. from scipy.optimize import minimize
  3. import scipy
  4.  
  5.  
  6.  
  7. m = 10 #m parameter from paper
  8.  
  9. def lamb(j, cs):
  10. return 1/m * sum(cs[i] for i in range(1, j))
  11.  
  12.  
  13. #Computes f_j(alphas, alphat) in time O(m^2)
  14. def fj(j, cs, l):
  15. part1 = 1-np.exp(-lamb(j, cs))
  16. part2 = 0
  17. for k in range(j, m+1):
  18. part2 += np.exp(-lamb(k, cs)) * (1-np.exp(-cs[k]/m)) * l/cs[k]
  19. return part1+part2
  20.  
  21.  
  22. def evaluate_competitive_ratio(cs):
  23. for i in range(1, len(cs)):
  24. if cs[i]<cs[i-1]:
  25. raise Exception("Values are not increasing")
  26.  
  27. competitive_ratio = 1-np.exp(-1/m * float(sum(cs)) )
  28. competitive_ratio = min(sum([np.exp(-lamb(k, cs)) * (1-np.exp(-cs[k]/m))/cs[k] for k in range(1, m+1)]), competitive_ratio)
  29.  
  30. for j in range(2, m+1):
  31. alphat_bounds = [(cs[j-1],cs[j])]
  32. x0 = (cs[j-1]+cs[j])/2.0
  33.  
  34. res = minimize(lambda l: fj(j, cs, l[0])/(1-np.exp(-l[0])),
  35. x0=x0,
  36. bounds=alphat_bounds)
  37. """As a sanity check, make sure res.fun <= a few values in the middle to make sure minimization worked"""
  38. for xx in np.linspace(alphat_bounds[0][0], alphat_bounds[0][1], 1000):
  39. assert res.fun <= fj(j, cs, xx)/(1-np.exp(-xx)), (alphat_bounds, xx, res)
  40.  
  41. competitive_ratio = min(competitive_ratio, res.fun)
  42. return competitive_ratio
  43.  
  44. cs = [0. , 0.07077646, 0.2268947 , 0.42146915, 0.60679691,
  45. 0.8570195 , 1.17239753, 1.51036256, 1.9258193 , 2.88381902,
  46. 3.97363258]
  47. c = evaluate_competitive_ratio(cs)
  48. print(c)
  49.  
Success #stdin #stdout 0.35s 52836KB
stdin
Standard input is empty
stdout
0.7406393033097848