text:
\section{Introduction}
In epidemic studies the analysis of
large amounts of personal data is essential. At the same time the
dissemination of the results of those studies, even in a compact and
summarized form, can provide some information that can be exploited to
identify the row pertaining to a certain individual. For instance, ZIP code, gender and date of birth can  uniquely
identify 87\% of individuals in the U.S.~\cite{Sweeny02}.
Therefore when managing personal data it is of  the utmost
importance to effectively protect individuals' privacy.

One approach to deal with such problem is
the $k$-anonymity model~\cite{DBLP:conf/pods/SamaratiS98,Sweeny02,DBLP:journals/tkde/Samarati01,Meyerson_PODS04}.
Each row of a given table represents all data regarding a certain individual.
Then different rows are clustered together, and
some entries of the rows in each cluster are suppressed (i.e.  they are
replaced with a $*$) so that
each cluster consists of at least $k$ identical rows.
Therefore each
row $r$ in the resulting table is clustered with at least other  $k-1$ rows
identical to $r$, hence the resulting data do not allow to identify any individual.
While such formulation is not really sophisticated and has some practical
limitations, it is definitely interesting from a
theoretical point of view, as witnessed by the rich literature available.
We will focus on
separating  the cases that can be
solved efficiently from those that are intractable, therefore hinting at which
strategies are  likely or not going to be successfully employed when studying
more sophisticated formalizations.
Notice that different formulations of the problem have also been
proposed~\cite{Aggar_PODS06}, for example allowing the generalization of
entry values,
that is an entry value can be replaced with a less specific
value~\cite{Aggar_JPT05}, or considering  a notion of
proximity among values~\cite{DBLP:conf/wads/DuEGL09}.

A parsimonious principle leads to the optimization problem where we want to
minimize  the
number of entries in the table to be suppressed.
The $k$-anonymity problem is known to be APX-hard
even  when the matrix entries are over a \emph{binary} alphabet and
$k=3$~\cite{conf/FCT/BonizzoniDD09}, as well as when the matrix has $8$
columns and $k=4$ (this time on arbitrary alphabets)~\cite{conf/FCT/BonizzoniDD09}.
Furthermore, a polynomial-time $O(k)$-approximation algorithm
on arbitrary input alphabet, as well as approximation algorithms
for restricted cases are known~\cite{Aggar_ICDT05}.
Recently, two polynomial-time approximation algorithms with factor $O(\log k)$ have been
independently proposed~\cite{Park_SIGMOD07,Gionis_ESA07}.

In this paper we investigate the parameterized complexity~\cite{ParameterizedComplexity,Niedermeier}
of the problem,
unveiling how different parameters are involved in the complexity of the problem.
A first systematic study of the parameterized complexity of the $k$-anonymity problem
has been proposed in~\cite{DBLP:conf/cocoa/ChaytorEW08}.
Here, we follow the same direction,
showing that the problem is W[1]-hard when parameterized by the size
of the solution and $k$, and we provide a fixed-parameter algorithm, when the
problem is parameterized by the number of
columns and the maximum number of different values in any column.
These problems were left open in~\cite{DBLP:conf/cocoa/ChaytorEW08}.

In Table~\ref{tab:par-compl-status} we report the status of the parameterized complexity
of the $k$-anonymity problem, where in bold we have emphasized the new results
presented in this paper. We recall
that a problem $P$ parameterized by a set $Y$ of parameters
is in the class FPT~\cite{ParameterizedComplexity} if it admits an exact
algorithm with complexity $f(Y)n^{O(1)}$,
where $f$ is an arbitrary function, and $n$ is the size of the
input problem, while it is W[i]-hard~\cite{ParameterizedComplexity}, for some $1 \leq i \leq p$
if it is unlikely to be fixed-parameter tractable.
We recall that XP~\cite{ParameterizedComplexity} is a
superclass of all sets W[$p$]. Moreover, proving that a  problem $\Pi$ with parameter set $S$
is NP-hard when all parameters in $S$ are some constants, implies that
$(\Pi,S) \notin $ XP unless P = NP.

\begin{table}[htb]
\begin{footnotesize}
\centering
\begin{tabular}{|c||c|c|c|c|}
\hline  & $-$ & $k$ & $e$ & $k,e$ \\
\hline  $-$ & NP-hard \cite{Meyerson_PODS04} & $\notin XP$~\cite{conf/FCT/BonizzoniDD09,Aggar_ICDT05} & \textbf{W[1]-hard} \emph{new} & \textbf{W[1]-hard} \emph{new}\\
\hline $|\Sigma|$ & $\notin XP$~\cite{conf/FCT/BonizzoniDD09} & $\notin XP$~\cite{conf/FCT/BonizzoniDD09} & ??? & ???  \\
\hline $m$ & $\notin XP$ for $m \geq 8$~\cite{conf/FCT/BonizzoniDD09}& $\notin XP$ for $m \geq 8$, $k\geq 4$~\cite{conf/FCT/BonizzoniDD09} & FPT~\cite{DBLP:conf/cocoa/ChaytorEW08} & FPT~\cite{DBLP:conf/cocoa/ChaytorEW08} \\
\hline $n$ & FPT~\cite{DBLP:conf/cocoa/ChaytorEW08} & FPT~\cite{DBLP:conf/cocoa/ChaytorEW08}  & FPT~\cite{DBLP:conf/cocoa/ChaytorEW08} &  FPT~\cite{DBLP:conf/cocoa/ChaytorEW08}\\
\hline  $|\Sigma|,m$ & \textbf{FPT} \emph{new} & FPT~\cite{DBLP:conf/cocoa/ChaytorEW08} & FPT~\cite{DBLP:conf/cocoa/ChaytorEW08} & FPT~\cite{DBLP:conf/cocoa/ChaytorEW08} \\
\hline $|\Sigma|,n$ & FPT~\cite{DBLP:conf/cocoa/ChaytorEW08} & FPT~\cite{DBLP:conf/cocoa/ChaytorEW08} & FPT~\cite{DBLP:conf/cocoa/ChaytorEW08}  &  FPT~\cite{DBLP:conf/cocoa/ChaytorEW08}\\
\hline
\end{tabular}
\caption{Summary of the parameterized complexity status of the $k$-anonymity problem;
$|\Sigma|$ represents the maximum number of different values in a column,
$m$ represents the number of columns, $n$ represents the number of rows,
$k$ represents the minimum size of a cluster, $e$ represents the size of the
solution.}
\label{tab:par-compl-status}
\end{footnotesize}
\end{table}

The rest of the paper is organized as follows.
In Section~\ref{sec:pre-sec} we introduce some preliminary definition and we give
the formal definition of the $k$-anonymity problem. In Section~\ref{sec:par-hard} we
show that the $k$-anonymity is W[1]-hard.
In Section~\ref{sec:fpt-algo} we give a fixed parameter algorithm, when the problem is parameterized by the size of the alphabet and the number of columns.
Finally, in Section~\ref{sec:AP-3-3} we show that the $3$-anonymity problem is APX-hard, even when the rows have length bounded by $3$.

\section{Preliminary Definitions}
\label{sec:pre-sec}

Let us
introduce some preliminary definitions that will be used in
the rest of the paper.
Given a graph $G=(V,E)$, and $V' \subseteq V$, the \emph{subgraph induced}
by $V'$ is denoted by $G[V']=(V', E')$, where $E' = E\cap (V'\times V')$.
A graph $G=(V,E)$ is cubic when each vertex in $V$ has degree three.

Given an alphabet $\Sigma$, a row $r$ is a vector of
elements taken from the set $\Sigma$, and the
$j$-th element of $r$ is denoted by $r[j]$.
Notice that it is equivalent to  consider  a row  as a vector over $\Sigma$ or as a string
over alphabet  $\Sigma$.
Let $r_1, r_2$ be two equal-length rows. Then $H(r_1,r_2)$ is the Hamming
distance of $r_1$ and $r_2$, i.e. $|\{i: r_1[i]\neq r_2[i]\}|$.
Let $R$ be a set of $l$ rows, then
a \emph{clustering} of $R$ is a partition $\Pi=(P_1,\dots , P_t )$ of $R$.
Given a clustering $\Pi = (P_1,\dots , P_t )$ of $R$, we define the \emph{cost}
of the row $r$ belonging to a set $P_i$ of $\Pi$ as
$c_{\Pi}(r) = |\{j:\exists r_1,r_2\in P_i,\ r_1[j]\neq r_2[j]\}|$, that is the number of entries
of $r$ that have to be suppressed so that all rows in $P_i$ are identical.
Similarly we define the cost of a set $P_i$,  denoted by $c_{\Pi}(P_i)$, as
$|P_i||\{j:\exists r_1,r_2\in P_i,\ r_1[j]\neq r_2[j]\}|$.
The cost of $\Pi$, denoted by $c(\Pi)$, is defined as
$\sum_{P_i\in \Pi} c(P_i)$.
Given a set $S \subseteq R$ and a clustering $\Pi$ of $R$,  the
cost induced by $\Pi$ in set $S$ is
$c_{\Pi}(S) = \sum_{r \in S} c_{\Pi}(r)$.
Notice that, given a clustering $\Pi = (P_1,\dots, P_t)$ of $R$, the quantity
$|P_i|\max_{r_1,r_2\in P_i}\{H(r_1,r_2)\}$ is a lower bound for $c(P_i)$,
since all the positions for which $r_1$ and $r_2$ differ will
be deleted in each row of $P_i$.
We are now able to formally define the $k$-Anonymity Problem
($k$-AP).

\begin{Problem}$k$-AP.\\
\textbf{Input}: a set $R$ of equal lenght rows over an alphabet $\Sigma_R$.\\
\textbf{Output}: a clustering $\Pi = (P_1,\dots, P_t)$ of $R$
such that for each set $P_i$, $|P_i|\geq k$ and $c(\Pi)$ is minimum.
\end{Problem}

In what follows, given a set $S$ of parameters, we denote by $\langle S \rangle$-AP
the $k$-AP problem parameterized by $S$, thus omitting $k$.
We will consider the following parameters:
$m$ is the number of columns of the rows in $R$;
$n$ is the  number of rows  in $R$;
$|\Sigma|$ is the  maximum number of different values in any column of the table;
$k$ is  the minimum size of a cluster;
$e$ is  the maximum number of entries that can be suppressed.

Let $\Pi=(P_1, \dots, P_z)$ be a solution of the $k$-AP problem.
Notice that a suppression at position $j$ of a row $r$ is represented
replacing the symbol $r[j]$ with a $*$.
Given a set
$P_j$ of $\Pi$, some entries of the rows clustered in $P_j$ are suppressed, so that
the resulting rows are all identical to a vector $r$ over alphabet $\Sigma_R \cup \{ * \}$; such
a vector is the \emph{resolution vector} associated
with $P_j$.
Given a
resolution vector $r$, we define $del(r)$ as the number of entries
suppressed in $r$, that is $del(r)=|\{j: r[j]=* \}|$.
Given a resolution vector $r$ and a row $r_i \in R$,
we say that $r$ is \emph{compatible} with row $r_i$ iff
$r[j] \neq r_i[j]$ implies $r[j]=*$.
Given a row $r_i$ of $R$ and a set of resolution vectors $S'$,
we define the set $comp(r_i,S')=\{ r \in S': r  \text{ is compatible with } r_i \}$.

Given a set $R$ of rows, we define a \emph{group} of rows of $R$ as a maximal
set of identical rows. Given a group $g$, the \emph{representative row} of $g$, denoted by $r(g)$, is
any row of $g$, while  $s(g)$ is the number of rows in $g$ and  $exc(g)=\max\{0, s(g)-k\}$.
A set $R$ of rows can be partitioned in groups of identical rows
in polynomial time~\cite{DBLP:conf/cocoa/ChaytorEW08}, therefore
we can compute in polynomial time
whether a set $R$ of rows is $k$-anonymous, i.e. $R$ can be partioned into groups of size at least $k$.
If this is not possible, then observe that at least $k$ entries of $R$ must be suppressed
to get a solution of the $k$-AP problem, that is $e \ge k$.
Hence $\langle e \rangle$-AP is in FPT iff $\langle e,k \rangle$-AP is in FPT.
Consequently our
parameterized reduction~\cite{ParameterizedComplexity,Niedermeier} will show
the fixed-parameter intractability of $\langle e \rangle$-AP and
$\langle e,k \rangle$-AP.
\begin{comment
Given two parameterized languages $L$ and $L'$, a parameterized
reduction from $L$ to $L'$ is a function that, given an input $(x,k)$ of $L$
computes an instance $(x',k')$ of $L'$ in time $f(k)n^{O(1)}$, where
$k'$ depends only on $k$, such that $(x,k) \in L$ iff $(x',k') \in L'$.
\end{comment}

\section{$\langle e \rangle$-AP and $\langle e,k \rangle$-AP are W[$1$]-hard}
\label{sec:par-hard}

We show that $\langle e \rangle$-AP and $\langle e,k \rangle$-AP are
W[1]-hard.
Given an set $R$ of equal length rows,
$\langle e \rangle$-AP and $\langle e,k \rangle$-AP ask if there exists
a clustering $\Pi = (P_1,\dots , P_t)$ of R such that $|P_i| \geq k$ for each set $P_i$,
and $c(\Pi) \leq e$.
We present a parameter preserving reduction from the $h$-Clique problem, which is
known to be W[1]-hard~\cite{DBLP:journals/tcs/DowneyF95}, to the $\langle e \rangle$-AP problem.
Given a graph $G=(V,E)$, an $h$-clique is a set $V' \subseteq V$
where each pair of vertices in $V'$ are connected by an edge of $G$, and
$|V'|=h$.
The $h$-Clique problem asks for a subset $V'$ of the
vertices of a given graph $G$ inducing an $h$-clique in $G$.
\begin{comment
First, let us introduce the $h$-Clique problem.

\begin{Problem}$h$-Clique.\\
\textbf{Input}: a graph $G=(V,E)$.\\
\textbf{Parameter}: $h$.\\
\textbf{Output}: a set $V' \subseteq V$, such that $G[V']$ is a complete graph and $|V|=h$.
\end{Problem}
\end{comment}

Clearly the vertices of a $h$-clique are connected by ${h} \choose{2}$ edges.
Given a graph $G=(V,E)$,  we use $m_G$  and $n_G$  to denote
respectively the number of edges and of vertices of $G$.
We construct the instance  $R$ of $\langle e \rangle$-AP associated with $G$.
First, let us define $k=2h^2$. The set  $R$ consists of
$(k+1)m_G+(k-{h \choose 2})$ rows
and $2h+n_G$ columns over alphabet $\Sigma_R= \{  0,1 \} \cup \{  \sigma_{i,j}:(v_i,v_j) \in E \}$.
More precisely, for each edge $e(i,j)=(v_i,v_j)$ in $E$, there is a
group $R(i,j)$ of $k+1$ identical rows $r_x(i,j)$, $1 \leq x \leq k+1$, where

\begin{itemize}
\item $r_x(i,j)[l]= \sigma_{i,j}$, for $1 \leq l \leq 2h$;
\item $r_x(i,j)[2h+i]= 1$, $r_x(i,j)[2h+j]= 1$;
\item $r_x(i,j)[2h+l]= 0$, for $l \neq i,j$ and $1 \leq l \leq n$.
\end{itemize}

Moreover, $R$ also contains a group $R_0$
made of $k-{h \choose 2}$ identical rows equal to $0^{2h+n_G}$.

\begin{Lemma}
\label{lem:W[1]-hard:prop-base}
Let $R$ be the instance of $\langle e \rangle$-AP associated with  $G$ and
consider two rows $r,r_x(i,j)$ of $R$, such that
$r \in R_0$ and $r_x(i,j) \in R(i,j)$. Then, $r[t] \neq r_x(i,j)[t]$,
for each $1 \leq t \leq 2h$.
\end{Lemma}

\begin{Lemma}
\label{lem:W[1]-hard-1}
Let $G=(V,E)$ be a graph, let $V'$ be a  $h$-clique of $G$ and let
$R$ be the instance of $\langle e \rangle$-AP associated with  $G$.
Then we can compute in polynomial time a solution $\Pi$ of $\langle e \rangle$-AP over instance $R$
with cost at most $6h^3$.
\end{Lemma}

\begin{Lemma}
\label{lem:W[1]-hard-2}
Let $G=(V,E)$ be an  instance of $h$-Clique, let
$R$ be the instance of $\langle e \rangle$-AP associated with $G$ and let  $\Pi$
be a solution of $\langle e \rangle$-AP over instance $R$ with cost at most $6h^3$.
Then we can compute in polynomial time a  $h$-clique  $V'$ of $G$.
\end{Lemma}
\begin{proof}
First we will prove that $\Pi$ must have a set $R_0'\supset R_0$. Assume to
the contrary that in $\Pi$ there are two sets $A$, $B$ containing at least a
row of $R_0$. Notice that $|R_0|<k$ while $|A|,|B|\ge k$.
Moreover, by Lemma~\ref{lem:W[1]-hard:prop-base}, all rows in $A$ or $B$  must
have suppressed the first
$2h$ entries,  which results in at least $4hk>6h^3$ suppressions,
contradicting the assumption on the cost of the solution.
Hence,  $R_0$ is properly contained in a set
$R_0'$ of $\Pi$, as $|R_0| < k$.
Moreover,
let $r'$ be a row of $R_0'\setminus R_0$ and let $r$ be a row of  $\in R_0$.
By Lemma~\ref{lem:W[1]-hard:prop-base} $r'[t] \neq r[t]$ for each column $t$,
$1 \leq t \leq 2h$,  therefore all entries in the
first $2h$ columns of each row in $R_0'$ must be suppressed.

Now, let us prove that, for each set $R(i,j)$ of $R$, there exists a set
$R'(i,j)$ of $\Pi$ such that $R'(i,j)\subseteq R(i,j)$. Assume to the contrary
that no such set $R'(i,j)$ exists, for a given $R(i,j)$. Then either $R(i,j)\subseteq
R_0'$ or there exists a row of $R(i,j)$  clustered together with a row of
$R(x,y)$ in $\Pi$, with $(x,y)\neq (i,j)$.
In the first case, that is  $R(i,j)\subseteq R_0'$, $|R_0'|\ge
2k+1-{h \choose 2}$, by construction
all entries of the first $2h$ columns of the rows in $R_0'$ must be suppressed,
resulting in at least $2h(4h^2-{h \choose 2})>6h^3$ suppressions
and thus contradicting the assumption on the cost of the solution. Consider now the second case,
that is there is a set $A$ in $\Pi$ containing at least a row of two different
sets $R(i,j)$ and $R(x,y)$ of $R$.
Observe that given $r'  \in R'_0 \setminus R_0$  and $r \in R_0$, $r$ and $r'$ differ in the first $2h$ columns.
Thus the entries of the  first $2h$ columns of the rows of $R_0'$ must be
suppressed,
resulting in at least $4hk>6h^3$ suppressed entries
and thus contradicting the assumption on the cost of the solution. Hence, for
each set $R(i,j)$ of $R$, there exists a set
$R'(i,j)$ of $\Pi$ such that $R'(i,j)\subseteq R(i,j)$.

By our previous arguments we can assume that $\Pi$ consists of the clusters
$R_0'$ and $R'(i,j)$, for each $R(i,j) \in R$,
and that $|R(i,j)|-1 \leq |R'(i,j)| \leq |R(i,j)|$. Notice that only
$R_0'$ can contain some suppressed entries.
Also  $|R_0'|=k$, for otherwise we can improve the cost of $\Pi$ by
moving a row
in $R(i,j) \cap R'_0$ from $R'_0$ to  $R'(i,j)$.
Now let $E'$ be the set of edges
$(v_i,v_j)$ of $G$ such that a row of $R(i,j)$ is in $R_0'$ and let $V'$ be the
set of vertices incident on at least an edge in $E'$. Then we can  show that
$G[V']$ is a $h$-clique.
Notice that the entries
in the first $2h$ columns of $R_0'$ must be suppressed, as well as all columns
with index $2h+l$ such that $v_l\in V'$, since in those columns all rows in
$R_0$ have value $0$ while some row in $R'_0 \setminus R_0$ have value $1$. An immediate
consequence is that the overall number of suppressed entries is at least
$2hk+k|V'|$. Since, by hypothesis, the number of suppressed entries is at
most $6h^3=3kh$, then $|V'|\le h$. Notice that,
since $|R_0 | = k - {h \choose 2}$ and $|R'_0| = k$, then $R'_0 \setminus R_0$
contains exactly ${h \choose 2}$ distinct rows corresponding to edges in $E'$
incident on $V'$ vertices.
Hence $V'$ induces a $h$-clique in $G$.
\qed\end{proof}

From Lemma~\ref{lem:W[1]-hard-1} and~\ref{lem:W[1]-hard-2},  our  reduction is
parameter preserving, therefore
$\langle e \rangle$-AP and $\langle e,k \rangle$-AP are W[1]-hard.

\begin{comment}
\begin{Theorem}
\label{therorem:W[1]-hard}
$\langle e \rangle$-AP and $\langle e,k \rangle$-AP are W[1]-hard.
\end{Theorem}
\end{comment}

\section{An FPT algorithm for $\langle |\Sigma|,m \rangle$-AP\xspace}
\label{sec:fpt-algo}

In this section we present a fixed-parameter algorithm for the
$\langle |\Sigma|,m \rangle$-AP\xspace problem, that is the instance of the AP problem, where
the number $m$ of columns and the maximum number $|\Sigma|$ of different values in any column
are two parameters.
Notice that $k$-AP parameterized by exactly one of $|\Sigma|$ or $m$
is not in FPT, as $k$-AP is APX-hard (hence NP-hard)
even when one of $|\Sigma|$ or $m$ is a constant~\cite{conf/FCT/BonizzoniDD09}.

Before giving the details of the algorithm, let us first introduce some preliminary
definitions.
Let $R$ be an instance of $\langle |\Sigma|,m \rangle$-AP\xspace,
and for each column of $R$ with index $j$,  $1 \leq j \leq m$, let $\Sigma_j$
be the set of different values that the rows of $R$ have in column $j$.
Notice that $|\Sigma_j| \leq |\Sigma|$, for each $1 \leq j \leq m$.
Let $\Sigma_j^{*} = \Sigma_j \cup \{ * \}$
and $\Sigma^{*} = \Sigma  \cup \{ * \}$.
Assume $\Pi = \{P_1, \cdots, P_z\}$  is a feasible solution
of $\langle |\Sigma|,m \rangle$-AP\xspace over instance $R$. The set $S'$ consisting of  a
resolution vector for each set $P_i \in \Pi$ is called
\emph{candidate set} for solution $\langle |\Sigma|,m \rangle$-AP\xspace.
Let $S$ be the set of possible rows of length $m$ and having value over alphabet
$\Sigma^*_j$ for the position $j$, $1 \leq j \leq m$,
then $|S|$ is
bounded by $|\Sigma^*|^m$.  Given a candidate set $S'$,
notice that $S' \subseteq S$ and that
each row $r \in R$ must compatible with at least one resolution
vector in $S'$.

Given a row $r$ and the set  $S'$ of resolution vectors, recall that we denote by $Comp(r,S')$
the set of resolution vectors of $S'$ compatible with $r$. Moreover,  given a
resolution vector $r' \in S'$,
we denote by $del(r')$  the number of suppressions in $r'$.
For each row $r\in R$ we define its weight as
$w(r)= \max_{r_x \in Comp(r,S')} \{m-del (r_x)\}$.
Notice that $w(r) = m$ whenever  $r$ is compatible with a row without
suppressions. Informally, the weight of a row is equal to
the maximum number of its entries that might be preserved in a solution where $S'$ is
the set of resolution vectors.
Finally, we define $W= \sum_{r \in R} w(r)$ and $w'(r_x)= W+ m-del(r_x)+1$
for each row $r_x\in S'$.
Notice that $w'(r_x) \geq \sum_{r \in R} w(r)$, for each $r_x \in R$.
The weights defined above will be used later in Section~\ref{subsect_build} to define the weight
function $w_h$.

Let us first describe the general idea of the algorithm.
Given a candidate set $S'$, the algorithm computes an optimal solution $\ensuremath{\Pi_{S'}}$ associated with a candidate
set $S' \subseteq S$ (see Algorithm~\ref{alg:solving-AP}).
The algorithm consists of two main phases.
In the first phase (Section~\ref{subsect_build}), given the set $R$ of input rows and the candidate set $S'$, the algorithm builds a weighted bipartite graph $G_{S',R}$
associated with $R$ and $S'$.
In the second phase (Section~\ref{subsect_solution}) a solution
of $\langle |\Sigma|,m \rangle$-AP\xspace is computed starting from a maximum weighted matching
of the graph $G_{S',R}$.
Section~\ref{subsect_opt_solution} is devoted to prove
that the solution computed by the algorithm is optimal.

\begin{algorithm}[t]
\label{alg:solving-AP}
\KwIn{An instance $R$ of $\langle |\Sigma|,m \rangle$-AP\xspace made  of a set of $n$ rows, each one consisting
  of $m$ symbols, and an integer $e$}
\KwOut{a solution of $\langle |\Sigma|,m \rangle$-AP\xspace over instance $R$,
if $\langle |\Sigma|,m \rangle$-AP\xspace admits a solution that suppresses at most $e$ entries\;}
$S\gets$ the set of resolved vectors of length $m$, where each $j$-th symbol, $1 \leq j \leq m$, is taken from the  alphabet $\Sigma^*_j$\;
$W= \sum_{r \in R} w(r)$\;
\ForEach{subset $S'$ of $S$}{%
  $G_{R,S'}$\xspace $\gets $ the graph associated with $R,S'$\;
  $M\gets $ a maximum matching of $G_{R,S'}$\xspace;
  $w\gets $ the weight of $M$\;
   \uIf{$M$ is feasible and $w \geq (W+1) k |S'| + m |R^l_{dist} \cup R^l_{safe}|- e$}{\Return{the solution $\ensuremath{\Pi_{S'}}(M)$ of $R$ associated with $M$\;}}
}
\Return{No such solution exists}
\caption{Solving $\langle |\Sigma|,m \rangle$-AP\xspace}
\end{algorithm}

\subsection{Building the graph $G_{R,S'}$\xspace}
\label{subsect_build}
Let us consider a candidate set $S'$ of vectors
for an optimal solution of $\langle |\Sigma|,m \rangle$-AP\xspace.
Since $S' \subseteq S$,  there exist
at most $2^{|\Sigma^{*}|^m}$ possible candidate sets of rows $S'$, therefore our
FPT algorithm computes each candidate set $S'$ and verifies if there exists a solution $\ensuremath{\Pi_{S'}}$
with cost at most $e$.
In order to verify if such a solution exists, the algorithm builds a bipartite graph
$G_{R,S'}$\xspace, as described in this section.
The intuitive idea behind the graph is that
edges of the graph correspond to possible ways of assigning each
row in $R$ to a resolution vector $x \in S'$. Rows
assigned to the same resolution vector $x \in S'$ are clustered in the solution $\ensuremath{\Pi_{S'}}$.

The construction of the vertex set of the graph is based on  a a
partition of $R$ into two disjoint sets called $\ensuremath{R_{safe}}$ and
$\ensuremath{R_{dist}}$ (that is $\ensuremath{R_{dist}} = R \setminus \ensuremath{R_{safe}}$). The set $\ensuremath{R_{safe}}
$ consists of those rows $r \in R$ belonging to the group $g$ such that:
$s(g) \geq k$, that is $r$ belongs to a group of at least $k$ identical rows, and
there exists a row $r_j \in S'$, such that $r_j$ and $r(g)$ are the
same vector.
Notice that only rows in \ensuremath{R_{safe}}{} might have no
suppressed entry in a solution $\ensuremath{\Pi_{S'}}$.

The vertex set of $G_{R,S'}$\xspace$=(V,E)$ has $6$ sets.
Two sets ($\ensuremath{R_{dist}}^l$, $\ensuremath{R_{dist}}^r$) consist of vertices associated
with the rows in $\ensuremath{R_{dist}}$, three sets ($\ensuremath{R_{safe}}'^l$, $\ensuremath{R_{safe}}^l$,
$\ensuremath{R_{safe}}^r$) consist of vertices associated
with the rows in $\ensuremath{R_{safe}}$, and a final set called $T$ consists of vertices
associated with the rows in $S'$. In the latter case notice that for each row
$x$ in $S'$ there exist $k$ vertices in $T$ to ensure that
the cluster associated with $x$ has size at least  $k$.
The vertex set is defined as follows:

\begin{itemize}
\item for each row $x\in \ensuremath{R_{dist}}$, there is a corresponding vertex
$\ensuremath{R_{dist}}^l(x)$ in $\ensuremath{R_{dist}}^l$  and a corresponding vertex $\ensuremath{R_{dist}}^r(x)$ in $\ensuremath{R_{dist}}^r$;
\item for each  group $g$ consisting of the set of rows $\{ x_1, x_2 , \dots, x_{s(g)}  \}$,
where each $x_i \in \ensuremath{R_{safe}}$, $1 \leq i \leq s(g)$,
there are $k$ corresponding vertices in $\ensuremath{R_{safe}}'^l$, (such vertices
are denoted by $\ensuremath{R_{safe}}'^l(g,1), \ldots , \ensuremath{R_{safe}}'^l(g,k)$),
$exc(g)$ corresponding vertices in $\ensuremath{R_{safe}}^l$ (such vertices
are denoted by $\ensuremath{R_{safe}}^l(g,1),$ $\ldots ,$ $\ensuremath{R_{safe}}^l(g,exc(g)$), and
$exc(g)$ corresponding vertices in $\ensuremath{R_{safe}}^r$ (such vertices are denoted by
$\ensuremath{R_{safe}}^r(g,1),$ $\ldots ,$
$\ensuremath{R_{safe}}^r(g,exc(g)$);
 \item for each row $x \in S'$, there are $k$ corresponding vertices in $T$ (such
vertices are denoted by $T(x, 1), \dots, T(x, k)$).
\end{itemize}

Notice that  our graph $G_{R,S'}$\xspace is edge-weighted. Let $w_h$ be the
weight function assigning a positive weight to each edge of
$G_{R,S'}$\xspace. Given the  set of edges $E' \subseteq E$, we denote by
$w_h(E')= \sum_{e \in E'} w_h(e)$.

First, notice that the set $S'$  consists of two disjoint sets:
the set \ensuremath{S'_{safe}} consists of those rows in $S'$ that have no
suppressions, while $\ensuremath{S'_{cost}}=S' \setminus \ensuremath{S'_{safe}}$.
Each edge connects a vertex of $\ensuremath{R_{safe}}'^l \cup \ensuremath{R_{safe}}^l \cup
\ensuremath{R_{dist}}^l$ with a vertex of $\ensuremath{R_{safe}}^r \cup \ensuremath{R_{dist}}^r \cup T$, hence
the graph $G_{R,S'}$\xspace is bipartite.
The set $S'$  consists of two disjoint sets:
the set \ensuremath{S'_{safe}} consists of those rows in $S'$ that have no
suppressions, while $\ensuremath{S'_{cost}}=S' \setminus \ensuremath{S'_{safe}}$.
Intuitevely, each edge represents a possible
assignment of a row in $R$ to a resolution vector in $S'$.
\begin{comment}
In particular, each vertex $\ensuremath{R_{safe}}'^l(g,j)$, with $1 \leq j \leq k$, is connected
only to vertex $T(x,j)$, where $x$ is the resolution vector identical to $r(g)$
(this kind of edges is defined at point 3). This kind of edges ensures that
there are at least $k$ vertices assigned to each resolved vector in $\ensuremath{S'_{safe}}$.
The vertices of $\ensuremath{R_{safe}}^l$ and the vertices of $\ensuremath{R_{dist}}^l$
are connected to a subset of vertices of $T$ associated
with resolved vectors in $S'$ (this kind of edges is defined at points 1 and 4).
Finally, each vertex of $\ensuremath{R_{dist}}^l$ is connected to a vertex
of $\ensuremath{R_{dist}}^r$ (this kind of edges is defined at point 2) and
each vertex of $\ensuremath{R_{safe}}^l$ is connected to a vertex
of $\ensuremath{R_{safe}}^r$ (this kind of edges is defined at point 5).

\end{comment}

\begin{comment}
The edges that will be defined later, are associated with different kinds of assignment
of the rows in $R$ to resolution vectors in $S'$. In particular,

\begin{description}

\item[Case a] At least $k$ identical rows of a group $g$ of rows in $\ensuremath{R_{safe}}$ are assigned
to a row $x$ of $\ensuremath{S'_{safe}}$ (notice that $r(g)$ are identical vectors); then each of the
$k$ vertices in the graph associated with the first $k$ rows of group $g$ is connected to
to exactly one vertex associated with $x$. This case leads to the edges of
type 3.

\item[Case b]
At least $k$ rows of $\ensuremath{R_{dist}} \cup \ensuremath{R_{safe}}$ are assigned
to a resolution vector $x$ of $\ensuremath{S'_{cost}}$; then a matching will connect $k$ vertices in
$\ensuremath{R_{dist}}^l \cup \ensuremath{R_{safe}}^l$ (vertices in $\ensuremath{R_{dist}}^l$ or the last $exc(g)$ vertices of
$\ensuremath{R_{safe}}^l$) to exactly one vertex associated with $x$. This case leads to the edges of
type 1 and 4.

\item[Case c]
More than $k$ rows are assigned to a resolution vector $x$ of $\ensuremath{S'_{cost}}$, then an
exceeding row $r$ is just assigned to the most convenient
compatible resolution vector; this assignment
corresponds to an edge of $G_{R,S'}$\xspace connecting
a vertex of $\ensuremath{R_{dist}}^l$ and a vertex of $\ensuremath{R_{dist}}^r$, or a
a vertex of $\ensuremath{R_{safe}}^l$ and a vertex of $\ensuremath{R_{safe}}^r$. This case leads to the edges of
type 2 and 5.
\end{description}
\end{comment}

\begin{algorithm}
\label{alg:matching} \KwIn{A graph $G_{R,S'}$\xspace associated with an
instance $R$ and a maximum weight matching $M$ of $G_{R,S'}$\xspace}
\KwOut{A solution $\ensuremath{\Pi_{S'}}(M)$ of $\langle |\Sigma|,m \rangle$-AP\xspace over instance $R$}
\ForEach{edge $y$ of $M$}{%
  \uIf(\tcc*[f]{edges defined at point 1}){$y = (\ensuremath{R_{dist}}^l(r),T(x,j))$}{%
    row $r$ is assigned to
    a set whose resolution row is $x$, $x \in S'$}
  \uIf(\tcc*[f]{edges defined at point 2}){$y = (\ensuremath{R_{dist}}^l(r),\ensuremath{R_{dist}}^r(r))$}{%
    row $r$ is assigned to
    a set whose resolution row is $r_y= \text{arg } \max w(r)$, $r_y \in S'$\;}
  \uIf(\tcc*[f]{edges defined at point 3}){$y = (\ensuremath{R_{safe}}'^l(g,i), T(x,j))$}{%
    assign the $i$-th row of $g$ to a set whose resolution row is
    $x$, $x \in S'$\;
  }
  \uIf(\tcc*[f]{edges defined at point 4}){$y = (\ensuremath{R_{safe}}^l(g,i), T(x,j))$}{%
    assign the $i$-th exceeding row of $g$ to a set whose resolution row is
    $x$, $x \in S'$\;
  }
  \uIf(\tcc*[f]{edges defined at point 5}){$y = (\ensuremath{R_{safe}}^l(g,i), \ensuremath{R_{safe}}^r(g,i))$}{%
    assign the $i$-th exceeding row of group $g$ to the set whose
    resolution row is $r(g)$, with $r(g) \in S'$ and $r \in \ensuremath{R_{safe}}$\;
  }
} \caption{From a matching to a feasible solution of $\langle |\Sigma|,m \rangle$-AP\xspace.}
\end{algorithm}

Now we are ready to define formally the set of edges $E$ of
$G_{R,S'}$\xspace and the weight function $w_h$. There are five possible
kinds of edges.

\begin{enumerate}
\item Let $r$ be a row of $\ensuremath{R_{dist}}$, and let $x$ be a row in  $Comp(r,S') \cap \ensuremath{S'_{cost}}$.
Then there is an edge $y=(\ensuremath{R_{dist}}^l(r),T(x,j))$, for each $1 \leq j \leq k$, with weight
$w_h \left( y \right)= w'(x)$.

\item Let $r$ be a row in $\ensuremath{R_{dist}}$.
Then there is an edge $y=(\ensuremath{R_{dist}}^l(r),\ensuremath{R_{dist}}^r(r))$ with weight
$w_h \left( y \right)=w(r)$.

\item
Let $g$ be a group consisting of rows $\{ r_1, \dots , r_{s(g)} \}$, where
$r_i$, for each $i$ with $1 \leq i \leq s(g)$, is a row of $\ensuremath{R_{safe}}$;
let $r'$ be the resolution vector of $\ensuremath{S'_{safe}}$ identical to $r(g)$.
Then there is an edge $y_i=(\ensuremath{R_{safe}}'^l(g,i), T(r',i))$, for each $i$ with $1 \leq
i \leq k$. All edges $y_i$ have weight $w_h \left( y_i \right)= w'(r')$.

\item Let $g$ be a group consisting of rows $\{ r_1, \dots , r_{s(g)} \}$, where
$r_i$, for each $i$ with $1 \leq i \leq s(g)$, is a row of $\ensuremath{R_{safe}}$; let $x$ be a row in $Comp(r(g),S') \cap \ensuremath{S'_{cost}}$.
Then there is an edge $y_{i,j}=(\ensuremath{R_{safe}}^l(g,i), T(x,j))$, for each $i$ with $1 \leq
i \leq exc(g)$ and for each $j$ with $1 \leq j \leq k$. All edges $y_{i,j}$ have weight $w_h \left( y_{i,j} \right)= w'(x)$.

\item Let $g$ be a group consisting of rows $\{ r_1, \dots , r_{s(g)} \}$, where
$r_i$, $1 \leq i \leq s(g)$, is a row of $\ensuremath{R_{safe}}$.
Then there is an edge $y_i=(\ensuremath{R_{safe}}^l(g,i), \ensuremath{R_{safe}}^r(g,i))$ for each $i$
with $1 \leq i \leq exc(g)$. All edges $y_i$ have weight $w_h \left( y_i \right)= w(r(g))$.
\end{enumerate}

\subsection{Computing a solution of $\langle |\Sigma|,m \rangle$-AP\xspace}
\label{subsect_solution}
In this  section we  prove  in
Lemma~\ref{lem:feas:solution} that  $\ensuremath{\Pi_{S'}}(M)$ is a clustering of
the rows in $R$ that is a feasible solution for the $\langle |\Sigma|,m \rangle$-AP\xspace problem. See Fig. \ref{fig:ex-alg} for an example.

Since $G_{R,S'}$\xspace bipartite, we can efficiently compute a maximum weight matching $M$ of
$G_{R,S'}$\xspace~\cite{fastmwb}.
Given a matching $M$ of the graph $G_{R,S'}$\xspace,  Algorithm~\ref{alg:matching}
computes in polynomial time a clustering $\ensuremath{\Pi_{S'}}(M)$ of the rows in $R$.
Informally, the clustering is computed by assigning
the rows in $R$ to the resolution vector in $S'$,
using the edges in the matching $M$.

\begin{comment}
\begin{Example}
Let $R$ be a an instance of $\langle |\Sigma|,m \rangle$-AP\xspace, with $k=2$ and $m=3$ defined as follows:
$R= \{ r_1 = (a,a,a), r_2 = (a,a,a), r_3 = (a,a,a), r_4 = (a,a,a),
r_5 = (a,b,a), r_6 = (b,b,b), r_7 = (b,b,c)\}.
$
Notice that $r_1$, $r_2$, $r_3$, $r_4$ belongs to the same group $g_1$ of identical rows, which has as representative
row $(a,a,a)$. Each row in $\{r_5, r_6, r_7 \}$ belongs to a different group.
Let $S'$ be the set of resolution vectors
$s_1 = (a,a,a)$, $s_2 = (a,*,a)$, $s_3 = (b,b,*)$.
Notice that $w(r_1)=w(r_2)=w(r_3)=w(r_4)=3$, while $w(r_5)=w(r_6)=w(r_7)=2$.
$W = \sum_{r \in R}w(r)=18$ and
$w'(s_1)=w'(s_2)=w'(s_3)=w'(s_4)=21$, while $w'(s_5)=w'(s_6)=w'(s_7)=20$.
Let us define the graph $G_{R,S'}$\xspace.
\end{Example}
\end{comment}
\begin{figure}[tb]
\label{fig:ex-alg}
\begin{minipage}{4cm}\small\begin{center}
\begin{tabular}{clll}
\multicolumn{4}{c}{Rows $R$}\\\hline\hline
Name&Data&$w$&Group\\\hline
$r_1$ & aaa&$3$&\\\cline{1-3}
$r_2$ & aaa&$3$&\\\cline{1-3}
$r_3$ & aaa&$3$&\raisebox{1.5ex}[0pt]{$g_1$}\\\cline{1-3}
$r_4$ & aaa&$3$&\\\hline
$r_5$ & aba&$2$&$g_2$\\\hline
$r_6$ & bbb&$2$&$g_3$\\\hline
$r_7$ & bbc&$2$&$g_4$\\\hline
\end{tabular}\vspace{2em}

\begin{tabular}{cll}
\multicolumn{3}{c}{Resolution vectors $S'$}\\\hline\hline
Name&Vectors&$w$\\\hline
$s_1$ & aaa&$21$\\\hline
$s_2$ & a*a&$20$\\\hline
$s_3$ & bb*&$20$\\\hline
\end{tabular}

\end{center}
\end{minipage}\hfill
\begin{minipage}{8cm}
\tikzstyle{vertex}=[circle,fill=black,minimum size=6pt,inner sep=0pt]
\begin{tikzpicture}[scale=0.65,font=\scriptsize]
\foreach \name/\x in {1/7, 2/6, 3/5}
     \node[vertex] (L-\name) at (7,1.75*\name) [label=below:$R^l_{dist}(r_{\x})$]{};

\foreach \name/\x in {4/2, 5/1}
     \node[vertex] (L-\name) at (7,1.75*\name) [label=below:$R^l_{safe}({g_1,\x})$]{};

\foreach \name/\x in {6/2, 7/1}
     \node[vertex] (L-\name) at (7,1.75*\name) [label=below:$R'^l_{safe}({g_1,\x})$]{};

\foreach \name/\x in {4/2, 5/1}
     \node[vertex] (R-\name) at (10,1.75*\name) [label=below:$R^r_{safe}({g_1,\x})$] {};

\foreach \name/\x in {1/7, 2/6, 3/5}
     \node[vertex] (R-\name) at (10,1.75*\name) [label=below:$R^r_{dist}(r_{\x})$] {};

\foreach \name/\x/\y/\z in {1/1/s_3/1, 2/2/s_3/2, 3/3/s_2/1, 4/4/s_2/2, 5/5/s_1/1, 6/6/s_1/2}
     \node[vertex] (S-\name) at (0,1+1.75*\x) [label=below:{$T(\y,\z)$}] {};

\foreach \from/\to/\w in {1/1/2, 2/2/2, 3/3/2, 4/4/3}
\draw [-, thin, dashed] (L-\from) --node[midway,below] {\w} (R-\to);

\foreach \from/\to in {2/1}
\draw [-, thin, dashed] (L-\from) -- node[pos=0.63,below] {20} (S-\to);

\foreach \from/\to in {3/4}
\draw [-, thin, dashed] (L-\from) -- node[pos=0.83,below] {20} (S-\to);

\foreach \from/\to in {4/3}
\draw [-, thin, dashed] (L-\from) -- node[pos=0.7,below] {20} (S-\to);

\foreach \from/\to in {5/3}
\draw [-, thin, dashed] (L-\from) -- node[pos=0.3,below] {20} (S-\to);

\foreach \from/\to in {1/2, 5/4}
\draw [-, thin, dashed] (L-\from) -- node[pos=0.63,above] {20} (S-\to);

\foreach \from/\to in {5/5}
\draw[very thick] (L-\from) -- node[midway,below] {3} (R-\to);

\foreach \from/\to/\w in {1/1/20, 2/2/20, 3/3/20, 4/4/20, 6/5/21, 7/6/21}
\draw [very thick] (L-\from) -- node[pos=0.36,below] {\w} (S-\to);
\end{tikzpicture}
\end{minipage}
\caption{An instance $R$ of $\langle |\Sigma|,m \rangle$-AP\xspace, with $k=2$ and $m=3$, a resolution vector
  set $S'$ and the associated
  graph $G_{R,S'}$\xspace. The thick edges are a maximum weight matching of $G_{R,S'}$\xspace.
The corresponding solution is made of the sets $\{r_1, r_2, r_3\}$ (cost $0$), $\{r_4, r_5\}$ (cost $2$),
$\{ r_6 ,r_7 \}$ (cost $2$).}
\end{figure}
\begin{comment}
Let $M$ be the matching of graph $G_{R,S'}$\xspace in Fig.~\ref{fig:ex-alg} made of the
thick edges.
Notice that $M$ is a maximum weight matching of $G_{R,S'}$\xspace.
The corresponding solution $\ensuremath{\Pi_{S'}}(M)$ consists of
the following sets: $C_1=\{r_1, r_2, r_3\}$, $C_2=\{r_4, r_5\}$,
$C_3=\{ r_6 ,r_7 \}$, having representative vectors $(a,a,a)$, $(a,*,a)$, $(b,b,*)$
respectively.
Each $C_2$ and $C_3$  costs $2$, while $C_1$ contributes nothing to cost.
\end{comment}

Notice that,
each vertex $\ensuremath{R_{safe}}^l(r,i)$ has only the edge
$(\ensuremath{R_{safe}}^l(r,i),T(r,i))$ on it, hence we can always add those edges to any
matching%
\footnote{Notice that these
  connected components are introduced only to simplify the
relationship between a matching $M$ and the corresponding solution
$\ensuremath{\Pi_{S'}}(M)$ of $\langle |\Sigma|,m \rangle$-AP\xspace}.
Let $M$ be a matching of $G_{R,S'}$\xspace and let $v$ be a vertex of $G_{R,S'}$\xspace, then
we say that $v$ is \emph{covered} by a matching $M$
if there exists an edge of $M$ for which $v$ is one
of its endpoints.
Moreover, we will say that $M$ is  \emph{feasible} if all vertices in $T$ are covered by $M$.
When a  matching $M$ covers all vertices in $R^l_{dist} \cup
R^l_{safe}$ and is feasible, it is defined as a \emph{complete
matching}.
Let $\Pi$ be a clustering of an instance $R$ of the $\langle |\Sigma|,m \rangle$-AP\xspace problem. Then
$\Pi$ is \emph{feasible} if and only if each set of the partition
$\Pi$ contains at least $k$ rows.
The next part of this section is devoted to show that every maximum weight matching $M$
is complete and that clustering $\ensuremath{\Pi_{S'}}(M)$ is \emph{feasible}.
First, we will show in the next two lemmata that, given $W' =
k\sum_{r_x\in T} w'(r_x)$, $W'$ is a threshold that distinguishes
between matchings that are feasible and those that are not.

\begin{Lemma}
\label{lem:eq-matching-weight-T} Let $M$ be a matching  of
$G_{R,S'}$\xspace, let $X$ be the subset of $T$ consisting of the vertices
of $T$ that are covered by $M$, and let $M_1$ be the subset of the
edges of $M$ that have one endpoint in $X$. Then the total weight
of the edges in $M_1$ is exactly $\sum_{T(t,i)\in X} w'(t)$.
\end{Lemma}
\begin{proof}
It is an immediate consequence of the observation that all edges where an
endpoint is $T(t,j)$
have the same weight $w'(t)$, with $t \in S'$.
\qed\end{proof}

\begin{Lemma}
\label{lem:eq-matching} Let $M$ be a matching  of  $G_{R,S'}$\xspace and
let $M_1$ be the subset of the edges of $M$ that have one endpoint
in $T$. Then the total weight of the edges in $M_1$ is at least
$W' = k\sum_{r\in S'} w'(r)$  if and only if $M$ is feasible.
\end{Lemma}
\begin{proof}
Let $M_1$ be the subset of the edges of $M$ that have one endpoint
in $T$, and let $W_1$ be the total weight of edges in $M_1$. An
immediate consequence of Lemma~\ref{lem:eq-matching-weight-T} is
that $W_1 = W'$ if and only if  $M_1$ is feasible.
Assume now that $M$ is not feasible, then there exists at least one vertex
$S'(x,j)\in T$ that is not covered by $M$. Again, a consequence of
Lemma~\ref{lem:eq-matching-weight-T} is that $W_1 \le W'-w'(x)$.
Let $M_2$ be the set $M\setminus M_1$. By construction, $w'(x)> W$ and $W$
is an upper bound on the total weight of $M_2$, therefore $W_1 + w_h(M_2) < W'$,
completing the proof.
\qed\end{proof}

Using Lemmata~\ref{lem:eq-matching-weight-T} and \ref{lem:eq-matching},
we can prove Lemma~\ref{lem:feas:solution}.

\begin{Lemma}
\label{lem:feas:solution}
Let $M$ be a maximum weight matching of $G_{R,S'}$\xspace, then $M$ is complete and
the solution $\ensuremath{\Pi_{S'}}(M)$ computed by Algorithm~\ref{alg:matching} is
feasible.
\end{Lemma}

\subsection{Proving the optimality of $\ensuremath{\Pi_{S'}}(M)$}
\label{subsect_opt_solution}

This section is devoted to prove that, starting from a maximum
weight matching $M$, Algorithm~\ref{alg:matching} computes an optimal
solution $\ensuremath{\Pi_{S'}}(M)$ of $\langle |\Sigma|,m \rangle$-AP\xspace.
In order to prove that any maximum weight matching $M$ of
the graph $G_{R,S'}$\xspace
leads to an optimal solution of $\langle |\Sigma|,m \rangle$-AP\xspace over instance $R$,  we are going
to prove that
$\sum_{(u,v) \in M} w_h\left((u,v)\right) \geq (W+1)k|S'|+m|R^l_{dist} \cup R^l_{safe}
\cup R'^l_{safe}| - e$
if and only if $\langle |\Sigma|,m \rangle$-AP\xspace over instance $R$ admits a solution with
cost not greater than $e$, and such solution is computed by applying
Algorithm~\ref{alg:matching}.
Such result will be obtained through a sequence of technical lemmata.

Since $M$ is a maximum weighted matching,
we can assume by Lemma~\ref{lem:feas:solution} that $M$ is complete.
Given a complete matching $M$, we denote by $M(T)$
the set of  edges of $M$ with one endpoint in
$R^l_{dist} \cup R^l_{safe} \cup R'^l_{safe}$ and one endpoint in $T$,
while we denote by $M(L)$ the set of those edges of $M$ that have
one endpoint in
$R^l_{dist} \cup R^l_{safe}$ and one endpoint in $R^r_{dist} \cup R^r_{safe}$.
Furthermore, let us denote by $V(T)$ the set of vertices of
$R^l_{dist} \cup R^l_{safe} \cup R'^l_{safe}$ that are endpoints of an edge in
$M(T)$ and by $V(L)$ the set of vertices of
$R^l_{dist} \cup R^l_{safe}$ that are endpoints of an edge in
$M(L)$. Notice that by definition of $V(L)$ and, by definition of
complete matching,
$V(T) \cup V(L) = R^l_{dist} \cup R^l_{safe} \cup R'^l_{safe}$.
Finally, let us denote by $R(L)$ the set of rows in $R$
associated with the vertices in $V(L)$.
Lemma~\ref{lem:cost:match:part:feas} shows how the
weight of a complete matching $M$ is related to the edge weights of
$G_{R,S'}$\xspace.

\begin{Lemma}
\label{lem:cost:match:part:feas}
Let $M$ be a complete matching of $G_{R,S'}$\xspace,
and let $w_h(M)$ be the total weight of $M$. Then
\begin{comment}
\begin{align*}
\label{eq:weigth:matching}
w_h(M) & = k \sum_{r \in S'} ( W + m -del(r)+1) + \sum_{r \in R(L)} (m - del(r)) =\\
 & = (W+1) k |S'| + m |R^l_{dist} \cup R^l_{safe} \cup R'^l_{safe}|- (k\sum_{r \in S'} del(r)
+ \sum_{r \in R(L)} del(r)).
\end{align*}
\end{comment}
$w_h(M) = k \sum_{r \in S'} ( W + m -del(r)+1) + \sum_{r \in R(L)} (m - del(r)) =
(W+1) k |S'| + m |R^l_{dist} \cup R^l_{safe} \cup R'^l_{safe}|- (k\sum_{r \in S'} del(r)
+ \sum_{r \in R(L)} del(r))$.
\end{Lemma}
\begin{comment
\begin{proof}
The total weight $w_h(M)$ of the matching $M$
is defined as $
w_h(M) =  \sum_{(u,v) \in M(T)} w_h((u,v)) + \sum_{(u,v) \in M(L)} w_h(u,v)$.
By Lemma~\ref{lem:eq-matching} and by definition of the weight function $w_h$,
 $w_h(M) = k\sum_{r \in S'} w'(r) + \sum_{r \in R(L)} (m - del(r))$
and by definition of $w'(r)$ it holds $w_h(M) = k \sum_{r \in S'} ( W + m -del(r)+1) + \sum_{r \in R(L)} (m - del(r))$.
Hence
$w_h(M) =  (W+m+1) k |S'| - k \sum_{r \in S'} del(r) + \sum_{r \in R(L)} m - \sum_{r \in R(L)} del(r)$ .
By definition of feasible matching and by
Lemma~\ref{lem:prop:match:part:feas},
$|V(T)|=|T|$.
Furthermore, since $|T| = k |S'|$,
then $mk|S'| = m |T|= m |V(T)|$. By construction $\sum_{r \in R(L)} m = m|V(L)| $
and $V(T) \cup V(L) = R^l_{dist} \cup R^l_{safe}$.
Hence $w_h(M) = (W+1) k |S'| + m |R^l_{dist} \cup R^l_{safe}|- (k\sum_{r \in S'} del(r)
+ \sum_{r \in R(L)} del(r))$.
\qed\end{proof}
\end{comment}

In the next two lemmata, we will show that: (i) given an instance $R$
of $\langle |\Sigma|,m \rangle$-AP\xspace, if there exists a solution of $\langle |\Sigma|,m \rangle$-AP\xspace over $R$
that suppresses at most $e$ entries then
the graph $G_{R,S'}$\xspace associated with $R$ admits
a complete matching of $G_{R,S'}$\xspace with total weight
$w_G(M) \geq (W+1) k |S'| + m |R^l_{dist} \cup R^l_{safe} \cup R'^l_{safe}|- e$;
(ii) given a complete matching of the graph $G_{R,S'}$\xspace of total weight
$w_G(M) \geq (W+1) k |S'| + m |R^l_{dist} \cup R^l_{safe} \cup R'^l_{safe}|- e$,
Algorithm~\ref{alg:matching} returns a solution $\ensuremath{\Pi_{S'}}(M)$
of $\langle |\Sigma|,m \rangle$-AP\xspace that suppresses at most $e$ entries.
These lemmata, coupled with Lemma~\ref{lem:feas:solution},
prove the correctness of Algorithm~\ref{alg:matching} in
Theorem~\ref{theo:correctness-algorithm}.

\begin{Lemma}
\label{lem:from-partially-feasible-solution-to-matching}
Let $R$ be an instance of $\langle |\Sigma|,m \rangle$-AP\xspace{}, let $\ensuremath{\Pi_{S'}}$ be a feasible
solution of $\langle |\Sigma|,m \rangle$-AP\xspace{} over instance $R$ that suppresses at most $e$ entries,
let $G_{R,S'}$\xspace be the graph associated with $R$ and $S'$.
Then there exists a complete  matching of $G_{R,S'}$\xspace with total weight
$w_G(M) \geq (W+1) k |S'| + m |R^l_{dist} \cup R^l_{safe} \cup R'^l_{safe}|- e$.
\end{Lemma}

\begin{Lemma}
\label{lem:feasible_matching-solution}
Let $R$ be an instance of $\langle |\Sigma|,m \rangle$-AP\xspace, let $G_{R,S'}$\xspace be the graph associated with $R$, and
let $M$ be a complete matching of $G_{R,S'}$\xspace of weight
$w_h(M) \geq (W+1) k |S'| + m |R^l_{dist} \cup R^l_{safe} \cup R'^l_{safe}|- e$.
Then, starting from the
matching $M$ of $G_{R,S'}$\xspace, Algorithm~\ref{alg:matching} computes a
feasible solution $\ensuremath{\Pi_{S'}}(M)$ of $\langle |\Sigma|,m \rangle$-AP\xspace over instance $R$, where there are at
most $e$ suppressions.
\end{Lemma}
\begin{proof}
Since $M$ is complete, for each vertex $T(x,j)$ of $T$, with $1 \leq j \leq k$,
there exists an edge  $(v, T(x,j))\in M$ for some
$v \in (R^l_{dist} \cup R^l_{safe} \cup R'^l_{safe})$. Then
Algorithm~\ref{alg:matching} defines a solution $\ensuremath{\Pi_{S'}}(M)$ for $\langle |\Sigma|,m \rangle$-AP\xspace
assigning, for each edge $(v, T(x,j))$,
the row $r$ corresponding to vertex $v$
to the set that has resolution vector $x$.
More precisely, row $r$ is defined by
Algorithm~\ref{alg:matching} as the $j$-th element of the set
that has resolution vector $x$.
Therefore each set associated with a resolution row $x \in S'$ will consist of
at least $k$ rows compatible with $x$.
Hence  $\ensuremath{\Pi_{S'}}(M)$ is a feasible solution.

Recall that $M$ has a total weight of at least
$(W+1) k |S'| + m |R^l_{dist} \cup R^l_{safe} \cup R'^l_{safe}|- e$.
We will prove that $\ensuremath{\Pi_{S'}}(M)$ induces at most $e$ suppressions.
By  Lemma~\ref{lem:cost:match:part:feas},
$
w_h(M) = k \sum_{r \in S'} ( W + m -del(r)+1) + \sum_{r \in R(L)} m - del(r)
= (W+1) k |S'| + m |R^l_{dist} \cup R^l_{safe} \cup R^l_{safe}|- (k\sum_{r \in S'} del(r) + \sum_{r \in R(L)} del(r))
\geq (W+1) k |S'| + m |R^l_{dist} \cup R^l_{safe} \cup R^l_{safe}|- e
$
where
$k \sum_{r \in S'} del(r) + \sum_{r \in R(L)} del(r) \leq e$.
Notice that, by definition of  $\ensuremath{\Pi_{S'}}(M)$, each vertex of $V(T)$ corresponds to
a row in $R$ assigned to a set with a resolution vector in $S'$. Such rows
associated with $V(T)$ induce
a cost in $\ensuremath{\Pi_{S'}}(M)$ of $k \sum_{r \in S'} del(r)$. Furthermore, the vertices of $V(L)$
corresponds to rows of $R$  inducing a cost of at most
$\sum_{r \in R(L)} del(r)$.
Therefore $\ensuremath{\Pi_{S'}}(M)$ induces $k \sum_{r \in S'} del(r) + \sum_{r \in R(L)} del(r) \leq e$
suppressions.
\qed\end{proof}

\begin{Theorem}
\label{theo:correctness-algorithm}
Let $R$ be an instance of $\langle |\Sigma|,m \rangle$-AP\xspace. Then
Algorithm~\ref{alg:solving-AP} returns a solution  $\ensuremath{\Pi_{S'}}(M)$ of cost at most $e$ if and only if
such a solution exists.
\end{Theorem}
\begin{proof}
By Lemma~\ref{lem:feas:solution}, $\ensuremath{\Pi_{S'}}(M)$ is feasible.
Hence if $\ensuremath{\Pi_{S'}}(M)$ suppresses at most $e$ entries, then $\langle |\Sigma|,m \rangle$-AP\xspace admits a solution
of cost at most $e$.
On the other hand, by
Lemma~\ref{lem:from-partially-feasible-solution-to-matching},
if there exists a solution $\Pi'$ of
$R$ that suppresses
at most $e$ entries, then there exists a feasible matching $M$ with
weight $w_G(M) \geq (W+1) k |S'| + m |R^l_{dist} \cup R^l_{safe} \cup R'^l_{safe}|- e$.
Then, by Lemma~\ref{lem:feasible_matching-solution},
Algorithm~\ref{alg:solving-AP} returns a solution $\ensuremath{\Pi_{S'}}(M)$ of \smA

that suppresses at most $e$ entries.
\qed\end{proof}

If $\langle |\Sigma|,m \rangle$-AP\xspace admits a solution that suppresses at most $e$ entries,
then there  exists a set $S^*$ of resolution vectors such that
$\Pi_{S^*}$ is a solution for $\langle |\Sigma|,m \rangle$-AP\xspace with resolution vectors $S^*$
with the property that $\Pi_{S^*}$ suppresses at most $e$ entries.
Now, there exist $O(2^{(|\Sigma|+1)^m})$ possible sets of resolution vectors and
the construction of graph $G_{R,S'}$\xspace requires $O(k|S^*||R|) \leq O(k e |R|) \leq O(kmn^2)$.
A maximum matching $M$ of a bipartite graph
can be computed in polynomial time~\cite{fastmwb}
and starting from $M$, we can compute a solution of the $\langle |\Sigma|,m \rangle$-AP\xspace
in time $O(|M|) \leq O(m)$. Hence the overall time complexity of the algorithm
is $O(2^{(|\Sigma|+1)^m}kmn^2)$.

\section{APX-hardness of $3$-AP($3$)}
\label{sec:AP-3-3}

In this section we investigate the computational and approximation complexity of
$3$-AP($3$), that is $k$-AP when each row
consists of exactly $3$ columns and $k=3$.
We show that $3$-AP($3$) is APX-hard
via an L-reduction
from Minimum Vertex Cover on Cubic Graphs (MVCC), which is known to be
APX-hard~\cite{AK92}.
Due to page limit, we only  sketch  the proof.
The MVCC problem, given a cubic graph $G=(V,E)$, asks for a smallest
$C \subseteq V$ such that each edge of $G$ has at least one
of its endpoints in $C$.
\begin{comment
Let us introduce the MVCC problem.

\begin{Problem}MVCC.\\
\textbf{Input}: a cubic graph $G=(V,E)$.\\
\textbf{Output}: a subset $C \subseteq V$ of minimum cardinality, such that for each edge
$(v_i,v_j) \in E$, at least one of $v_i$ or $v_j$ belongs to $C$.
\end{Problem}
\end{comment}

Let $G=( V , E )$ be instance of MVCC, where $|V|=n$ and $|E|=m$.
The reduction builds an
instance $R$ of $3$-AP($3$) associating with each vertex $v_i \in V$
a set $R_i$ consisting of $9$ rows, and with each edge $e=(v_i, v_j) \in E$ a set
$E_{i,j}$ consisting of $7$ rows.
Finally, a set $X$ of $3$ more rows is added to $R$.
\begin{comment}
The main idea of the reduction is that some of the rows are identical and can
therefore be grouped together. Since our construction do not allow to have
three identical rows, the cost of a cluster must be either three times, or
twice, or equal to the number of rows of the cluster. We will call such
clusters respectively \emph{toxic}, \emph{bad}, or \emph{good}. We
will restrict our attention to canonical solutions where, among other
properties, toxic clusters are only a fixed number, therefore we are able to
relate the size of a vertex cover of $\mathcal{G}$ to the number of bad clusters in
a solution of $R$.

We can build an auxiliary graph $G_1$ whose vertices are the groups of identical
rows of $R$, and two vertices are adjacent in $G_1$ if and only if the
corresponding rows have Hamming distance $1$. The auxiliary graph has a very
precise structure; in fact each vertex of $G$ corresponds to a subgraph of
$G_1$ consisting of a triangle and three external (called docking) vertices,
each of which is connected with a vertex of the triangle.
Each edge $(v_i,v_j)$ of $G$ corresponds to a 4-edge path of $G_1$ connecting two docking
vertices of $v_i$ and $v_j$, as well as three disconnected vertices.
An example of auxiliary graph on two vertices connected by an edge is
represented in Fig.~\ref{fig:graph-dist-1}.

A canonical solution of $R$ consists of merging together some groups that form
a clique in the auxiliary graph. Consider now the subgraph of $G_1$ that is
associated to a vertex of $G$. In such subgraph, either the triangle is grouped
together (in which case the corresponding vertex of $G$ belongs to the encoded
vertex cover) or each docking vertex $d$ is grouped together with the only
vertex of the triangle to which $d$ is adjacent (in which case the
corresponding vertex of $G$ does not belong to the encoded
vertex cover).
\end{comment}

Now we can describe formally our reduction.
Let $R_i$ be the set of rows associated with vertex $v_i \in V$.
The rows in $R_i$ have values over an alphabet
$\Sigma_i= \{ \sigma_i, \sigma_{i,1}, \sigma_{i,2}, \sigma_{i,3}  \}$.
The set $R_i$ consists of $9$ rows belonging to $6$ groups,
denoted by $g_1(v_i), \dots , g_6(v_i)$, of identical rows.
The representative rows of groups $g_1(v_i), \dots , g_6(v_i)$, and the cardinality of the groups,
are defined as follows:

\vspace*{0.12cm}
- $r(g_h(v_i))=\sigma_{i,h} \sigma_i \sigma_{i,h}$,
    with $h \in \{ 1,2,3 \}$; each group $g_h(v_i)$,  with $h \in \{ 1,2,3 \}$, consists of exactly two rows;

- $r(g_{3+h}(v_i))= \sigma_i \sigma_i \sigma_{i,h}$, with $h \in \{ 1,2,3 \}$;
each group $g_{3+h}(v_i)$, with $h \in \{ 1,2,3 \}$, consists of exactly one row.
\vspace*{0.12cm}

Notice that given two rows $r,r'$ belonging to different groups of $R_i$,
$H(r,r')=1$ iff $r \in g_h(v_i)$, $r' \in g_{3+h}(v_i)$ (or the converse) or
$r,r' \in \{ g_4(v_i), g_5(v_i), g_6(v_i)\}$.
Given a group $g_h(v_i)$, with $h \in \{ 1,2,3 \}$, each symbol $\sigma_{i,h}$
is called the \emph{private} symbol of  $g_h(v_i)$.
The groups of rows $g_j(v_i)$,  with $j \in \{ 1,2,3\}$, are denoted as the
\emph{docking groups} of $R_i$, and each of them is associated with a set $E_{i,h}$
of rows encoding an edge $(v_i,v_h)$ of $G$.
More precisely, given the set of rows $E_{i,j}$, we denote by
$d_{i,j}(g(v_i))$ the docking group of $R_i$ associated with set $E_{i,j}$.

Now, let us build the set $E_{i,j}$ of rows associated with an edge $(v_i,v_j)$.
Let $d_{i,j}(g(v_i))$ and $d_{i,j}(g(v_j))$ be the two docking groups of $R_i$ and $R_j$ respectively,
associated with the set $E_{i,j}$.
Let $\sigma_{i,x}$ and $\sigma_{j,y}$ be the private symbols of groups $d_{i,j}(g(v_i))$ and $d_{i,j}(g(v_j))$
respectively.
The set
$E_{i,j}$  consists of $7$ rows distributed in $6$ groups.
The rows of $E_{i,j}$ have values over alphabet
$\Sigma_{i,j} = \{  \sigma_{i,x}, \sigma_{j,y} ,  \sigma_{i,j} , \sigma_{i,j,4}, \sigma_{i,j,5},
\sigma_{i,j,6} \}$.
Let us define the representative rows and the cardinality of the groups in $E_{i,j}$:

\vspace*{0.15cm}
- $r(g_1(v_i,v_j))= \sigma_{i,x} \sigma_{i,j} \sigma_{i,x}$;
group $g_1(v_i,v_j)$ consists of a single row;

- $r(g_2(v_i,v_j))= \sigma_{i,x} \sigma_{i,j} \sigma_{j,y}$; group $g_2(v_i,v_j)$ consists of two rows;

- $r(g_3(v_i,v_j))= \sigma_{j,y} \sigma_{i,j} \sigma_{j,y}$;
group $g_3(v_i,v_j)$ consists of a single row;

- $r(g_t(v_i,v_j))= \sigma_{i,j,t} \sigma_{i,j} \sigma_{i,j,t}$, with $t \in \{ 4,5,6 \}$;
each group $g_t(v_i,v_j)$, with $t \in \{ 4,5,6 \}$, consists of a single row.

\vspace*{0.15cm}

The group of $E_{i,j}$ that has two occurrences of symbol $\sigma_{i,x}$ shared with
$d_{i,j}(g(v_i))$ is called the $i$-group of set $E_{i,j}$, and is denoted as
$g^i(v_i,v_j)$.
Notice that, given two rows $r,r'$ of $R_i$, $E_{i,j}$ respectively, then
$H(r,r')=1$ iff $r \in d_{i,j}(g(v_i))$ and $r' \in g^i(v_i,v_j)$.

Finally, a set $X$ of $3$ rows $x_1, x_2, x_3$ are added to $R$. The rows in
$X$ have values over an alphabet $\Sigma_x$ disjoint from any other set $\Sigma_i$, $\Sigma_{i,j}$.
Each row $x_i=w_i^3$, and it has Hamming distance $3$ from any other row of $R$.
Therefore for any set $C$ containing some rows $x_i$, all  positions
of a row in $C$ will be suppressed.
\begin{comment
It is easy to see that, by construction, the following properties hold.

\begin{Proposition}
\label{prop:dist-vertex-rows}
Let $r_a$, $r_b$ be two rows of $R_i$, with $r_a=g_j(v_i)$ and
$r_b=g_l(v_i)$, $j < l$. Let $r_c$ be a row of $R_j$, with
$i \neq j$. Then:

\begin{itemize}

\item $H(r_a, r_c)=H(r_b, r_c)=3$;

\item $H(r_a,r_b) \leq 2$;

\item $H(r_a,r_b) = 1$ iff $r_a=g_h(v_i)$ and $r_b=g_{h+3}(v_i)$, with
$1 \leq h \leq 3$, or $r_a=g_h(v_i)$ and $r_b=g_l(v_i)$, with
$4 \leq j \leq l \leq 6$.

\end{itemize}

\end{Proposition}

\begin{Proposition}
\label{prop:dist-edge-rows}
Let $r_a$, $r_b$ be two rows of $E_{i,j}$, with $r_a \in g_h(v_i,v_j)$ and
$r_b \in g_l(v_i,v_j)$, with $h < l$. Let $r_c$, $r_d$ be two rows of $R_i$ and $R_p$,
with $p \neq i,j$, and let
$r_e$ be a row of $E_{t,z}$,  with $t \neq i$ or $z \neq j$. Then:

\begin{itemize}

\item $H(r_a, r_b) \leq 2$;

\item $H(r_a,r_b) = 1$ iff $r_a=g_h(v_i,v_j)$ and $r_b=g_{h+1}(v_i,v_j)$, with
$1 \leq h \leq 2$;

\item $H(r_a, r_c) = 1$ iff $r_c$ is in the docking group $d_{i,j}(g(v_i))$ of $R_i$
and $r_a$ is in the group $g^i(v_i,v_j)$;

\item $H(r_a, r_c) = 2$ only if $r_c$ is in a group adjacent to $d_{i,j}(g(v_i))$;

\item $H(r_a, r_d) = 3$;

\item $H(r_a, r_e) = 3$.

\end{itemize}

\end{Proposition}

In what follows, by an abuse of notation, we may use a group $g(\cdot{})$ to denote its representative row $r_g(\cdot{})$.
Fig.~\ref{fig:graph-dist-1} shows the groups of $R_i$, $R_j$, $E_{i,j}$. Each group
of identical rows si represented with a vertex, while an edge
joins two vertices iff the corresponding groups are at Hamming distance $1$.

\begin{figure}[htb!]
\begin{center}
\includegraphics[width=12cm]{3-3-red}
\label{fig:graph-dist-1}
\caption{Groups at Hamming distance $1$ in $R_i$, $R_j$, $E_{i,j}$:
  vertices represent groups, while an edge joins two vertices
  representing groups at Hamming distance $1$.}
\end{center}
\end{figure}

Before giving the details of the reduction, we present the general idea of the reduction.
The idea is that we can define a solution such that
the set of rows of $R_i$ can be clustered only with rows at Hamming distance $1$.
Hence, by Prop.~\ref{prop:dist-vertex-rows} and Prop.~\ref{prop:dist-edge-rows},
there exist only two possible solutions for the rows of $R_i$:
either each group $g_{t}(v_i)$, with $t \in \{ 1,2,3 \}$, is co-clustered
with its adjacent group $g_{t+3}(v_i)$ (this case corresponds to a vertex $v_i$
in the vertex cover), or each docking group $d_{i,j}(v_i)$ of $R_i$ is
co-clustered with the $i$-group of $E_{i,j}$, while all the groups
$g_{t}(v_i)$, with $t \in \{ 4,5,6 \}$ are co-clustered
(this case corresponds to a vertex $v_i$ not in the vertex cover).
\end{comment}

Now, consider the set $R_i$. The following lemma
gives a lower bound on the cost of an optimal solution of $3$-AP($3$) over instance
$R_i$.

\begin{Lemma}
\label{lem:opt-R_i}
Let $R_i$ be a set of rows, then an optimal solution of
$3$-AP($3$) over instance $R_i$ has a cost of at least $9$.
\end{Lemma}
\begin{comment
\begin{proof}
Let us consider the set of $9$ rows, distributed in $6$ groups, of $R_i$.
As none of the group of $R_i$ consists of at least $3$ rows, it follows that
each row will have a cost of at least $1$, hence
the lemma follows.
\end{proof}
\end{comment}

\begin{comment
First, we give the definition
of canonical solution, then we present the definition of \emph{type a } and \emph{type b } solutions.
\end{comment}

The main idea of the reduction is showing that we can consider a set of solutions,
called \emph{canonical solutions}, that is solutions where:

\vspace*{0.15cm}
(i) $\Pi$ contains exactly one cluster $X$ containing only suppressed  entries;

(ii)  each set $R_i$ is associated with either a \emph{type a } or a \emph{type b } solution
(to be defined later), eventually with the contribution of
some rows in the sets $E_{i,j}$ for a \emph{type b } solution;

(iii) two sets $R_i$, $R_j$ are associated with a \emph{type b } solution
only if there is no edge set $E_{i,j}$ in the instance $R$, that is
the corresponding vertices $v_i$, $v_j$ are not adjacent in $G$;

(iv) either an edge set is part of a \emph{type b } solution of some set $R_i$ and has a total cost of $10$ or
it has a total cost of $11$.

\vspace*{0.15cm}
Notice that, by construction, in a canonical solution, rows $x_1, x_2, x_3 \in X$.

Let us define the notions of \emph{type a } and \emph{type b } solution. Given a set $R_i$ and the
edge sets $E_{i,j}$, $E_{i,h}$, $E_{i,l}$, a \emph{type a } solution for $R_i$
consists of three sets $S_{i,1}, S_{i,2}, S_{i,3}$,
where $S_{i,t}=g_t(v_i) \cup g_{t+3}(v_i)$, while
a \emph{type b } solution
consists of the following sets:
(i) three sets $d_{i,j}(g(v_i)) \cup g^i(v_i,v_j)$,
$d_{i,h}(g(v_i)) \cup g^i(v_i,v_h)$, $d_{i,l}(g(v_i)) \cup g^i(v_i,v_l)$;
(ii) $g_4(v_i) \cup g_5(v_i) \cup g_6(v_i)$.

Lemma~\ref{lem:compute-canonical} is the main technical contribution of this section.
\begin{Lemma}
\label{lem:compute-canonical}
Let $\Pi$  be a solution of $3$-AP($3$) over instance $R$. Then we can compute in polynomial time a canonical solution $\Pi'$ of $3$-AP($3$) over instance $R$ such that $c(\Pi') \leq c(\Pi)$.
\end{Lemma}
\noindent
\emph{Sketch of the proof.}
By direct inspection, it is immediate to notice that \emph{type a } and \emph{type b }
solutions induce $9$ suppression
in rows of $R_i$ hence, by Lemma~\ref{lem:opt-R_i}, they are optimal for $R_i$.
The next step is computing in polynomial time a solution $\Pi''$ such that
each set $R_i$  is associated
in $\Pi''$ only with either a \emph{type a } or \emph{type b } solution, and such that $c(\Pi'')
\leq c(\Pi)$.
Such step is obtained by exploiting the optimality of \emph{type a } and \emph{type b } solutions
for $R_i$, and some properties of the instance $R$.

Then, starting from such solution $\Pi''$, we can compute in polynomial time
a canonical solution $\Pi'$ such that
$c(\Pi') \leq c(\Pi'')$. The main idea to prove this result is that for any
two sets $R_i$, $R_j$, such that both $R_i$ and $R_j$ are associated
with a \emph{type b } solution in $\Pi''$ and $E_{i,j}$ is part of the instance $R$,
then we can improve the solution by imposing
a \emph{type a } solution for  $R_i$.
\qed

\vspace*{0.15cm}

A consequence of Lemmata~\ref{lem:opt-R_i} and~\ref{lem:compute-canonical}
and some properties of the instance $R$, is Lemma~\ref{lem:apx-hard1}.

\begin{Lemma}
\label{lem:apx-hard1}
Let $\Pi$ be a solution of $3$-AP($3$) over instance $R$
of cost $6|V|+3|C|+11|E|+9$, then
we can compute in polynomial time a solution of MVCC over instance $G$ of size $C$.
\end{Lemma}
\begin{proof}
Let us consider a canonical solution of $3$-AP($3$).
First ,notice that the three rows $w_1$, $w_2$, $w_3$ provide together a cost of $9$.
Since two sets of rows are associated with a \emph{type b } solution only if there does not
exist a set $E_{i,j}$, on the contrary, given an edge set $E_{i,j}$
at least one of the set $R_i$ and $R_j$ is associated with a \emph{type a } solution.
Consequently, the set of rows associated with a \emph{type a } solution corresponds
to a vertex cover of the graph $G$.

Now consider the cost of a canonical solution. For each set $R_i$ of rows associated
with a \emph{type b } solution, we can show that each of the three edge sets
$E_{i,j}$, $E_{i,h}$, $E_{i,l}$ has a cost of $10$. Notice that, given
an edge set $E_{i,j}$,
if both sets $R_i$, $R_j$ are associated with \emph{type a } solutions, then we can show
that the edge set $E_{i,j}$ has a cost of $11$.
Accounting this decreasing of the cost of the edge sets to the set $R_i$ of
rows with a \emph{type b } solution, is equivalent to assign to a \emph{type b } solution a cost
equal to  $6$, while a \emph{type a } solution has a cost equal to $9$.
\end{proof}

Similarly to Lemma~\ref{lem:apx-hard1}, we can prove that
starting from a solution $C$ of MVCC over instance $G$, we can compute
in polynomial time a solution $\Pi$ of $3$-AP($3$) over instance $R$
of cost $6|V|+3|C|+11|E|+9$.
Therefore
$3$-AP($3$) is APX-hard.

\begin{comment
Now, we prove some properties of a canonical solution.
\end{comment}
\begin{comment
\begin{Lemma}
\label{lem:opt-ty_a}
Let $R_i$ be a set of rows. Then  a solution of $3$-AP($3$) over instance $R$ induces an optimal cost
for the set $R_i$ if it is a \emph{type a } solution.
\end{Lemma}
\begin{proof}
By construction, a \emph{type a } solution is an optimal solution over instance $R_i$, as each
row has a cost of $1$ in a \emph{type a } solution.
\end{proof}
\end{comment}
\begin{comment
Now, in Lemma~\ref{lem:cost-ty_b}, we will prove a property
of a \emph{type b } solution over the sets $R_i$, $E_{i,j}$, $E_{i,h}$, $E_{i,k}$. The
proof is omitted due to page constraints.

\begin{Lemma}
\label{lem:cost-ty_b}
Let $S$ be a \emph{type b } solution of $3$-AP($3$) over instance
$R_i \cup E_{i,j} \cup E_{i,h} \cup E_{i,k}$, then $S$ suppresses $9$ entries in the rows of $R_i$,
and $10$ entries in the rows of each edge set in $E_{i,j} \cup E_{i,h} \cup E_{i,k}$.
\end{Lemma}

\begin{proof}
By construction each set of a \emph{type b } solution
containing a docking group of $R_i$ consists of three rows, where exactly one position is suppressed
for each row by Prop.~\ref{prop:dist-edge-rows}.
The cluster $g_4(v_i) \cup g_5(v_i) \cup g_6(v_i)$ consists of $3$ rows, where exactly one position
is suppressed for each row.
The set consisting of the rows in $g_t(v_i,v_j)$, with $t \in \{4,5,6 \}$, consists
of three rows, where two positions for each row are deleted.
Finally, each set $g_2(v_i,v_j) \cup g^j(v_i,v_j)$,
contains three rows, where exactly one position is suppressed for each row.
By a simple counting argument, the rows of $R_i$ have a total cost of $9$,
while the total cost of each edge set is $10$.
\end{proof}
\end{comment}
\begin{comment
\begin{Lemma}
\label{lem:set-X}
Let $S$ be a solution of $3$-AP($3$) over instance $R$,
then we can compute in polynomial time a solution $S'$ such that
$c(S') \leq c(S)$ and $S'$ contains at most one set suppressing
three entries for each row.
\end{Lemma}
\begin{proof}
Assume that solution $S$ contains sets $Y_1, \dots, Y_p$, with $ p \geq 2$, such that
all the positions of the rows in $Y_j$ are suppressed. Then we can compute
in polynomial time a solution $S'$ by merging the set $Y_1, \dots, Y_p$ in a single
cluster $Y$. Notice that $c(S') \leq c(S)$, as in both solution $S'$ and $S$
three positions are suppressed for each row $r \in \bigcup_{j=1 \dots p}Y_j$.
\end{proof}
\end{comment}

\begin{comment
section is devoted to show that,
given a solution $\Pi$ of $3$-AP($3$),
we can compute in polynomial time a \emph{canonical solution} $\Pi'$
of $3$-AP($3$), such that $c(\Pi) \geq c(\Pi')$ (Lemma~\ref{lem:compute-canonical}).
Let us first introduce some properties of a solution of $3$-AP($3$)
over instance $R$.

\begin{Lemma}
\label{lem:cost-edge-mand-set}
Let $\Pi$ be a solution of $3$-AP($3$) over instance $R$, we can compute in polynomial time
a solution $\Pi'$ such that
\begin{enumerate}
\item for each edge set $E_{i,j}$, $\Pi'$ has a set $S_{i,j}$ containing the rows of groups $\bigcup_{t = 4,5,6} g_t(v_i,v_z)$, such that for each row in $S_{i,j}$ exactly two positions are removed;
\item $c(\Pi') \leq c(\Pi)$.
\end{enumerate}
\end{Lemma}
\begin{proof}
First, notice that by Prop.~\ref{prop:dist-edge-rows} the rows in the groups
$\cup_{t = 4,5,6} g_t(v_i,v_j)$ have distance smaller than $3$ only
w.r.t. rows of $E_{i,j}$.
Furthermore, notice that, by construction, each row in $\bigcup_{t = 4,5,6} g_t(v_i,v_j)$
may be equal to another row of $R$ only in the second position.

Assume that there exist clusters $S_1, S_2, S_3$ (at most one of these clusters can be empty)
containing the rows of $\bigcup_{t = 4,5,6} g_t(v_i,v_j)$,
such that at most two entries are suppressed for each row of the cluster
$S_j$, $j \in \{ 1,2,3 \}$. Then, for each row in $S_1 \cup S_2 \cup S_3$,
the positions $1$ and $3$ are suppressed.
Hence, we can merge clusters $S_1, S_2, S_3$, without increasing the cost of the solution,
obtaining one set that contains the rows $\bigcup_{t = 4,5,6} g_t(v_i,v_z)$.

Assume that some rows of $\cup_{t = 4,5,6} g_t(v_i,v_j)$ are in the cluster $X$
and some rows of $\cup_{t = 4,5,6} g_t(v_i,v_j)$ are in  a different cluster $Y$,
such that at most two entries are suppressed for each row of the cluster
$Y$.
Then we can move the rows of $\cup_{t = 4,5,6} g_t(v_i,v_j) \cap X$ to $Y$, decreasing the
cost of the solution.

Now, assume that these rows are all clustered in set $X$. It follows that each row
of $\cup_{t = 4,5,6} g_t(v_i,v_j)$ have a cost of $3$. Hence, we can move
this set of rows to a new set $\cup_{t = 4,5,6} g_t(v_i,v_j)$,
decreasing the cost of the solution.
\end{proof}

\begin{Lemma}
\label{lem:cost-vert-adj-opt}
Let $R_i$, $R_j$ be two set of rows and let $E_{i,j}$ be an edge set of $R$.
Let $\Pi$ be a solution of $3$-AP($3$) over instance $R$ that associates a \emph{type b } solution
with both $R_i$, $R_j$.
Then we can compute in polynomial time a solution $\Pi'$ of $3$-AP($3$) over instance $R$
where exactly one of $R_i$, $R_j$ is associated with a \emph{type b } solution and
such that $c(\Pi') \leq c(\Pi)$.
\end{Lemma}
\end{comment}
\begin{comment
\begin{proof}
Notice that, by Prop.~\ref{prop:dist-edge-rows}, the rows of group $g_2(v_i,v_j)$
have Hamming distance $1$ only from the rows of $g_1(v_i,v_j)$ and
$g_3(v_i,v_j)$. Since in a \emph{type b } solution the rows of $g_1(v_i,v_j)$ and
$g_3(v_i,v_j)$ are co-clustered with rows of $R_i$ and $R_j$, it follows that
the rows of $g_2(v_i,v_j)$ are co-clustered in $\Pi$ with rows at Hamming distance
at least $2$. Hence, $\Pi$ suppresses two entries in each row of $g_2(v_i,v_j)$,
and as $g_2(v_i,v_j)$ consists of $2$ rows, at least $4$ entries of rows
in $g_2(v_i,v_j)$ are suppressed in $\Pi$.
Notice that, as $R_i$ and $R_j$ are associated with \emph{type b } solutions in $\Pi$, the only rows that can be clustered
with the rows of $g_2(v_i,v_j)$ are those of groups  $g_4(v_i,v_j)$, $g_5(v_i,v_j)$, $g_6(v_i,v_j)$.

Let us compute a solution $\Pi'$ of $3$-AP($3$) over instance $R$ as follows.
Define a \emph{type a } solution for $R_i$; co-cluster the row in group $d_j(v_i)$
with the rows in group $g^i(v_i,v_j)$; for each row of a group
$g^i(v_i,v_z)$ in a edge set $E_{i,z}$, with $z \neq j$,
co-cluster such group $g^i(v_i, v_z)$ with the cluster containing the rows of
$\bigcup_{t = 4,5,6} g_t(v_i,v_z)$.
Notice that by Lemma~\ref{lem:cost-edge-mand-set}, we can assume that $\Pi$ has
a set $S$ containing $\bigcup_{t = 4,5,6} g_t(v_i,v_z)$, such that exactly
two entries (corresponding to the positions $1$ and $3$)
are suppressed for each row in $S$. Hence the representative row of $S$
has Hamming distance $2$ from $g^i(v_i, v_z)$, due to positions $1$ and $3$.

Now, each of these two rows $g^i(v_i, v_z)$ has a cost of $2$ in $\Pi'$, while it has a cost of $1$
in $\Pi$. Notice that each of the two rows of $g_2(v_i,v_j)$ has a cost of $2$ in $\Pi$,
while it has a cost of $1$ in $\Pi'$.
Hence, $c(\Pi')\leq c(\Pi)$.
\end{proof}

\begin{Lemma}
\label{lem:APX-edge-set-cost}
Let $\Pi$  be a solution of the $3$-AP($3$) over instance $R$, such that two sets
$R_i$, $R_j$ are not associated with a \emph{type b } solution in $\Pi$ and
$\Pi$ induces a total cost of $10$ for the rows in $E_{i,j}$.
Then at least one of $R_i$, $R_j$ has cost $11$.
\end{Lemma}
\end{comment}
\begin{comment
\begin{proof}
Assume that $\Pi$ induces a total cost of $10$ for the rows in $E_{i,j}$.
Notice that the rows in $\bigcup_{t=4,5,6}g_t(v_i,v_j)$
have a total cost of $6$, as
by Prop.~\ref{prop:dist-edge-rows} they are at Hamming distance at least $2$ from any other row
of $R$. Furthermore, the $4$ rows of $E_{i,j} \setminus \bigcup_{t=4,5,6}g_t(v_i,v_j)$
must have a cost of at least $1$ in $\Pi$.
Notice that, by construction, in $\Pi$ exactly one of
$g^i(v_i,v_j)$, $g^j(v_i,v_j)$ is clustered with
a docking group of $R_i$, $R_j$ (w.l.o.g. we assume that
$g^i(v_i,v_j)$ is clustered
with rows of $d_{i,j}(v_i)$), while one of $g^i(v_i,v_j)$, $g^j(v_i,v_j)$ (w.l.o.g. $g^j(v_i,v_j)$)
is clustered with $g_2(v_i,v_j)$, otherwise some
rows of $g_2(v_i,v_j)$ are clustered in $\Pi$ with a row at Hamming distance
at least $2$, hence the total cost of the rows in $E_{i,j}$ is greater than $10$.
But then, we claim that $\Pi$ induces a cost of at least
$11$ for the rows of the set $R_i$.

Now recall that by hypothesis
$R_i$ is not associated with a \emph{type b } solution in $\Pi$,
and let us consider the clusters containing rows of $R_i$ in $\Pi$. Notice that
if at least two rows of $R_i$ are clustered with some rows
at Hamming distance at least $2$, then $\Pi$ induces a cost of at least $11$ for the set $R_i$.
Recall that group $d_{i,j}(g(v_i))$ of $R_i$ is clustered
only with rows of group $g^i(v_i,v_j)$ of $E_{i,j}$, and consider the cases that either the three
groups of rows in $g_4(v_i), g_5(v_i), g_6(v_i)$ are co-clustered, or not.
In the former case, as
$R_i$ is not associated with a \emph{type b } solution, it follows that the rows of at least one
of the docking group of $R_i$ are clustered with rows at Hamming distance $2$;
hence $\Pi$ induces a cost of at least $11$ for the set $R_i$.
In the latter case, let us consider the group of $R_i$ (w.l.o.g. $g_4(v_i)$) adjacent to
$d_{i,j}(g(v_i))$ and let $C$ be the cluster
containing the unique row of $g_4(v_i)$. As the rows in $g_4(v_i), g_5(v_i), g_6(v_i)$ are
not co-clustered, it follows that $C$ contains a row $r$ at Hamming distance
at least $2$ from $g_4(v_i)$. If $r \in R_i$, then
$\Pi$ suppresses at least two entries of two rows of $R_i$,
namely $r$ and $g_4(v_i)$,
hence
$\Pi$ induces a cost of at least $11$ in rows of $R_i$.
If $r \notin R_i$, then $r$ must be a row at Hamming distance
$3$ from $g_4(v_i)$. Indeed by Prop.~\ref{prop:dist-vertex-rows} and by Prop.~\ref{prop:dist-edge-rows},
the rows at Hamming distance
not greater than $2$ from $g_4(v_i)$ belong to $R_i \cup (E_{i,j} \setminus \bigcup_{t=4,5,6}g_t(v_i,v_j))$.
We have assumed that $(R_i \setminus \{ g_4(v_i) \}) \cap C = \emptyset$,
and it must be $( E_{i,j}\setminus \bigcup_{t=4,5,6}g_t(v_i,v_j)) \cap C = \emptyset$,
since by hypothesis $\Pi$ induces a total  cost of $10$ for the rows in $E_{i,j}$,
hence each row in $E_{i,j} \setminus \bigcup_{t=4,5,6}g_t(v_i,v_j)$ must contain at most $1$ suppression
in $\Pi$.
Then, $g_4(v_i)$  must have
cost equal to $3$ and must be part of the cluster $X$ in $\Pi$ by the Lemma~\ref{lem:set-X}.
It follows that $\Pi$ induces a cost of at least
$11$ for the set $R_i$.
\end{proof}

\begin{Lemma}
\label{lem:compute-canonical}
Let $\Pi$  be a solution of the $3$-AP($3$) over instance $R$. Then we can compute in polynomial time a canonical solution $\Pi'$ of $3$-AP($3$) over instance $R$ such that
$c(\Pi') \leq c(\Pi)$.
\end{Lemma}
\begin{proof}
Let us consider the solution $\Pi$.
Before computing a canonical solution $\Pi'$, we
compute an intermediate solution $\Pi''$ such that
$c(\Pi'') \leq c(\Pi)$ as follows.
First, for each set $R_i$, if $R_i$ is associated with
a $\emph{type b }$ solution in $\Pi$, then define a $\emph{type b }$ solution for $R_i$ in $\Pi''$.
Otherwise, if each docking vertices $d_{i,j}(v_i)$ of a set $R_i$ is clustered in $\Pi$ with
the row of group $g^i(v_i,v_j)$ of $E_{i,j}$, then define a \emph{type b } solution for $R_i$ in $\Pi''$;
else define a \emph{type a } solution for $R_i$ in $\Pi''$. Furthermore,
define a set containing row $x_1, x_2, x_3$ in $\Pi''$.
Next, consider the rows of an edge set $E_{i,j}$, and
define a clustering of the rows not yet clustered in $\Pi''$.
If at least one of $R_i$, $R_j$
(w.l.o.g. $R_i$) is associated
with a \emph{type a } solution in $\Pi''$, then define a clustering
of the rows in $E_{i,j}$ in solution $\Pi''$ as follows:
one set contains the rows in $g^i(v_i,v_j) \cup g_2(v_i,v_j)$;
one set contains the rows in  $\bigcup_{t=4,5,6} g_t(v_i,v_j)$ and
eventually the row in $g^j(v_i,v_j)$,
in case the row in $g^j(v_i,v_j)$ are not already clustered in a \emph{type b } solution of $R_j$.
If both $R_i$, $R_j$ are associated with a \emph{type b } solution in $\Pi''$, then
define a set
$\bigcup_{t=4,5,6} (g_t(v_i,v_j)) \cup g_2(v_i,v_j) $ in $\Pi''$.

Now, let us show that $c(\Pi) \geq c(\Pi'')$.
By Lemma~\ref{lem:opt-ty_a} and  by Lemma\ref{lem:cost-ty_b}
it follows that for each row in a set $R_i$
the cost in $\Pi''$ is optimal.
Furthermore, by Lemma~\ref{lem:set-X}, we can assume that $\Pi$ contains
a set $X \supseteq \{ x_1, x_2, x_3 \}$,  hence the rows in $\{ x_1, x_2, x_3 \}$
have all cost $3$ in both $\Pi$ and $\Pi''$.
Hence it remains to consider the cost of the edge set $E_{i,j}$.

Let $E_{i,j}$ be an edge set. Notice that by Lemma~\ref{lem:cost-edge-mand-set},
we can assume that $\Pi$ contains a set $S_{i,j} \supseteq \bigcup_{t=4,5,6}g_t(v_i,v_j)$,
and by construction $\Pi'$ contains a set $S'_{i,j} \supseteq \bigcup_{t=4,5,6}g_t(v_i,v_j)$.
Hence each row of $g_t(v_i,v_j)$, with $t \in \{ 4,5,6 \}$, has a cost
equal to $2$ in both $\Pi$, $\Pi'$.
Let us consider the case when both sets
$R_i$ and $R_j$ are associated with a \emph{type b } solution in both $\Pi$ and $\Pi''$.
The groups of $E_{i,j}$ not co-clustered in a \emph{type b } solution of
$R_i$, $R_j$, are $g_2(v_i,v_j)$, $g_4(v_i,v_j)$,
$g_5(v_i,v_j)$, $g_6(v_i,v_j)$. By construction,
as the rows at Hamming distance $1$ from $g_2(v_i,v_j)$ are clustered in the
\emph{type b } solution of $R_i$, $R_j$ in $\Pi$ (hence cannot be co-clustered with $g_2(v_i,v_j)$),
it follows that
the rows $g_2(v_i,v_j)$ must be clustered with a row having Hamming distance
at least $2$ in $\Pi$.
As $\Pi''$ contains the set $S''_{i,j} = (\bigcup_{t=4,5,6}g_t(v_i,v_j)) \cup g_2(v_i,v_j)$
and as $\Pi$ contains the set $S_{i,j} \supseteq \bigcup_{t=4,5,6}g_t(v_i,v_j)$,
it follows that the cost of the rows in $E_{i,j}$ in solution $\Pi$ is greater or equal than the cost of the rows
in $E_{i,j}$ in solution $\Pi''$.

Let us consider the case when exactly one of the sets
$R_i$ and $R_j$ (w.l.o.g. $R_j$) is  associated with a \emph{type b } solution in $\Pi''$ and in $\Pi$.
By construction, $R_i$ is associated with a
\emph{type a } solution in $\Pi''$. By Lemma~\ref{lem:cost-ty_b} that $c_{\Pi''}(E_{i,j}) = 10$,
and, as each row in $\bigcup_{t=4,5,6} g_t(v_i,v_j)$ has a cost of $2$ in $\Pi''$,
it follows that each row in $E_{i,j} \setminus (\bigcup_{t=4,5,6} g_t(v_i,v_j)) $ has a cost of $1$ in $\Pi''$.
As $\Pi$ contains the set $S_{i,j}$, it follows
that $\Pi$ suppresses two entries in the rows of $\bigcup_{t=4,5,6} g_t(v_i,v_j)$,
hence the cost of the rows in $E_{i,j}$ in solution $\Pi$ is greater or equal than the cost of
the rows in $E_{i,j}$ in solution $\Pi''$.

Let us consider the case when at least one of the sets
$R_i$ and $R_j$ (w.l.o.g. $R_i$) is associated with a \emph{type b } solution in $\Pi''$ and not in $\Pi$.
Notice that by construction, the rows in groups $d_{i,j}(v_i)$, $g^i(v_j,v_j)$
are clustered in both $\Pi$ and $\Pi''$. Now, if $\Pi$ induces a cost of at least $11$
for the rows in $E_{i,j}$, since $\Pi''$ induces a cost of at most $11$
for the rows in $E_{i,j}$ it follows that
$c_{\Pi}(E_{i,j}) \geq c_{\Pi''}(E_{i,j})$.
If $\Pi$ induces a cost of $10$
for the rows in $E_{i,j}$, then $g_2(v_i,v_j)$ must be co-clustered with
$g^j(v_i,v_j)$. Then, it follows that by construction $R_j$ is associated
with a \emph{type a } solution in $\Pi''$ and that the rows of $E_{i,j}$ have a total
cost of $10$ in $\Pi''$. Hence
the cost of the rows in $E_{i,j}$ in solution $\Pi$ is greater or equal than the cost of
the rows in $E_{i,j}$ in solution $\Pi''$.

Now, let us consider the case when both $R_i$, $R_j$, are associated with a \emph{type a }
solution in $\Pi''$. In this case, by construction, the rows in the edge set $E_{i,j}$
have a total cost of $11$ in $\Pi''$, while they have a cost of at least $10$ in $\Pi$,
as the rows in $\bigcup_{t=4,5,6}g_t(v_i,v_j)$ (contained in the set $S_{i,j}$ of $\Pi$)
have a total cost of $6$, while the $4$ rows of $E_{i,j} \setminus \bigcup_{t=4,5,6}g_t(v_i,v_j)$
have a cost of at least $1$ in $\Pi$.
Assume that the rows of $E_{i,j}$ have a total cost of $10$ in $\Pi$.
By Lemma~\ref{lem:APX-edge-set-cost}, $\Pi$ induces a total cost of $11$ for the
rows of one of the sets $R_i$, $R_j$ (w.l.o.g. $R_i$).
Notice that by Lemma~\ref{lem:opt-ty_a} $\Pi''$ induces a cost of $9$ for all the set $R_i$.
Now, let us consider the set $R_i$ and the three edge sets
$E_{i,j}$, $E_{i,h}$, $E_{i,k}$.
For each edge set $E_{i,x}$ in $\{ E_{i,j}, E_{i,h}, E_{i,k} \}$, let us consider
its cost together with the cost of $R_i$ only if
$d_{i,x}(v_i)$ and $g^i(v_i,v_x)$ are clustered in $\Pi$ (otherwise
$E_{i,x}$ will be eventually be considered together with $R_x$).
By construction the cost of at most two edge sets in $E_{i,j}$, $E_{i,h}$, $E_{i,k}$
(assume w.l.o.g. $E_{i,j}$, $E_{i,h}$) are considered together with the cost of $R_i$,
otherwise $R_i$ would be associated with a \emph{type b } solution.
Since
$c_{\Pi}(E_{i,j})\geq 10$, $c_{\Pi}(E_{i,h})\geq 10$, it follows that
$c_{\Pi}(E_{i,j}) + c_{\Pi}(E_{i,h}) + c_{\Pi}(R_i)
\geq c_{\Pi''}(E_{i,j}) + c_{\Pi''}(E_{i,h}) + c_{\Pi''}(R_i)$.

Now, we have shown that $c(\Pi) \geq c(\Pi'')$. Notice that $\Pi''$ may not
be a canonical solution, as there may exist two sets $R_i$, $R_j$,
with $E_{i,j}$ part of the instance, associated with a \emph{type b } solution in $\Pi''$.
Now, applying Lemma~\ref{lem:cost-vert-adj-opt} for each pair of sets $R_i$, $R_j$,
with $E_{i,j}$ part of the instance, associated with a \emph{type b } solution in $\Pi''$,
we can compute a canonical solution
$\Pi'$ such that $c(\Pi'') \geq c(\Pi')$. Hence $c(\Pi) \geq c(\Pi')$.
\end{proof}
\end{comment}
\begin{comment
\begin{Lemma}
\label{lem:apx-hard1}
Let $\Pi$ be a solution of $3$-AP($3$) over instance $R$
of cost of cost $6|V|+3|C|+11|E|$, then
we can compute in polynomial time a be a solution of MVCC over instance $G$ of size $C$.
\end{Lemma}
\begin{proof}
Let us consider a canonical solution of $3$-AP($3$). Since two
sets of rows are associated with a \emph{type b } solution only if there does not
exist a set $E_{i,j}$, it follows that for each edge set $E_{i,j}$
at least one of the set $R_i$ and $R_j$ is associated with a \emph{type a } solution.
But then, the set of rows associated with a \emph{type a } solution corresponds
to a vertex cover of the graph $\mathcal{G}$.

Now consider the cost of a canonical solution. For each set $R_i$ of rows associated
with a \emph{type b } solution, the three edge sets have a cost of $10$ instead of $11$.
Accounting this decreasing of the cost of the edge sets to the set $R_i$ of rows with a \emph{type b } solution, it follows that the cost of a \emph{type b } solution is $6$, while of a \emph{type a } solution is $9$.
\end{proof}

\begin{Lemma}
\label{lem:apx-hard2}
Let $C$ be cover of $G$. Then, we can compute in polynomial time
a solution $\Pi$ of $3$-AP($3$) over instance $R$
of cost $6|V|+3|C|+11|E|$.
\end{Lemma}
\end{comment}

\begin{comment
\begin{proof}
We can define a solution $\Pi$ of $3$-AP($3$) of cost
$6|V|+3|C|+11|E|$, defining a \emph{type a } solution for each $R_i$ associated
with a vertex in $v_i \in C$,
a \emph{type b } solution for each vertex $v_i \in V-C$.
\end{proof}

A consequence of Lemmata~\ref{lem:apx-hard1} and Lemma~\ref{lem:apx-hard2}
\begin{Theorem}
\label{teo:apx-hard}
 $3$-AP($3$) is APX-hard.
\end{Theorem}
\end{comment}

\small

redpajama_set_name: RedPajamaArXiv


9 out of 10 based on 152 ratings. 4,798 user reviews.
wwwalslib››Plasma TV›VIERA TC-P42S30View and Download Panasonic Viera TC-P42S30 owner's manual online. 42"/46"/50" Class 1080p Plasma HDTV. Viera TC-P42S30 Plasma TV pdf manual download. Also for: Viera tc-p50s30, Viera tc-p46s30, Viera tc-p42x3, Viera tc-p46x3, Viera tc-p50x3.
Jul 08, 20187 y.o. panasonic viera plasma TV model tc-p42s30. Turned it on, worked fine for a minute, then snapping sound. Screen now black, no audio. LED power light on, but power light does not respond to remote. When I turn off power manually (on TV, holding power button down), then turned on, Power LED started blinking.
www››TV Boards, Parts & ComponentsGet the best deal for Panasonic Tc P42s30 from the largest online selection at eBay. Browse your favorite brands affordable prices free shipping on many items. Up For Sale Is a 42" Panasonic Plasma TV TC-P42S30 C1 & C2 Buffer Boards TNPA5314 TNPA5315. Mail-in Repair Service For Panasonic TC-P42S30 SC Board 1 YEAR WARRANTY.


text:
Explained | What is Strategic Petroleum Reserve?
NEW YORK:, November 24, 2021 13:09 IST
Updated: November 25, 2021 18:23 IST
America's Strategic Petroleum Reserve holds about 605 million barrels of oil in underground salt caverns in Texas and Louisiana.
Image for representational purpose only. | Photo Credit: Reuters
When President Joe Biden ordered the release of 50 million barrels of oil from America's strategic reserve to help reduce energy costs, he was taking aim at a growing burden for millions of Americans embarking on Thanksgiving travel.
The step announced on Tuesday, done in a rare coordination with several other nations, is among the few things a Presidential administration can do to try to lessen the squeeze – and the political threat – of rising inflation. The likelihood of providing meaningful relief in the near future, however, is probably low. Still, any help in easing fuel prices, even modestly, would be welcomed by many Americans.
What is the petroleum reserve?
America's Strategic Petroleum Reserve holds about 605 million barrels of oil in underground salt caverns in Texas and Louisiana. It was created following the 1970s Arab oil embargo to store oil that could be tapped in an emergency. But the dynamics of the global oil industry changed dramatically in recent years: Now the U.S exports more oil than it imports.
There's a limit to how much can be released at once. In the past, the government has released about one million barrels per day. At that rate, the promised influx of 50 million barrels of crude could last about two months.
Why did Joe Biden tap the reserve?
The idea is that by putting more oil on the market, prices will fall. That hasn't happened yet. But depending on what happens in the rest of the world, there's still a chance it could work.
Oil prices rose slightly after the announcement. Traders were anticipating the news, and may have been underwhelmed by the details, said Claudio Galimberti, senior vice-president for oil markets at Rystad Energy.
"The immediate price reaction is not the final judgment on the effectiveness of this effort," said Jim Burkhard, vice-president at IHS Markit. "It will really be in the months ahead."
Whether the move is effective depends on several factors.
What about OPEC?
The OPEC oil cartel and its allies will be meeting in about a week to decide whether to increase production or to hold back, a strategy the group often employs to boost prices. Earlier this month, Mr. Biden had hoped OPEC nations, led by Saudi Arabia, would agree to significantly boost production. But they only made modest increases.
If OPEC decides next week that it wants higher prices, its members could take oil off the market. "Just overnight, they could just offset it," Mr. Burkhard said. "So that's a big question mark, is how they react to this."
The coalition Mr. Biden assembled – bringing together India, China, Japan, South Korea and the U.K. to tap their strategic oil reserves – is unprecedented, Mr. Galimberti said. Altogether, the group could be adding 70 million to 80 million barrels of oil onto the market, he estimates.
Also read | India to release 5 millon barrels of crude oil from strategic reserves
"It's kind of a coalition of oil importers," he added. "But can they really supplant, or can they really represent a rival to OPEC-plus? The answer is absolutely not." That's because the group of importers are using their strategic petroleum reserves, which are limited. On the other hand, OPEC and its allies have oil reserves that can last for decades. "So there is no comparison between the two," Mr. Galimberti said.
Will gasoline get cheaper?
What many consumers want to know is what's going to happen to gasoline prices at the pump. Many factors go into the price of gasoline. Refineries buy crude oil in advance, so they're still working with more expensive oil, and states have differing tax rates that impact the price. Nevertheless, if OPEC doesn't respond by curtailing production, the influx of oil could lead to a gasoline price decrease of 10 cents to 15 cents per gallon, said Kevin Book, managing director at Clearview Energy Partners. Even if the price drop doesn't happen, Mr. Biden can make the case that he tried.
"Really, what we're talking about are the most price-sensitive consumers in the economy," Mr. Book said. "They may not show up in GDP numbers or recessions, but they show up in vote counts as marginal voters, who may or may not respond in the next election cycle, and I think if we get down to it that's really what this is about."
Why does oil matter?
The future of oil and gas in the U.S. is a political flashpoint and source of tension, especially as companies and government agencies grapple with climate change and the transition to cleaner sources of energy.
On the one hand, the U.S. oil and gas industry has been praised by some political leaders for creating energy independence. Where the U.S. once relied heavily on imports, other nations now rely on the U.S. for oil. It's also a job supplier: The oil and gas industry employs more than 10 million people in the U.S. and contributes about 8% of the nation's gross domestic product, according to the American Petroleum Institute. Any impact resulting from Mr. Biden's release of oil from the strategic reserves "is likely to be short-lived unless it is paired with policy measures that encourage the production of American energy resources," the API said in a statement.
Companies that supply oil benefit from higher prices. But consumers don't like it when those higher prices trickle down to the pump.
Also read | Oil prices drop as coordinated reserve release eases some supply fears
"The broader drama is this new variable in the oil market: It's the tension between aspirations to decarbonise and the practical concern to have low gasoline prices," Mr. Burkhard said. "And there's a conflict between those two forces. And that's why we're going to continue to see dislocations between demand and supply."
Credit Suisse chairman Antonio Horta-Osorio resigns after internal investigation
Two Indians among 3 killed in Abu Dhabi oil tanker blasts
Apple complies with Dutch watchdog ruling on payment options in Netherlands
China's birth rate drops to record low in 2021
Morning digest: India records a 40% spike in COVID-19 infections over a week; Congress, BJP demand postponement of Punjab polls, and more
North Korea fires 2 suspected missiles in 4th launch this year
British police arrest 2 in investigation into Texas standoff
Printable version | Jan 19, 2022 1:11:12 PM | https://www.thehindu.com/news/international/explained-what-is-strategic-petroleum-reserve/article37658251.ece
Trending in International
International What's behind the Houthis' UAE attacks?
International Out of this world: 555.55-carat black diamond lands in Dubai
International Two Indians among 3 killed in Abu Dhabi oil tanker blasts
International Saudi Arabia hits back at Houthi rebels after UAE drone attack
International Watch | Tonga's Underwater Volcano Erupts
International 'Foreign parcels spreading Omicron in China': Chinese media
International Xi Jinping rejects 'Cold War mentality'
International Indonesia passes law to relocate capital to remote Borneo
International Impact of tsunami being assessed in Tonga
International Texas standoff: 'We escaped. We weren't released or freed,' says rabbi
International Imran Khan hails Putin's remark against Islamophobia
International Taiwan pays $900,000 for ally Guatemala to hire Trump-supporter lobbyist in U.S.
International Volcano erupts near Tonga, islanders rush to escape waves
International Spaniard said to be world's oldest man dies at 112
International In a first, U.S. surgeons transplant pig heart into human patient
International Credit Suisse chairman Antonio Horta-Osorio resigns after internal investigation
International Germany vows 'to do all' to guarantee Ukraine's security
International Sri Lanka's looming economic crisis
International Karl Marx in five core ideas
International Libya elections could be rescheduled for June: U.N. official
Watch | The Taliban regime and Afghanistan's humanitarian crisis
A video explainer on how bad the humanitarian situation is in Afghanistan and whether the war is over.
The Hindu Net Desk
Watch | All about the new Omicron coronavirus variant
A video on the new coronavirus variant called Omicron or B.1.1.529
6mins Dip in eastern swamp deer population in Kaziranga
13mins Pfizer chief Albert Bourla wins $1 million Genesis Prize
14mins Seven-year-old buried alive under snow in Jammu and Kashmir's Kishtwar
1hr TMC steps up attack on Meghalaya govt. over illegal coal trade
2hrs Black Caps' Australia tour postponed over New Zealand's hard quarantine norms

redpajama_set_name: RedPajamaCommonCrawl


According to a new study conducted by Harvard, drinking one to two cans of sugary drink per day can increase the risk of dying from heart disease by up to 31%.
As the researchers pointed out, drinks such as sugar-sweetened soda, juice, and energy drinks not only drastically increase the risk of dying from heart disease but also increase one's chances of premature death by other causes, such as cancer, by 21%.
While switching sugary drinks for diet, sugar-free alternatives, results in lower risk of premature death according to the study, the risk also increases depending on the amount consumed and can reach alarming rates if a person drinks over four cans per day.
The research was led by Vasanti Malik, a department of nutrition scientist of the Harvard T.H. Chan School of Public Health.
Before the researchers could come to this conclusion, they analyzed over 37,000 men from the Health Professionals Follow-up Study (1986 to 2014) and more than 80,000 women from the Nurses' Health Study (1980 to 2014).
Every two years, the participants of these studies were asked about their lifestyle habits and the state of their health.
According to the results of the study, the participants who drank more than a can of sugary drinks per day were up to 31% more likely to die due to heart disease than those who only drank SSBs once per month or less. Furthermore, every additional can of SSB adds 10% to the risk of experiencing heart disease.
"These findings are consistent with the known adverse effects of high sugar intake on metabolic risk factors," Dr. Walter Willett of Harvard added.
"And the strong evidence that drinking sugar-sweetened beverages increases the risk of type 2 diabetes, itself a major risk factor for premature death.
What are your thoughts on this study? Let us know in the comments and don't forget to SHARE this post with your friends and family to raise awareness of the dangers of SSBs!


Here you can download Arcade and Action games. Playing Arcade games you should act fast relying upon your reflexes and reaction. On our site you can find various Arcade and Action games such as arcanoid games, platform games, shooters and many others.
Bad Girl - Join in a prehistoric adventure!
Macabre Ring - Investigate a mysterious murder at the abandoned prison!
Trito's Adventure - Save an underwater kingdom in this match 3 adventure!
Katy and Bob: Cake Cafe - Katy and Bob are back, let's open a wedding bakery!
Magica Travel Agency: Las Vegas - Unique match 3 challenges in New Las Vegas!
Heart of Moon: The Mask of Seasons - Find the Mask of Seasons in an innovative match 3 adventure.
Rune Lord - Only you can close the gateway and defeat the Ice Golem!
Monster Toons - Match cute monsters in rows!
Brain Puzzle - Put your logic to the test!
My Pretty Kitty - A wonderful blend of match 3 and Tamagochi!


Paperback, 9.75 x 12 in. / 304 pgs / 22 color.
Edited by Theodora Vischer, Fondation Beyeler. Text by Gottfried Boehm, Ralph Ubl, Theodora Vischer.
On the occasion of the Beyeler Fondation's 20th anniversary, this richly illustrated publication gathers quotes, letters, interviews and writings from Arp, Bourgeois, Cézanne, Degas, Dubuffet, Kandinsky, Klee, Malevich, Matisse, Mondrian, Monet, Picasso, Rousseau, Tillmans, Van Gogh, Wolfson and others.
FORMAT: Pbk, 9.75 x 12 in. / 304 pgs / 22 color.