On the configuration-LP for scheduling on unrelated machines

DOI10.1007/s10951-013-0359-4zbMath1305.68046OpenAlexW1605794186MaRDI QIDQ490331

José Verschae, Andreas Wiese

Publication date: 22 January 2015

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-013-0359-4

zbMATH Keywords

machine schedulingapproximation algorithmsintegrality gapconfiguration-LP

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Related Items (16)

Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines ⋮ Parameterized orientable deletion ⋮ Strong LP formulations for scheduling splittable jobs on unrelated machines ⋮ Approximation algorithms for the graph balancing problem with two speeds and two job lengths ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ Compact LP Relaxations for Allocation Problems ⋮ A 3/2-approximation algorithm for the graph balancing problem with two weights ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Optimal matroid partitioning problems ⋮ Semidefinite and linear programming integrality gaps for scheduling identical machines ⋮ Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs ⋮ Unnamed Item ⋮ Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments ⋮ Unnamed Item ⋮ On minimizing the makespan when some jobs cannot be assigned on the same machine

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• A note on graph balancing problems with restrictions
• Parallel machine scheduling of machine-dependent jobs with unit-length.
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
• An optimal rounding gives a better approximation for scheduling unrelated machines
• The Santa Claus problem
• On the Configuration-LP for Scheduling on Unrelated Machines
• Santa claus meets hypergraph matchings
• Santa Claus Meets Hypergraph Matchings
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• Santa Claus Schedules Jobs on Unrelated Machines
• On Allocating Goods to Maximize Fairness
• MaxMin allocation via degree lower-bounded arborescences
• An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods
• New Constructive Aspects of the Lovász Local Lemma
• The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders

This page was built for publication: On the configuration-LP for scheduling on unrelated machines