• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Satisfying more than half of a system of linear equations over GF(2): A multivariate approach

Thumbnail
View/Open
mlinJ5b.pdf (361.4Kb)
Date
2014
Dewey
Analyse
Sujet
MaxLin; Kernel; Fixed-parameter tractable
Journal issue
Journal of Computer and System Sciences
Volume
80
Number
4
Publication date
2014
Article pages
687-696
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.jcss.2013.10.002
URI
https://basepub.dauphine.fr/handle/123456789/15690
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Crowston, Robert
228022 Department of Computer Science [Royal Holloway]
Fellows, Michael R.
267244 Autre
Gutin, Gregory
33171 Department of Computer Science
Jones, Mark
33171 Department of Computer Science
Kim, Eun Jung
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Rosamond, Frances
267244 Autre
Rusza, Imre Z.
187934 Alfréd Rényi Institute of Mathematics
Thomassé, Stéphan
35418 Laboratoire de l'Informatique du Parallélisme [LIP]
Yeo, Anders
status unknown
Type
Article accepté pour publication ou publié
Abstract (EN)
In the parameterized problem MaxLin2-AA[k ], we are given a system with variables x1,…,xnx1,…,xn consisting of equations of the form ∏i∈Ixi=b∏i∈Ixi=b, where xi,b∈{−1,1}xi,b∈{−1,1} and I⊆[n]I⊆[n], each equation has a positive integral weight, and we are to decide whether it is possible to simultaneously satisfy equations of total weight at least W/2+kW/2+k, where W is the total weight of all equations and k is the parameter (it is always possible for k=0k=0). We show that MaxLin2-AA[k ] has a kernel with at most View the MathML sourceO(k2logk) variables and can be solved in time 2O(klogk)(nm)O(1)2O(klogk)(nm)O(1). This solves an open problem of Mahajan et al. (2006). The problem Max-r-Lin2-AA[k,rk,r] is the same as MaxLin2-AA[k] with two differences: each equation has at most r variables and r is the second parameter. We prove that Max-r-Lin2-AA[k,rk,r] has a kernel with at most (2k−1)r(2k−1)r variables.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.