<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//TaxonX//DTD Taxonomic Treatment Publishing DTD v0 20100105//EN" "../../nlm/tax-treatment-NS0.dtd">
<article xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:tp="http://www.plazi.org/taxpub" article-type="research-article" dtd-version="3.0" xml:lang="en">
  <front>
    <journal-meta>
      <journal-id journal-id-type="publisher-id">109</journal-id>
      <journal-id journal-id-type="index">urn:lsid:arphahub.com:pub:3dc5f44e-8666-58db-bc76-a455210e8891</journal-id>
      <journal-title-group>
        <journal-title xml:lang="en">JUCS - Journal of Universal Computer Science</journal-title>
        <abbrev-journal-title xml:lang="en">jucs</abbrev-journal-title>
      </journal-title-group>
      <issn pub-type="ppub">0948-695X</issn>
      <issn pub-type="epub">0948-6968</issn>
      <publisher>
        <publisher-name>Journal of Universal Computer Science</publisher-name>
      </publisher>
    </journal-meta>
    <article-meta>
      <article-id pub-id-type="doi">10.3217/jucs-014-04-0566</article-id>
      <article-id pub-id-type="publisher-id">28971</article-id>
      <article-categories>
        <subj-group subj-group-type="heading">
          <subject>Research Article</subject>
        </subj-group>
        <subj-group subj-group-type="scientific_subject">
          <subject>F.2 - ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY</subject>
          <subject>G.2.1 - Combinatorics</subject>
        </subj-group>
      </article-categories>
      <title-group>
        <article-title>A Linear Time Approximation Algorithm for Ruler Folding Problem</article-title>
      </title-group>
      <contrib-group content-type="authors">
        <contrib contrib-type="author" corresp="yes">
          <name name-style="western">
            <surname>Nourollah</surname>
            <given-names>Ali</given-names>
          </name>
          <email xlink:type="simple">nourollah@aut.ac.ir</email>
          <xref ref-type="aff" rid="A1">1</xref>
        </contrib>
        <contrib contrib-type="author" corresp="no">
          <name name-style="western">
            <surname>Razzazi</surname>
            <given-names>Mohammadreza</given-names>
          </name>
          <xref ref-type="aff" rid="A1">1</xref>
        </contrib>
      </contrib-group>
      <aff id="A1">
        <label>1</label>
        <addr-line content-type="verbatim">Amirkabir University of Technology, Tehran, Iran</addr-line>
        <institution>Amirkabir University of Technology</institution>
        <addr-line content-type="city">Tehran</addr-line>
        <country>Iran</country>
      </aff>
      <author-notes>
        <fn fn-type="corresp">
          <p>Corresponding author: Ali Nourollah (<email xlink:type="simple">nourollah@aut.ac.ir</email>).</p>
        </fn>
        <fn fn-type="edited-by">
          <p>Academic editor: </p>
        </fn>
      </author-notes>
      <pub-date pub-type="collection">
        <year>2008</year>
      </pub-date>
      <pub-date pub-type="epub">
        <day>28</day>
        <month>02</month>
        <year>2008</year>
      </pub-date>
      <volume>14</volume>
      <issue>4</issue>
      <fpage>566</fpage>
      <lpage>574</lpage>
      <uri content-type="arpha" xlink:href="http://openbiodiv.net/76973ED8-79E9-52F3-90A4-65C333200E57">76973ED8-79E9-52F3-90A4-65C333200E57</uri>
      <uri content-type="zenodo_dep_id" xlink:href="https://zenodo.org/record/7000132">7000132</uri>
      <permissions>
        <copyright-statement>Ali Nourollah, Mohammadreza Razzazi</copyright-statement>
        <license license-type="creative-commons-attribution" xlink:href="" xlink:type="simple">
          <license-p>This article is freely available under the J.UCS Open Content License.</license-p>
        </license>
      </permissions>
      <abstract>
        <label>Abstract</label>
        <p>A chain or n-link is a sequence of n links whose lengths are fixed and are joined together from their endpoints, free to turn about their endpoints, which act as joints. "Ruler Folding Problem", which is NP-Complete is to find the minimum length of the folded chain. The best linear approximation algorithm for it were proposed by Hopcroft et al. Their algorithm folds any open chain in the interval whose length is less than 2m1, where m1 is the length of the longest link in the chain. We propose a linear time approximation algorithm using O(1) additional space. Our algorithm has lower upper bound for the length of the folded chain which is max  where m1 and m2are the lengths of the two distinct maximum length links in the chain respectively, and k is the number of links whose lengths are m1 in the chain. Hence it is the best known approximation algorithm for "Ruler Folding Problem".</p>
      </abstract>
    </article-meta>
  </front>
</article>
