Graph balancing: a special case of scheduling unrelated parallel machines
This paper considers a special case of the scheduling problem on unrelated parallel machines. We are given a set of jobs and a group M of machines; each job \(j_i\) has processing time \(p_i\) and it can be processed by at most 2 machines from M. The goal is to schedule the jobs so as to minimize the makespan or completion time of the last job. This problem is equivalent to the graph balancing problem, where we are given a multigraph with weights on the edges and the goal is to orient the edgers so that the maximum total weight of the edges directed towards a vertex is minimum. The main result of the paper is a 1.75 approximation algorithm for the above problem. This algorithm is based on the classic 2-approximation algorithm of \textit{J. K. Lenstra} et al. [Math. Program. 46, No. 3 (A), 259--271 (1990; Zbl 0715.90063)] for scheduling jobs on unrelated parallel machines. However, the authors need to introduce a different integer programming formulation for the problem with a stronger linear programming relaxation than the one used by Lenstra et al. [loc. cit.]. They propose two different linear programs that have integrality gap 1.75. The new programming formulations make use of the fact that no vertex can have more than one large weight edge pointing towards it. A somewhat elaborated rounding procedure allows a solution for any of the above linear programs to be converted into an integral solution of value at most 1.75 times the optimum. The authors also show that for the versions of the problem when machines have different speeds, or when a job can be processed by up to three machines, their linear programming formulations and the configuration linear program of \textit{N. Bansal} and \textit{M. Sviridenko} [``The Santa Claus problem, in: Proceedings of the thirty-eighth annual ACM symposium on theory of computing (STOC 2006). New York, NY: ACM Press. 31--40 (2006; \url{doi:10.1145/1132516.1132522})] have integrality gap of value 2.
- A 3/2-approximation algorithm for the graph balancing problem with two weights
- On some special cases of the restricted assignment problem
- A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges
- Approximation algorithms for the graph balancing problem with two speeds and two job lengths
- Makespan minimization on unrelated parallel machines with a few bags
- A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
- A unified approach to scheduling on unrelated parallel machines
- An approximation algorithm for max-min fair allocation of indivisible goods
- An optimal rounding gives a better approximation for scheduling unrelated machines
- Approximation algorithms for scheduling unrelated parallel machines
- Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
- Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
- Convex programming for scheduling unrelated parallel machines
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
- Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
- GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
- Graph orientation to maximize the minimum weighted outdegree
- scientific article; zbMATH DE number 5764783 (Why is no real title available?)
- Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
- MaxMin allocation via degree lower-bounded arborescences
- Minimizing maximum indegree
- On allocating goods to maximize fairness
- On the Configuration-LP for Scheduling on Unrelated Machines
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- Santa Claus Meets Hypergraph Matchings
- The Santa Claus problem
- Restricted assignment scheduling with resource constraints
- A 3/2-approximation algorithm for the graph balancing problem with two weights
- Estimating the makespan of the two-valued restricted assignment problem
- Scheduling reclaimer operations in the stockyard to minimize makespan
- Upper and lower degree-constrained graph orientation with minimum penalty
- Makespan minimization on unrelated parallel machines with a few bags
- Parameterized orientable deletion
- Approximation algorithms for the graph balancing problem with two speeds and two job lengths
- Degree-constrained graph orientation: maximum satisfaction and minimum violation
- On some special cases of the restricted assignment problem
- On the extension complexity of scheduling polytopes
- Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
- On the configuration-LP for scheduling on unrelated machines
- Simpler and Better Algorithms for Minimum-Norm Load Balancing
- Graph balancing with orientation costs
- Local search breaks 1.75 for graph balancing
- On minimizing the makespan when some jobs cannot be assigned on the same machine
- Parameterized orientable deletion
- Compact LP relaxations for allocation problems
- Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs
- Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments
- Makespan minimization on unrelated parallel machines with a few bags
- Better trees for Santa Claus
- On the existence of funneled orientations for classes of rooted phylogenetic networks
- (In-)approximability results for interval, resource restricted, and low rank scheduling
- Truthful allocation in graphs and hypergraphs
- Efficient approximation algorithms for scheduling problems with uniform p-batch machines and arbitrary processing set restrictions
- Approximate algorithms for unrelated machine scheduling to minimize makespan
- Strong LP formulations for scheduling splittable jobs on unrelated machines
- A note on graph balancing problems with restrictions
This page was built for publication: Graph balancing: a special case of scheduling unrelated parallel machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2441586)
