3
$\begingroup$

I'm trying to solve the following optimization problem.

A is a rectangular matrix with coefficients in the finite field Z/2Z (size less than 1000 X 1000). I have a system of the form A.X = Y (X and Y are vectors). And I'm looking for X such that the Hamming weight of Y is maximal.

In the best case, there would be a solution with Y_i = 1 for all i, and I would find it using the Gauss algorithm. But I know it's not the case.

So far, I haven't found a better algorithm than a random/greedy local search, but I'm sure I can use some maths to get a better solution. I've considered running a Gauss algorithm starting with B = (1,...,1) and somehow backtrack when a run into a contradiction (and switch the b_i that prevent me to get a solution). Could matrix factorization help somehow?

$\endgroup$
  • $\begingroup$ Your problem is likely NP-hard, probably also NP-hard to approximate. But perhaps there are subexponential algorithms that give reasonable results for your dimensions. $\endgroup$ – Yuval Filmus Jan 31 '16 at 22:33
  • $\begingroup$ I don't need to solve it exactly, but I'm sure I can do better than my current solution. $\endgroup$ – Nemo Jan 31 '16 at 22:54
  • $\begingroup$ You might want to look into the block Lancosz algorithm for finding solutions. $\endgroup$ – Pseudonym Feb 1 '16 at 1:04
  • $\begingroup$ Block lancosz algorithm - does that give poly time bounds even in case of sparse number of entries? $\endgroup$ – user3483902 Mar 21 '18 at 19:42
4
$\begingroup$

(Note that a random assignment has probability at least 1/(1+$\hspace{.03 in}$(size($\hspace{.03 in}$Y$\hspace{.03 in}$)))
of making at least 1/2 of Y's entries equal 1. ​ That can be derandomized
by sequentially setting each variable to [something that forces at least
as many of Y's entries to 1 as it forces to 0, with ties broken arbitrarily].)


By this paper's proof of Theorem 5.6, for all real
numbers $\epsilon$, if ​ $0 < \epsilon$ ​ then the promise problem

Input: ​ instance of your problem in which each row of A has exactly 4 ones
must output YES if: ​ ​ ​ there is an assignment which makes more than 1-$\hspace{.03 in}\epsilon$ of Y's entries equal 1
must output NO if: ​ ​ ​ ​ for every assignment, less than ​ (1/2)$\hspace{.03 in}$+$\hspace{.03 in}\epsilon$ ​ of Y's entries equal 1

is NP-hard.


When parameterized by the number of zeros in Y, your problem is obviously in W$[\hspace{-0.02 in}$P$]$O,
but I don't know anything else about your problem's parameterized complexity.

This paper gives a possible try for your problem,
although it looks like it's just a student's "3rd Year Project Report".

$\endgroup$
2
$\begingroup$

This is known as "the maximum-weight codeword problem": it is the problem of finding the maximum-weight codeword of a linear code. It is closely related to the minimum-weight codeword problem. For instance, if you add a row containing all ones, then there's a correspondence between the maximum-weight codeword and the minimum-weight codeword.

The minimum-weight codeword problem (for a general linear code) is known to be NP-hard. However, there are non-trivial algorithms for it: I believe there are algorithms with subexponential running time. (The problem has been studied extensively in the cryptographic literature.) You might look at those algorithms; perhaps they can be adapted to solve the maximum-weight codeword problem, too.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.