Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Publication

On the Approximability of Single-Machine Scheduling with Precedence Constraints

Ola Nils Anders Svensson
2011
Journal Articles

Résumé

We consider the single-machine scheduling problem to minimize the weighted sum of completion times under precedence constraints. In a series of recent papers, it was established that this scheduling problem is a special case of minimum weighted vertex cover.

Source officielle

Ola Nils Anders Svensson
2011
Journal Articles

Résumé

Source officielle

Concepts associés (9)

Scheduling (production processes)

Scheduling is the process of arranging, controlling and optimizing work and workloads in a production process or manufacturing process. Scheduling is used to allocate plant and machinery resources, plan human resources, plan production processes and purchase materials. It is an important tool for manufacturing and engineering, where it can have a major impact on the productivity of a process. In manufacturing, the purpose of scheduling is to keep due dates of customers and then minimize the production time and costs, by telling a production facility when to make, with which staff, and on which equipment.

Ordonnancement dans les systèmes d'exploitation

Dans les systèmes d'exploitation, l’ordonnanceur est le composant du noyau du système d'exploitation choisissant l'ordre d'exécution des processus sur les processeurs d'un ordinateur. En anglais, l'ordonnanceur est appelé scheduler. Un processus a besoin de la ressource processeur pour exécuter des calculs; il l'abandonne quand se produit une interruption, etc. De nombreux anciens processeurs ne peuvent effectuer qu'un traitement à la fois.

Vertex cover

In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimization problem. It is NP-hard, so it cannot be solved by a polynomial-time algorithm if P ≠ NP. Moreover, it is hard to approximate – it cannot be approximated up to a factor smaller than 2 if the unique games conjecture is true. On the other hand, it has several simple 2-factor approximations.

Afficher plus

Publications associées (10)

Afficher plus

On the Approximability of Single-Machine Scheduling with Precedence Constraints

Graph Chatbot

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon

New Graph Algorithms via Polyhedral Techniques