fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Claimed bound of 0.883 is True
https://ideone.com/pnbjas
language:
Python 3 (python  3.9.5)
created:
233 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!