All-norm approximation algorithms

Y. Azar, L. Epstein, Y. Richter, G.J. Woeginger

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    8 Citaten (Scopus)


    A major drawback in optimization problems and in particular in scheduling problems is that for every measure there may be a different optimal solution. In many cases the various measures are different l p norms. We address this problem by introducing the concept of an All-norm ¿-approximation algorithm, which supplies one solution that guarantees ¿-approximation to all l p norms simultaneously. Specifically, we consider the problem of scheduling in the restricted assignment model, where there are m machines and n jobs, each is associated with a subset of the machines and should be assigned to one of them. Previous work considered approximation algorithms for each norm separately. Lenstra et al. [12] showed a 2-approximation algorithm for the problem with respect to the l8 norm. For any fixed l p norm the previously known approximation algorithm has a performance of ¿(p). We provide an all-norm 2-approximation polynomial algorithm for the restricted assignment problem. On the other hand, we show that for any given l p norm (p > 1) there is no PTAS unless P=NP by showing an APX-hardness result. We also show for any given l p norm a FPTAS for any fixed number of machines.
    Originele taal-2Engels
    TitelAlgorithm Theory - SWAT 2002 (Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, Turku, Finland, July 3-5, 2002)
    RedacteurenM. Penttonen, E.M. Schmidt
    Plaats van productieBerlin
    ISBN van geprinte versie3-540-43866-1
    StatusGepubliceerd - 2002

    Publicatie series

    NaamLecture Notes in Computer Science
    ISSN van geprinte versie0302-9743


    Duik in de onderzoeksthema's van 'All-norm approximation algorithms'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit