Using fractional primal-dual to schedule split intervals with demands
We consider the problem of scheduling jobs that are given as groups of non-intersecting intervals on the real line. Each job \(j\) is associated with a \(t\)-interval (which consists of up to \(t\) segments, for some \(t\geq 1\)), a demand, \(d_j\in[0,1]\), and a weight, \(w(j)\). A feasible schedule is a collection of jobs such that, for every \(s\in\mathbb R\), the total demand of the jobs in the schedule whose \(t\)-interval contains \(s\) does not exceed 1. Our goal is to find a feasible schedule that maximizes the total weight of scheduled jobs. We present a \(6t\)-approximation algorithm for this problem that uses a novel extension of the primal-dual schema called fractional primal-dual. The first step in a fractional primal-dual \(r\)-approximation algorithm is to compute an optimal solution, \(x^*\), of an LP relaxation of the problem. Next, the algorithm produces an integral primal solution \(x\), and a new LP, denoted by \(P'\), that has the same objective function as the original problem, but contains inequalities that may not be valid with respect to the original problem. Moreover, \(x^*\) is a feasible solution of \(P'\). The algorithm also computes a solution \(y\) to the dual of \(P'\). The solution \(x\) is \(r\)-approximate, since its weight is bounded by the value of \(y\) divided by \(r\). We present a fractional local ratio interpretation of our \(6t\)-approximation algorithm. We also discuss the connection between fractional primal-dual and the fractional local ratio technique. Specifically, we show that the former is the primal-dual manifestation of the latter.
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- A General Approximation Technique for Constrained Forest Problems
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- A unified approach to approximating resource allocation and scheduling
- Admission control in networks with advance reservations
- From valid inequalities to heuristics: A unified view of primal-dual approximation algorithms in covering problems
- Greedy approximations of independent sets in low degree graphs
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3869066 (Why is no real title available?)
- scientific article; zbMATH DE number 1185295 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1305512 (Why is no real title available?)
- scientific article; zbMATH DE number 2086936 (Why is no real title available?)
- scientific article; zbMATH DE number 2119734 (Why is no real title available?)
- Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
- On approximation properties of the Independent set problem for degree 3 graphs
- On the complexity of approximating \(k\)-dimensional matching
- On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
- On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
- One for the price of two: a unified approach for approximating covering problems
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Optimization, approximation, and complexity classes
- Recognizing graphs with fixed interval number is NP-complete
- The primal-dual method for approximation algorithms
This page was built for publication: Using fractional primal-dual to schedule split intervals with demands
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q865744)
