Note on Max Lin-2 above average

DOI10.1016/J.IPL.2010.04.010zbMATH Open1229.68044arXiv0911.5384OpenAlexW2161307522MaRDI QIDQ656604FDOQ656604

Juan-Miguel Gracia

Publication date: 18 January 2012

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

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).

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

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

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)

Cites Work

• Parameterizing above or below guaranteed values
• Parametrized complexity theory.
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Title not available (Why is that?)
• Title not available (Why is that?)
• The linear arrangement problem parameterized above guaranteed value
• Interval Completion Is Fixed Parameter Tractable
• A probabilistic approach to problems parameterized above or below tight bounds
• Title not available (Why is that?)
• Fixed-parameter complexity of minimum profile problems
• On the advantage over a random assignment

Cited In (9)

• 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 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
• Betweenness parameterized above tight lower bound
• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application
• On the complexity of and solutions to the minimum stopping and trapping set problems

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)