Motivated by applications in grid computing and project management, we study multiprocessor scheduling in scenarios where there is uncertainty in the successful execution of jobs when assigned to processors. We consid...
详细信息
Motivated by applications in grid computing and project management, we study multiprocessor scheduling in scenarios where there is uncertainty in the successful execution of jobs when assigned to processors. We consider the problem of multiprocessor scheduling under uncertainty, in which we are given n unit-time jobs and m machines, a directed acyclic graph C giving the dependencies among the jobs, and for every job j and machine i, the probability p (ij) of the successful completion of job j when scheduled on machine i in any given particular step. The goal of the problem is to find a schedule that minimizes the expected makespan, that is, the expected time at which all of the jobs are completed. The problem of multiprocessor scheduling under uncertainty was introduced by Malewicz and was shown to be NP-hard even when all the jobs are independent. In this paper, we present polynomial-time approximation algorithms for the problem, for special cases of the dag C. We obtain an O(log n)-approximation for the case of independent jobs, an O(log mlog nlog (n+m)/log log (n+m))-approximation when C is a collection of disjoint chains, an O(log mlog (2) n)-approximation when C is a collection of directed out- or in-trees, and an O(log mlog (2) nlog (n+m)/log log (n+m))-approximation when C is a directed forest.
In this paper, we present new approximation results for the offline problem of single machine scheduling with sequence-independent set-ups and item availability, where the jobs to be scheduled are independent (i.e., h...
详细信息
In this paper, we present new approximation results for the offline problem of single machine scheduling with sequence-independent set-ups and item availability, where the jobs to be scheduled are independent (i.e., have no precedence constraints) and have a common release time. We present polynomial-time approximation algorithms for two versions of this problem. In the first version, the input includes a weight for each job, and the goal is to minimize the total weighted completion time. On any input, our algorithm produces a schedule whose total weighted completion time is within a factor 2 of optimal for that input. In the second version, the input includes a due date for each job, and the goal is to minimize the maximum lateness of any job. On any input, our algorithm produces a schedule with the following performance guarantee: the maximum lateness of a job is at most the maximum lateness of the optimal schedule on a machine that runs at half the speed of our machine. (C) 2007 Elsevier B.V. All rights reserved.
We study the problem of non-preemptively scheduling n independent sequential jobs on a system of m identical parallel machines in the presence of reservations, where m is constant. This setting is practically relevant...
详细信息
We study the problem of non-preemptively scheduling n independent sequential jobs on a system of m identical parallel machines in the presence of reservations, where m is constant. This setting is practically relevant because for various reasons, some machines may not be available during specified time intervals. The objective is to minimize the makespan C-max, which is the maximum completion time. The general case of the problem is inapproximable unless P = NP;hence, we study a suitable strongly NP-hard restriction, namely the case where at least one machine is always available. For this setting we contribute approximation schemes, complemented by inapproximability results. The approach is based on algorithms for multiple subset sum problems;our technique yields a PTAS which is best possible in the sense that an FPTAS is ruled out unless P = NP. The PTAS presented here is the first one for the problem under consideration;so far, not even for well-known special cases approximation schemes have been proposed. Furthermore we derive a low cost algorithm with a constant approximation ratio and discuss FPTASes for special cases as well as the complexity of the problem if m is part of the input.
Given a set P of n points in the plane, we consider the problem of covering P with a minimum number of unit disks. This problem is known to be NP-hard. We present a simple 4-approximation algorithm for this problem wh...
详细信息
Given a set P of n points in the plane, we consider the problem of covering P with a minimum number of unit disks. This problem is known to be NP-hard. We present a simple 4-approximation algorithm for this problem which runs in O (n log n)-time. We also show how to extend this algorithm to other metrics, and to three dimensions. (C) 2016 Elsevier B.V. All rights reserved.
LetR be a rectangle and letP be a set of points located insideR. Our problem consists of introducing a set of line segments of least total length to partition the interior ofR into rectangles. Each rectangle in a vali...
详细信息
LetR be a rectangle and letP be a set of points located insideR. Our problem consists of introducing a set of line segments of least total length to partition the interior ofR into rectangles. Each rectangle in a valid partition must not contain points fromP as interior points. Since this partitioning problem is computationally intractable (NP-hard), we present efficient approximation algorithms for its solution. The solutions generated by our algorithms are guaranteed to be within three times the optimal solution value. Our algorithm also generates solutions within four times the optimal solution value whenR is a rectilinear polygon. Our algorithm can be generalized to generate good approximation solutions for the case whenR is a rectilinear polygon, there are rectilinear polygonal holes, and the sum of the length of the boundaries is not more than the sum of the length of the edges in an optimal solution.
We study the distance constrained vehicle routing problem (DVRP) (Laporte et al., Networks 14 (1984), 47-61, Li et al., Oper Res 40 (1992), 790-799): given a set of vertices in a metric space, a specified depot, and a...
详细信息
We study the distance constrained vehicle routing problem (DVRP) (Laporte et al., Networks 14 (1984), 47-61, Li et al., Oper Res 40 (1992), 790-799): given a set of vertices in a metric space, a specified depot, and a distance bound D, find a minimum cardinality set of tours originating at the depot that covers all vertices, such that each tour has length at most D. This problem is NP-complete, even when the underlying metric is induced by a weighted star. Our main result is a 2-approximation algorithm for DVRP on tree metrics;we also show that no approximation factor better than 1.5 is possible unless P = NP. For the problem on general metrics, we present a (O(log 1/epsilon), 1 + epsilon)-bicriteria approximation algorithm: i.e., for any epsilon > 0, it obtains a solution violating the length bound by a 1 + epsilon factor while using at most O(log 1/epsilon) times the optimal number of vehicles. (C) 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 59(2), 209-214 2012
The max-bisection problem is to find a partition of the vertices of a graph into two equal size subsets that maximizes the number of edges with endpoints in both subsets. We obtain new improved approximation ratios fo...
详细信息
The max-bisection problem is to find a partition of the vertices of a graph into two equal size subsets that maximizes the number of edges with endpoints in both subsets. We obtain new improved approximation ratios for the max-bisection problem on the low degree k-regular graphs for 3 less than or equal to k less than or equal to 8, by deriving some improved transformations from a maximum cut intofrom a maximum bisection. In the case of three regular graphs we obtain an approximation ratio of 0.854, and in the case of four and five regular graphs, approximation ratios of 0.805, and 0.812, respectively.
In this paper, we develop approximation algorithms for a few node deletion problems when the input is restricted to be a bipartite graph. We look at node deletion problems for non-trivial properties which can be chara...
详细信息
In this paper, we develop approximation algorithms for a few node deletion problems when the input is restricted to be a bipartite graph. We look at node deletion problems for non-trivial properties which can be characterized by forbidden structure which has a bounded intersection with both the bipartitions. The approximation factors obtained directly depend upon the size of the largest such intersection. Special instances of this general problem include problems such as the MINIMUM CHAIN VERTEX DELETION, MINIMUM DISSOCIATION VERTEX DELETION, MINIMUM BIPARTITE CLAW VERTEX DELETION, MINIMUM BI-COMPLEMENT VERTEX DELETION and MINIMUM BIPARTITE THRESHOLD VERTEX DELETION problems. The algorithms are based upon the techniques of linear programming and iterative rounding. We also use the node deletion algorithms to marginally improve the trivial approximation factor for complementary problem of determining the size of the maximum sized vertex induced subgraph lying in the given graph class and prove the APX-completeness of all of these problems. (C) 2014 Elsevier B.V. All rights reserved.
As a fundamental optimization problem, the vehicle routing problem has wide application backgrounds and has been paid lots of attentions in past decades. In this paper we study its applications in data gathering and w...
详细信息
As a fundamental optimization problem, the vehicle routing problem has wide application backgrounds and has been paid lots of attentions in past decades. In this paper we study its applications in data gathering and wireless energy charging for wireless sensor networks, by devising improved approximation algorithms for it and its variants. The key ingredients in the algorithm design include exploiting the combinatorial properties of the problems and making use of tree decomposition and minimum weighted maximum matching techniques. Specifically, given a metric complete graph G and an integer k > 0, we consider rootless, uncapacitated rooted, and capacitated rooted min-max cycle cover problems in G with an aim to find k rootless (or rooted) edge-disjoint cycles covering the vertices in V such that the maximum cycle weight among the k cycles is minimized. For each of the mentioned problems, we develop an improved approximate solution. That is, for the rootless min-max cycle cover problem, we develop a (5 1/3 + epsilon)-approximation algorithm;for the uncapacitated rooted min-max cycle cover problem, we devise a (6 1/3 + epsilon)-approximation algorithm;and for the capacitated rooted min-max cycle cover problem, we propose a (7 + epsilon)-approximation algorithm. These algorithms improve the best existing approximation ratios of the corresponding problems 6 + epsilon, 7 + epsilon, and 13 + epsilon, respectively, where epsilon is a constant with 0 < + < 1. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results show that the actual approximation ratios delivered by the proposed algorithms are always no more than 2, much better than their analytical counterparts.
Compressive sensing (CS) states that a sparse signal can be recovered from a small number of linear measurements, and that this recovery can be performed efficiently in polynomial time. The framework of model-based CS...
详细信息
Compressive sensing (CS) states that a sparse signal can be recovered from a small number of linear measurements, and that this recovery can be performed efficiently in polynomial time. The framework of model-based CS (model-CS) leverages additional structure in the signal and provides new recovery schemes that can reduce the number of measurements even further. This idea has led to measurement-efficient recovery schemes for a variety of signal models. However, for any given model, model-CS requires an algorithm that solves the model-projection problem: given a query signal, report the signal in the model that is closest to the query signal. Often, this optimization can be computationally very expensive. Moreover, an approximation algorithm is not sufficient for this optimization to provably succeed. As a result, the model-projection problem poses a fundamental obstacle for extending model-CS to many interesting classes of models. In this paper, we introduce a new framework that we call approximation-tolerant model-CS. This framework includes a range of algorithms for sparse recovery that require only approximate solutions for the model-projection problem. In essence, our work removes the aforementioned obstacle to model-CS, thereby extending model-CS to a much wider class of signal models. Interestingly, all our algorithms involve both the minimization and the maximization variants of the model-projection problem. We instantiate this new framework for a new signal model that we call the constrained earth mover distance (CEMD) model. This model is particularly useful for signal ensembles, where the positions of the nonzero coefficients do not change significantly as a function of spatial (or temporal) location. We develop novel approximation algorithms for both the maximization and the minimization versions of the model-projection problem via graph optimization techniques. Leveraging these algorithms and our framework results in a nearly sample-optimal sparse recove
暂无评论