<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.0 20120330//EN" "JATS-journalpublishing1.dtd"><article xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" article-type="research-article"><front><journal-meta><journal-id journal-id-type="publisher-id">INFORMATICA</journal-id><journal-title-group><journal-title>Informatica</journal-title></journal-title-group><issn pub-type="epub">0868-4952</issn><issn pub-type="ppub">0868-4952</issn><publisher><publisher-name>VU</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="publisher-id">info21204</article-id><article-id pub-id-type="doi">10.15388/Informatica.2010.283</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research article</subject></subj-group></article-categories><title-group><article-title>Inapproximability Results for Wavelength Assignment in WDM Optical Networks</article-title></title-group><contrib-group><contrib contrib-type="Author"><name><surname>Li</surname><given-names>Keqin</given-names></name><email xlink:href="mailto:lik@newpaltz.edu">lik@newpaltz.edu</email><xref ref-type="aff" rid="j_INFORMATICA_aff_000"/></contrib><aff id="j_INFORMATICA_aff_000">Department of Computer Science, State University of New York, New Paltz, New York 12561, USA</aff></contrib-group><pub-date pub-type="epub"><day>01</day><month>01</month><year>2010</year></pub-date><volume>21</volume><issue>2</issue><fpage>205</fpage><lpage>214</lpage><history><date date-type="received"><day>01</day><month>09</month><year>2008</year></date><date date-type="accepted"><day>01</day><month>02</month><year>2009</year></date></history><abstract><p>We address the issue of inapproximability of the wavelength assignment problem in wavelength division multiplexing (WDM) optical networks. We prove that in an n-node WDM optical network with m lightpaths and maximum load L, if NP ≠ ZPP, for any constant δ&gt;0, no polynomial time algorithm can achieve approximation ratio n<sup>1/2−δ</sup> or m<sup>1−δ</sup>, where NP is the class of problems which can be solved by nondeterministic polynomial time algorithms, and ZPP is the class of problems that can be solved by polynomial randomized algorithms with zero probability of error. Furthermore, the above result still holds even when L=2. We also prove that no algorithm can guarantee the number of wavelengths to be less than <formula>$(\sqrt{n}/2)L$</formula> or (m/2)L. This is the first time inapproximability results are established for the wavelength assignment problem in WDM optical networks. We also notice the following fact, namely, there is a polynomial time algorithm for wavelength assignment which achieves approximation ratio of O(m(log log m)<sup>2</sup>/(log m)<sup>3</sup>). Therefore, the above lower bound of m<sup>1−δ</sup> is nearly tight.</p></abstract><kwd-group><label>Keywords</label><kwd>approximation ratio</kwd><kwd>graph coloring</kwd><kwd>inapproximability</kwd><kwd>optical network</kwd><kwd>wavelength assignment</kwd><kwd>wavelength division multiplexing</kwd></kwd-group></article-meta></front></article>