Publication

A Quasi-Polynomial Approximation For The Restricted Assignment Problem

Lars Rohwedder
2020
Journal Articles

Résumé

The RESTRICTED ASSIGNMENT problem is a prominent special case of SCHEDULING ON UNRELATED PARALLEL MACHINES. For the strongest known linear programming relaxation, the configuration LP, we improve the nonconstructive bound on its integrality gap from 1.9412 to 1.8334 and significantly simplify the proof. Then we give a constructive variant, yielding a 1.8334-approximation in quasi-polynomial time. This is the first quasi-polynomial algorithm for this problem improving on the long-standing approximation rate of 2.

Source officielle

https://infoscience.epfl.ch/entities/publication/5649ee23-fe5d-4708-94da-27af8360dc5a

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

A Quasi-Polynomial Approximation For The Restricted Assignment Problem

Chattez avec Graph Search

Measuring Linkability of Protected Biometric Templates Using Maximal Leakage

Disagreement and fragmentation in growing groups

A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem