math - Handling rounding errors of exponential function in convex optimization for scheduling web crawler -


i writing web crawler scheduler , have run problems. first describe how i'm trying find optimal schedule when crawler visiting page , present problem.

scheduler definition

scheduler based on paper "optimal crawling strategies web search engines" j.wolf. paper proposes update times of web pages follow exponential distribution parameter λ. problem finding optimal number of times xi, page i crawled in time interval [0,t]. function proposed is:

f

because function convex , input arguments xi discrete kind of problem can solved using algorithm suggested fredrerickson , johnson in "the complexity of selection , ranking in x + y , matrices sorted columns", has time complexity o(max{n, log(r/n)}). optimization algorithm solves problem finding n-th element in [rxn] matrix element @ position (i, j) equal derivation of j function input argument x = i, derivation dj(xi) equal to:

d_min

because function fi convex means function di has property monotonically increasing (matrix has sorted columns).

problems

i run problems when evaluating derivation, because of rounding errors d(x+1) - d(x), did not have guarantee greater or equal 0, , i'm not sure values got optimizer optional values. rounding errors happen because value of x can positive integers in range of 0 few billions, therefor exponent in function f either big negative number or extremely small number (-5000).

failed attempts

the first thing tried, downloaded arbitrary precision library. solved problem overhead of library big.

the second thing tried expanded d , got function like:

d_expanded

and tried compare dj(xi) , dk(xw) comparing terms individually , try deduce dj bigger or smaller or greater dk. if compare derivation solve problem because optimization algorithm not need concrete values, instead need relations between values. couldn't find solution because term w.

i tried looking @ log(dj(xi)) because log preserves function monotony, log had rounding errors , couldn't compare log(dj) , log(dk) without computing final values.

if has other solution potentially work graceful.


Comments

Post a Comment

Popular posts from this blog

Is there a better way to structure post methods in Class Based Views -

i'm using class based views in django , never specify url in ajax calls , omit action parameter in form because know these requests go through post method of class based view. notice view - profile page make many requests depending on user updating on page - post method become convoluted , if/else mess example: def post(self, request, *args, **kwargs): # handle user changing available date if request.post.get('availabledate') != none: self.updateavailabledate(request) return jsonresponse({'result':'success'}) if request.post.get('newprojectname') != none: creative_user = creativeuserprofile.objects.get(id = request.user.id) project = project.create_project(creative_user, request.post['newprojectname']) project.save() return jsonresponse({'projectid': project.id }) if request.post.get('projectimage') != none , request.files['file']: proj
Read more

performance - Why is XCHG reg, reg a 3 micro-op instruction on modern Intel architectures? -

i'm doing micro-optimization on performance critical part of code , came across sequence of instructions (in at&t syntax): add %rax, %rbx mov %rdx, %rax mov %rbx, %rdx i thought had use case xchg allow me shave instruction , write: add %rbx, %rax xchg %rax, %rdx however, dimay found agner fog's instruction tables , xchg 3 micro-op instruction 2 cycle latency on sandy bridge, ivy bridge, broadwell, haswell , skylake. 3 whole micro-ops , 2 cycles of latency! 3 micro-ops throws off 4-1-1-1 cadence , 2 cycle latency makes worse original in best case since last 2 instructions in original might execute in parallel. now... cpu might breaking instruction micro-ops equivalent to: mov %rax, %tmp mov %rdx, %rax mov %tmp, %rdx where tmp anonymous internal register , suppose last 2 micro-ops run in parallel latency 2 cycles. given register renaming occurs on these micro-architectures, though, doesn't make sense me done way. why wouldn't register renamer
Read more

jquery - Responsive Navbar with Sub Navbar -

good day, forgive me nav vocabulary not best. if question confusing apologize. i'm working on navigation bar needs centered on page @ 768px , above. items in nav open (or perhaps toggle) subnav lives directly below. these nav should appear centered on page. i have been able work through responsive portion of nav bar, having main items align vertically , sub nav menu of each item roll out below, , gave them indent separation. working well. however, issue not responsive side, behavior @ width greater 768px. happens toggling menu's sub navigation pushes other main items down page below sub nav. here's code: $(document).ready(function () { //stick in fixed 100% height behind navbar don't wrap $('#slide-nav.navbar-inverse').after($('<div class="inverse" id="navbar-height-col"></div>')); $('#slide-nav.navbar-default').after($('<div id="navbar-height-col"></d
Read more