@prefix dcat: <http://www.w3.org/ns/dcat#> .
@prefix dct: <http://purl.org/dc/terms/> .
@prefix foaf: <http://xmlns.com/foaf/0.1/> .
@prefix vcard: <http://www.w3.org/2006/vcard/ns#> .
@prefix xsd: <http://www.w3.org/2001/XMLSchema#> .

<https://rec.harvest-normandie.data4citizen.com/dataset/oai-hal-hal-00907607v1> a dcat:Dataset ;
    dct:description """
              This paper proposes a way to bring together two seemingly "foreign" domains that are the polynomial approximation and the exact computation for NP-hard problems. We show how one can match ideas from both areas in order to design approximation algorithms achiev- ing ratios unachievable in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation. We then apply these ideas to two famous combinatorial optimiza- tion problems, namely, the MAX INDEPENDENT SET and the MIN VERTEX COVER, as well as to some other problems mainly linked to max independent set by simple approximation preserving reductions.
            """ ;
    dct:identifier "hal-00907607" ;
    dct:issued "2026-05-08T03:44:09.138252"^^xsd:dateTime ;
    dct:language "en" ;
    dct:modified "2026-05-08T03:44:09.138257"^^xsd:dateTime ;
    dct:publisher <https://rec.harvest-normandie.data4citizen.com/organization/cce9db95-46d9-4dc2-84b6-764215d0a002> ;
    dct:title "Efficient approximation by \"low-complexity\" exponential algorithms" ;
    dcat:contactPoint [ a vcard:Organization ;
            vcard:fn "CCSD" ] ;
    dcat:distribution <https://rec.harvest-normandie.data4citizen.com/dataset/oai-hal-hal-00907607v1/resource/c8c23e49-0418-4efa-999f-0ef7dd9cfed0> ;
    dcat:keyword "infoeu-reposemanticspreprint",
        "infoinfo-cccomputer-science-cscomputational-complexity-cscc",
        "infoinfo-dscomputer-science-csdata-structures-and-algorithms-csds",
        "infoinfo-rocomputer-science-csoperations-research-mathoc",
        "preprints-working-papers-" ;
    dcat:landingPage <https://hal.science/hal-00907607> .

<https://rec.harvest-normandie.data4citizen.com/dataset/oai-hal-hal-00907607v1/resource/c8c23e49-0418-4efa-999f-0ef7dd9cfed0> a dcat:Distribution ;
    dct:format "HTML" ;
    dct:issued "2026-05-08T03:44:09.139319"^^xsd:dateTime ;
    dct:modified "2026-05-08T03:44:09.132139"^^xsd:dateTime ;
    dct:title "Efficient approximation by \"low-complexity\" exponential algorithms" ;
    dcat:accessURL <https://hal.science/hal-00907607> .

<https://rec.harvest-normandie.data4citizen.com/organization/cce9db95-46d9-4dc2-84b6-764215d0a002> a foaf:Agent ;
    foaf:name "test_moissonnage_selune" .

<https://hal.science/hal-00907607> a foaf:Document .