Cloud services require the allocation of scarce resources to multiple user requests (jobs) in a setting that facilitates preemption and migration, while respecting resource and timing constraints. This gives rise to t...
详细信息
ISBN:
(纸本)9781450357999
Cloud services require the allocation of scarce resources to multiple user requests (jobs) in a setting that facilitates preemption and migration, while respecting resource and timing constraints. This gives rise to the following variants of the classical resource allocation problem (RAP). The input is a set J of jobs and a set M of homogeneous hosts, each has available amount of some resource. A job is associated with a release time, a due date, a weight and a given length, as well as its resource requirement. A feasible schedule is an allocation of the resource to a subset of the jobs, satisfying the job release times/due dates as well as the resource constraints. We consider two essential objectives: throughput maximization (MaxT), which seeks a maximum weight subset of the jobs that can be feasibly scheduled on the hosts in M, and resource minimization (MinR), that is finding the minimum number of (homogeneous) hosts needed to feasibly schedule all jobs. Both problems are known to be NP-hard. We address these fundamental problems, which have been studied previously in the non-preemptive model, and develop novel techniques for tackling them. In the full version of the paper, we present an Omega(1)-approximation algorithm for MaxT, assuming there is sufficient slack for each job to be completed in its time window. For MinR we study a more general setting with d resources and derive an O(log d)-approximation for any fixed d >= 1, under the assumption that time windows are not too small. This assumption can be removed leading to a slightly worse ratio of O(log d log* T), where T is the maximum due date of any job.
We consider some classical and quantum approximate optimization algorithms with bounded depth. First, we define a class of "local" classical optimization algorithms and show that a single step version of the...
详细信息
Let G = (V, E) be a complete undirected graph with vertex set V, edge set E and let H = be a hypergraph, where S is a set of not necessarily disjoint clusters S1, …, Sm, Si ⊆ V ∀i ∈ {1, …, m}. The clustered traveli...
详细信息
We give approximation algorithms for the edge expansion and sparsest cut with product demands problems on directed hypergraphs, which subsume previous graph models such as undirected hypergraphs and directed normal gr...
详细信息
ISBN:
(纸本)9783319947761;9783319947754
We give approximation algorithms for the edge expansion and sparsest cut with product demands problems on directed hypergraphs, which subsume previous graph models such as undirected hypergraphs and directed normal graphs. Using an SDP formulation adapted to directed hypergraphs, we apply the SDP primal-dual framework by Arora and Kale (JACM 2016) to design polynomial-time algorithms whose approximation ratios match those of algorithms previously designed for more restricted graph models. Moreover, we have deconstructed their framework and simplified the notation to give a much cleaner presentation of the algorithms.
Kernel based methods provide a way to reconstruct potentially high-dimensional functions from meshfree samples, i.e., sampling points and corresponding target values. A crucial ingredient for this to be successful is ...
详细信息
approximation algorithms for constraint satisfaction problems (CSPs) are a central direction of study in theoretical computer science. In this work, we study classical product state approximation algorithms for a phys...
详细信息
Experimental design is a classical area in statistics [21] and has also found new applications in machine learning[2]. In the combinatorial experimental design problem, the aim is to estimate an unknown m-dimensional ...
详细信息
ISBN:
(纸本)9781611975031
Experimental design is a classical area in statistics [21] and has also found new applications in machine learning[2]. In the combinatorial experimental design problem, the aim is to estimate an unknown m-dimensional vector x from linear measurements where a Gaussian noise is introduced in each measurement. The goal is to pick k out of the given n experiments so as to make the most accurate estimate of the unknown parameter x. Given a set S of chosen experiments, the most likelihood estimate x' can be obtained by a least squares computation. One of the robust measures of error estimation is the D-optimality criterion [27] which aims to minimize the generalized variance of the estimator. This corresponds to minimizing the volume of the standard confidence ellipsoid for the estimation error x - x'. The problem gives rise to two natural variants depending on whether repetitions of experiments is allowed or not. The latter variant, while being more general, has also found applications in geographical location of sensors [19]. We show a close connection between approximation algorithms for the D-optimal design problem and constructions of approximately m-wise positively correlated distributions. This connection allows us to obtain a 1/e-approximation for the D-optimal design problem with and without repetitions giving the first constant factor approximation for the problem. We then consider the case when the number of experiments chosen is much larger than the dimension m and show one can obtain (1-epsilon)-approximation if k >= 2m/epsilon when repetitions are allowed and if k = O(m/epsilon + 1/epsilon(2) . log 1/epsilon) when no repetitions are allowed improving on previous work.
Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under variou...
详细信息
We give new approximation algorithms for the submodular joint replenishment problem and the inventory routing problem, using an iterative rounding approach. In both problems, we are given a set of N items and a discre...
详细信息
Some of the most fundamental and well-studied graph parameters are the Diameter (the largest shortest paths distance) and Radius (the smallest distance for which a "center" node can reach all other nodes). T...
详细信息
暂无评论