Note on Max Lin-2 above average

DOI10.1016/J.IPL.2010.04.010MaRDI QIDQ656604zbMATH OpenOpenAlexFDO

Authors Juan-Miguel Gracia

Publication date 18 January 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0911.5384

zbMATH Keywords

fixed-parameter tractabilityMax LinMax Sat

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: In the Max Lin-2 problem we are given a system $S$ of $m$ linear equations in $n$ variables over $mathbb{F}_2$ in which Equation $j$ is assigned a positive integral weight $w_j$ for each $j$. We wish to find an assignment of values to the variables which maximizes the total weight of satisfied equations. This problem generalizes Max Cut. The expected weight of satisfied equations is $W/2$, where $W=w_1+\mathrm{...}+w_m$; $W/2$ is a tight lower bound on the optimal solution of Max Lin-2. Mahajan et al. (J. Comput. Syst. Sci. 75, 2009) stated the following parameterized version of Max Lin-2: decide whether there is an assignment of values to the variables that satisfies equations of total weight at least $W/2+k$, where $k$ is the parameter. They asked whether this parameterized problem is fixed-parameter tractable, i.e., can be solved in time $f(k)(nm{)}^{O(1)}$, where $f(k)$ is an arbitrary computable function in $k$ only. Their question remains open, but using some probabilistic inequalities and, in one case, a Fourier analysis inequality, Gutin et al. (IWPEC 2009) proved that the problem is fixed-parameter tractable in three special cases. In this paper we significantly extend two of the three special cases using only tools from combinatorics. We show that one of our results can be used to obtain a combinatorial proof that another problem from Mahajan et al. (J. Comput. Syst. Sci. 75, 2009), Max $r$-SAT above the Average, is fixed-parameter tractable for each $rge2.$ Note that Max $r$-SAT above the Average has been already shown to be fixed-parameter tractable by Alon et al. (SODA 2010), but the paper used the approach of Gutin et al. (IWPEC 2009).

Recommendations

• Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
• Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
• Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• Parameterized constraint satisfaction problems: a survey

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 6297727 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A probabilistic approach to problems parameterized above or below tight bounds
• Fixed-parameter complexity of minimum profile problems
• Interval Completion Is Fixed Parameter Tractable
• On the advantage over a random assignment
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Parameterizing above or below guaranteed values
• Parametrized complexity theory.
• The linear arrangement problem parameterized above guaranteed value

Cited in

(12)

• A new bound for 3-satisfiable MaxSat and its algorithmic application
• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• A new bound for 3-satisfiable MaxSat and its algorithmic application
• A probabilistic approach to problems parameterized above or below tight bounds
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• Note on maximal bisection above tight lower bound
• Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
• Betweenness parameterized above tight lower bound
• Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• On the complexity of and solutions to the minimum stopping and trapping set problems
• Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)

This page was built for publication: Note on Max Lin-2 above average

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q656604)