<?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">inf20205</article-id>
			<article-id pub-id-type="doi">10.15388/Informatica.2009.247</article-id>
			<article-categories>
				<subj-group subj-group-type="heading">
					<subject>Research article</subject>
				</subj-group>
			</article-categories>
			<title-group>
				<article-title>Complexity and Approximability of Committee Polyhedral Separability of Sets in General Position</article-title>
			</title-group>
			<contrib-group>
				<contrib contrib-type="Author">
					<name>
						<surname>Khachay</surname>
						<given-names>Michael</given-names>
					</name>
					<email xlink:href="mailto:mkhachay@imm.uran.ru">mkhachay@imm.uran.ru</email>
					<xref ref-type="aff" rid="j_INFORMATICA_aff_000"/>
				</contrib>
				<contrib contrib-type="Author">
					<name>
						<surname>Poberii</surname>
						<given-names>Maria</given-names>
					</name>
					<xref ref-type="aff" rid="j_INFORMATICA_aff_000"/>
				</contrib>
				<aff id="j_INFORMATICA_aff_000">Institute of Mathematics and Mechanics, Ural Branch of Russian Academy of Sciences, S.Kovalevskoy 16, 620219 Ekaterinburg, Russia</aff>
			</contrib-group>
			<pub-date pub-type="epub">
				<day>01</day>
				<month>01</month>
				<year>2009</year>
			</pub-date>
			<volume>20</volume>
			<issue>2</issue>
			<fpage>217</fpage>
			<lpage>234</lpage>
			<history>
				<date date-type="received">
					<day>01</day>
					<month>08</month>
					<year>2008</year>
				</date>
				<date date-type="accepted">
					<day>01</day>
					<month>05</month>
					<year>2009</year>
				</date>
			</history>
			<abstract>
				<p>It is known that the minimum affine separating committee (MASC) combinatorial optimization problem, which is related to some machine learning techniques, is NP-hard and does not belong to Apx class unless P=NP. In this paper, it is shown that the MASC problem formulated in a fixed dimension space within n&gt;1 is intractable even if sets defining an instance of the problem are in general position. A new polynomial-time approximation algorithm for this modification of the MASC problem is presented. An approximation ratio and complexity bounds of the algorithm are obtained.</p>
			</abstract>
			<kwd-group>
				<label>Keywords</label>
				<kwd>polyhedral separability</kwd>
				<kwd>computational complexity</kwd>
				<kwd>approximation algorithms</kwd>
				<kwd>committees</kwd>
			</kwd-group>
		</article-meta>
	</front>
</article>