|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Max Lin Above Average Problem and Lower Bounds for Maxima of Pseudo-boolean Functions | | R. Crowston
; G. Gutin
; M. Jones
; E.J. Kim
; I.Z. Ruzsa
; | | Date: |
1 Feb 2010 | | Abstract: | In the problem Max Lin, we are given a system $Az=b$ of $m$ linear equations
with $n$ variables over $mathbb{F}_2$ in which each equation is assigned a
positive weight and we wish to find an assignment of values to the variables in
order to maximize the total weight of satisfied equations. Max Lin Above
Average (MLAA) is a parameterized version of Max Lin introduced by Mahajan et
al. (Proc. IWPEC’06 and J. Comput. Syst. Sci. 75, 2009). In MLAA all weights
are integral and we wish to decide whether there is an assignment of values to
the variables such that the total weight of satisfied equations minus the total
weight of falsified equations is at least $k$, where $k$ is the parameter.
Mahajan et al. raised the question of determining the parameterized complexity
of MLAA.
It is not hard to see that we may assume that no two equations in $Az=b$ have
the same left-hand side and $n={
m rank A}$. We prove that, under these
assumptions, MLAA is fixed-parameter tractable for a wide special case: $mle
2^{p(n)}$ for an arbitrary fixed function $p(n)=o(n)$. Our result generalizes
earlier results by Crowston et al. (arXiv:0911.5384) and Gutin et al. (Proc.
IWPEC’09). We also prove that MLAA is polynomial-time solvable for every fixed
$k$ and, moreover, MLAA is in the parameterized complexity class W[P].
We show that maximization of arbitrary pseudo-boolean functions, i.e.,
functions $f: {-1,+1}^n o mathbb{R}$, represented by their Fourier
expansions is equivalent to solving Max Lin. Using a combination of results
proved (in this paper or recently) for MLAA, probabilistic method, and results
from Fourier analysis, we obtain four lower bounds on the maxima of
pseudo-boolean functions. | | Source: | arXiv, 1002.0286 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER