<?xml version="1.0" encoding="utf-8"?>
<TEI xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:hal="http://hal.archives-ouvertes.fr/" xmlns:gml="http://www.opengis.net/gml/3.3/" xmlns:gmlce="http://www.opengis.net/gml/3.3/ce" version="1.1" xsi:schemaLocation="http://www.tei-c.org/ns/1.0 http://api.archives-ouvertes.fr/documents/aofr-sword.xsd">
  <teiHeader>
    <fileDesc>
      <titleStmt>
        <title>HAL TEI export of hal-03377095</title>
      </titleStmt>
      <publicationStmt>
        <distributor>CCSD</distributor>
        <availability status="restricted">
          <licence target="https://creativecommons.org/publicdomain/zero/1.0/">CC0 1.0 - Universal</licence>
        </availability>
        <date when="2026-05-23T11:21:40+02:00"/>
      </publicationStmt>
      <sourceDesc>
        <p part="N">HAL API Platform</p>
      </sourceDesc>
    </fileDesc>
  </teiHeader>
  <text>
    <body>
      <listBibl>
        <biblFull>
          <titleStmt>
            <title xml:lang="en">Fixed-Target Runtime Analysis</title>
            <author role="aut">
              <persName>
                <forename type="first">Maxim</forename>
                <surname>Buzdalov</surname>
              </persName>
              <idno type="halauthorid">1617577-0</idno>
              <affiliation ref="#struct-303103"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Benjamin</forename>
                <surname>Doerr</surname>
              </persName>
              <email type="md5">6fe34ee45c65e78ce2c5b32228c02332</email>
              <email type="domain">lix.polytechnique.fr</email>
              <idno type="idhal" notation="string">benjamin-doerr</idno>
              <idno type="idhal" notation="numeric">751503</idno>
              <idno type="halauthorid" notation="string">54103-751503</idno>
              <idno type="ORCID">https://orcid.org/0000-0002-9786-220X</idno>
              <affiliation ref="#struct-2071"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Carola</forename>
                <surname>Doerr</surname>
              </persName>
              <email type="md5">d1b2e33c2d3f25d09951b4c49fa97770</email>
              <email type="domain">lip6.fr</email>
              <idno type="idhal" notation="string">carola-doerr</idno>
              <idno type="idhal" notation="numeric">1290</idno>
              <idno type="halauthorid" notation="string">17976-1290</idno>
              <idno type="ORCID">https://orcid.org/0000-0002-4981-3227</idno>
              <idno type="IDREF">https://www.idref.fr/232603383</idno>
              <affiliation ref="#struct-541718"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Dmitry</forename>
                <surname>Vinokurov</surname>
              </persName>
              <idno type="halauthorid">1617581-0</idno>
              <affiliation ref="#struct-303103"/>
            </author>
            <editor role="depositor">
              <persName>
                <forename>Carola</forename>
                <surname>Doerr</surname>
              </persName>
              <email type="md5">d1b2e33c2d3f25d09951b4c49fa97770</email>
              <email type="domain">lip6.fr</email>
            </editor>
            <funder ref="#projanr-37962"/>
          </titleStmt>
          <editionStmt>
            <edition n="v1" type="current">
              <date type="whenSubmitted">2021-10-14 07:29:14</date>
              <date type="whenWritten">2022</date>
              <date type="whenModified">2025-02-17 13:55:27</date>
              <date type="whenReleased">2021-10-14 08:28:36</date>
              <date type="whenProduced">2022</date>
              <date type="whenEndEmbargoed">2021-10-14</date>
              <ref type="file" target="https://hal.sorbonne-universite.fr/hal-03377095v1/document">
                <date notBefore="2021-10-14"/>
              </ref>
              <ref type="file" subtype="author" n="1" target="https://hal.sorbonne-universite.fr/hal-03377095v1/file/Fixed-target-final.pdf" id="file-3377095-2964901">
                <date notBefore="2021-10-14"/>
              </ref>
            </edition>
            <respStmt>
              <resp>contributor</resp>
              <name key="303028">
                <persName>
                  <forename>Carola</forename>
                  <surname>Doerr</surname>
                </persName>
                <email type="md5">d1b2e33c2d3f25d09951b4c49fa97770</email>
                <email type="domain">lip6.fr</email>
              </name>
            </respStmt>
          </editionStmt>
          <publicationStmt>
            <distributor>CCSD</distributor>
            <idno type="halId">hal-03377095</idno>
            <idno type="halUri">https://hal.sorbonne-universite.fr/hal-03377095</idno>
            <idno type="halBibtex">buzdalov:hal-03377095</idno>
            <idno type="halRefHtml">&lt;i&gt;Algorithmica&lt;/i&gt;, 2022, 84 (6), pp.1762--1793. &lt;a target="_blank" href="https://dx.doi.org/10.1007/s00453-021-00881-0"&gt;&amp;#x27E8;10.1007/s00453-021-00881-0&amp;#x27E9;&lt;/a&gt;</idno>
            <idno type="halRef">Algorithmica, 2022, 84 (6), pp.1762--1793. &amp;#x27E8;10.1007/s00453-021-00881-0&amp;#x27E9;</idno>
            <availability status="restricted">
              <licence target="https://about.hal.science/hal-authorisation-v1/">HAL Authorization<ref corresp="#file-3377095-2964901"/></licence>
            </availability>
          </publicationStmt>
          <seriesStmt>
            <idno type="stamp" n="X">École polytechnique</idno>
            <idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
            <idno type="stamp" n="LIX" corresp="X">Laboratoire d'informatique de l'Ecole polytechnique</idno>
            <idno type="stamp" n="X-DEP-INFO">Département d'informatique de l’École polytechnique</idno>
            <idno type="stamp" n="LIP6" corresp="SORBONNE-UNIVERSITE">Laboratoire d'Informatique de Paris 6</idno>
            <idno type="stamp" n="SORBONNE-UNIVERSITE">Sorbonne Université</idno>
            <idno type="stamp" n="SORBONNE-UNIV" corresp="SORBONNE-UNIVERSITE">Sorbonne Université 01/01/2018</idno>
            <idno type="stamp" n="SU-SCIENCES" corresp="SORBONNE-UNIVERSITE">Faculté des Sciences de Sorbonne Université</idno>
            <idno type="stamp" n="IP_PARIS">Institut Polytechnique de Paris</idno>
            <idno type="stamp" n="TEST-HALCNRS">Collection test HAL CNRS</idno>
            <idno type="stamp" n="SU-TI">Sorbonne Université - Texte Intégral</idno>
            <idno type="stamp" n="ANR">ANR</idno>
            <idno type="stamp" n="ALLIANCE-SU"> Alliance Sorbonne Université</idno>
            <idno type="stamp" n="SUPRA_MATHS_INFO">Mathématiques + Informatique</idno>
          </seriesStmt>
          <notesStmt>
            <note type="audience" n="2">International</note>
            <note type="popular" n="0">No</note>
            <note type="peer" n="1">Yes</note>
          </notesStmt>
          <sourceDesc>
            <biblStruct>
              <analytic>
                <title xml:lang="en">Fixed-Target Runtime Analysis</title>
                <author role="aut">
                  <persName>
                    <forename type="first">Maxim</forename>
                    <surname>Buzdalov</surname>
                  </persName>
                  <idno type="halauthorid">1617577-0</idno>
                  <affiliation ref="#struct-303103"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Benjamin</forename>
                    <surname>Doerr</surname>
                  </persName>
                  <email type="md5">6fe34ee45c65e78ce2c5b32228c02332</email>
                  <email type="domain">lix.polytechnique.fr</email>
                  <idno type="idhal" notation="string">benjamin-doerr</idno>
                  <idno type="idhal" notation="numeric">751503</idno>
                  <idno type="halauthorid" notation="string">54103-751503</idno>
                  <idno type="ORCID">https://orcid.org/0000-0002-9786-220X</idno>
                  <affiliation ref="#struct-2071"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Carola</forename>
                    <surname>Doerr</surname>
                  </persName>
                  <email type="md5">d1b2e33c2d3f25d09951b4c49fa97770</email>
                  <email type="domain">lip6.fr</email>
                  <idno type="idhal" notation="string">carola-doerr</idno>
                  <idno type="idhal" notation="numeric">1290</idno>
                  <idno type="halauthorid" notation="string">17976-1290</idno>
                  <idno type="ORCID">https://orcid.org/0000-0002-4981-3227</idno>
                  <idno type="IDREF">https://www.idref.fr/232603383</idno>
                  <affiliation ref="#struct-541718"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Dmitry</forename>
                    <surname>Vinokurov</surname>
                  </persName>
                  <idno type="halauthorid">1617581-0</idno>
                  <affiliation ref="#struct-303103"/>
                </author>
              </analytic>
              <monogr>
                <idno type="halJournalId" status="VALID">10334</idno>
                <idno type="issn">0178-4617</idno>
                <idno type="eissn">1432-0541</idno>
                <title level="j">Algorithmica</title>
                <imprint>
                  <publisher>Springer Verlag</publisher>
                  <biblScope unit="volume">84</biblScope>
                  <biblScope unit="issue">6</biblScope>
                  <biblScope unit="pp">1762--1793</biblScope>
                  <date type="datePub">2022</date>
                </imprint>
              </monogr>
              <idno type="doi">10.1007/s00453-021-00881-0</idno>
            </biblStruct>
          </sourceDesc>
          <profileDesc>
            <langUsage>
              <language ident="en">English</language>
            </langUsage>
            <textClass>
              <classCode scheme="halDomain" n="info.info-ne">Computer Science [cs]/Neural and Evolutionary Computing [cs.NE]</classCode>
              <classCode scheme="halTypology" n="ART">Journal articles</classCode>
              <classCode scheme="halOldTypology" n="ART">Journal articles</classCode>
              <classCode scheme="halTreeTypology" n="ART">Journal articles</classCode>
            </textClass>
            <abstract xml:lang="en">
              <p>Runtime analysis aims at contributing to our understanding of evolutionary algorithms through mathematical analyses of their runtimes. In the context of discrete optimization problems, runtime analysis classically studies the time needed to find an optimal solution. However, both from a practical and from a theoretical viewpoint, more fine-grained performance measures are needed to gain a more detailed understanding of the main working principles and their resulting performance implications. Two complementary approaches have been suggested: fixed-budget analyses and fixed-target analyses. In this work, we conduct an in-depth study on the advantages and the limitations of fixed-target analyses. We show that, different from fixed-budget analyses, many classical methods from the runtime analysis of discrete evolutionary algorithms yield fixed-target results without greater effort. We use this to conduct a number of new fixed-target analyses. However, we also point out examples where an extension of existing runtime results to fixed-target results is highly non-trivial.</p>
            </abstract>
          </profileDesc>
        </biblFull>
      </listBibl>
    </body>
    <back>
      <listOrg type="structures">
        <org type="institution" xml:id="struct-303103" status="VALID">
          <orgName>ITMO University [Russia]</orgName>
          <desc>
            <address>
              <country key="RU"/>
            </address>
          </desc>
        </org>
        <org type="laboratory" xml:id="struct-2071" status="VALID">
          <idno type="IdRef">196509955</idno>
          <idno type="ISNI">0000000403673665</idno>
          <idno type="RNSR">200519331V</idno>
          <idno type="ROR">https://ror.org/04afed728</idno>
          <idno type="Wikidata">Q16009025</idno>
          <orgName>Laboratoire d'informatique de l'École polytechnique [Palaiseau]</orgName>
          <orgName type="acronym">LIX</orgName>
          <date type="start">2005-01-01</date>
          <desc>
            <address>
              <addrLine>1 Rue Honoré d’Estienne d’Orves, Bâtiment Alain Turing, 91120 Palaiseau</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.lix.polytechnique.fr/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-300340" type="direct"/>
            <relation active="#struct-563936" type="indirect"/>
            <relation name="UMR7161" active="#struct-441569" type="direct"/>
          </listRelation>
        </org>
        <org type="researchteam" xml:id="struct-541718" status="VALID">
          <orgName>Recherche Opérationnelle</orgName>
          <orgName type="acronym">RO</orgName>
          <date type="start">2018-01-01</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
          </desc>
          <listRelation>
            <relation active="#struct-541703" type="direct"/>
            <relation active="#struct-413221" type="indirect"/>
            <relation name="UMR7606" active="#struct-441569" type="indirect"/>
          </listRelation>
        </org>
        <org type="institution" xml:id="struct-300340" status="VALID">
          <idno type="IdRef">027309320</idno>
          <idno type="ISNI">0000000121581279</idno>
          <idno type="ROR">https://ror.org/05hy3tk52</idno>
          <idno type="Wikidata">Q273626</idno>
          <orgName>École polytechnique</orgName>
          <orgName type="acronym">X</orgName>
          <date type="start">1794-03-11</date>
          <desc>
            <address>
              <addrLine>Route de Saclay, 91128 Palaiseau Cedex</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.polytechnique.edu/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-563936" type="direct"/>
          </listRelation>
        </org>
        <org type="regroupinstitution" xml:id="struct-563936" status="VALID">
          <idno type="IdRef">238327159</idno>
          <idno type="ISNI">0000000502717600</idno>
          <idno type="ROR">https://ror.org/042tfbd02</idno>
          <idno type="Wikidata">Q48759778</idno>
          <orgName>Institut Polytechnique de Paris</orgName>
          <orgName type="acronym">IP Paris</orgName>
          <date type="start">2019-06-02</date>
          <desc>
            <address>
              <addrLine>Route de Saclay, 91120 Palaiseau Cedex, France</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.ip-paris.fr</ref>
          </desc>
        </org>
        <org type="regroupinstitution" xml:id="struct-441569" status="VALID">
          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <idno type="ROR">https://ror.org/02feahw73</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.cnrs.fr/</ref>
          </desc>
        </org>
        <org type="laboratory" xml:id="struct-541703" status="VALID">
          <idno type="IdRef">13558292X</idno>
          <idno type="RNSR">199712651U</idno>
          <idno type="ROR">https://ror.org/05krcen59</idno>
          <orgName>LIP6</orgName>
          <date type="start">2018-01-01</date>
          <desc>
            <address>
              <addrLine>4 Place JUSSIEU 75252 PARIS CEDEX 05</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.lip6.fr/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-413221" type="direct"/>
            <relation name="UMR7606" active="#struct-441569" type="direct"/>
          </listRelation>
        </org>
        <org type="regroupinstitution" xml:id="struct-413221" status="VALID">
          <idno type="IdRef">221333754</idno>
          <idno type="ROR">https://ror.org/02en5vm52</idno>
          <orgName>Sorbonne Université</orgName>
          <orgName type="acronym">SU</orgName>
          <date type="start">2018-01-01</date>
          <desc>
            <address>
              <addrLine>21 rue de l’École de médecine - 75006 Paris</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.sorbonne-universite.fr/</ref>
          </desc>
        </org>
      </listOrg>
      <listOrg type="projects">
        <org type="anrProject" xml:id="projanr-37962" status="VALID">
          <idno type="anr">ANR-11-LABX-0056</idno>
          <idno type="program">Centres d'excellences</idno>
          <orgName>LMH</orgName>
          <desc>LabEx Mathématique Hadamard</desc>
          <date type="start">2011</date>
        </org>
      </listOrg>
    </back>
  </text>
</TEI>