2 results found
We study a variant of the pessimistic bi-level optimization problem, which comprises constraintsthat must be satis ed for any optimal solution of a subordinate (lower-level) optimization problem. Wepresent conditions that guarantee the existence of optimal solutions in such a problem, and we characterizethe computational complexity of various subclasses of the problem. We then focus on probleminstances that may lack convexity, but that satisfy a certain independence property. We develop convergentapproximations for these instances, and we derive an iterative solution scheme that is reminiscent ofthe discretization techniques used in semi-in nite programming. We also present a computational studythat illustrates the numerical behavior of our algorithm on standard benchmark instances.
When users submit new queries to a distributedstream processing system (DSPS), a query planner must allocatephysical resources, such as CPU cores, memory and networkbandwidth, from a set of hosts to queries. Allocation decisionsmust provide the correct mix of resources required by queries,while achieving an efficient overall allocation to scale in thenumber of admitted queries. By exploiting overlap betweenqueries and reusing partial results, a query planner can conserveresources but has to carry out more complex planning decisions.In this paper, we describe SQPR, a query planner that targetsDSPSs in data centre environments with heterogeneous resources.SQPR models query admission, allocation and reuse as a singleconstrained optimisation problem and solves an approximate versionto achieve scalability. It prevents individual resources frombecoming bottlenecks by re-planning past allocation decisionsand supports different allocation objectives. As our experimentalevaluation in comparison with a state-of-the-art planner showsSQPR makes efficient resource allocation decisions, even with ahigh utilisation of resources, with acceptable overheads.
This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.