Show simple item record

dc.contributor.authorCrowston, Robert*
dc.contributor.authorFellows, Michael*
dc.contributor.authorGutin, Gregory*
dc.contributor.authorJones, Mark*
dc.contributor.authorKim, Eun Jung*
dc.contributor.authorRosamond, Frances*
dc.contributor.authorRusza, Imre Z.*
dc.contributor.authorThomassé, Stéphan*
dc.contributor.authorYeo, Anders*
dc.date.accessioned2016-07-21T14:50:33Z
dc.date.available2016-07-21T14:50:33Z
dc.date.issued2014
dc.identifier.issn0022-0000
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/15690
dc.language.isoenen
dc.subjectMaxLinen
dc.subjectKernelen
dc.subjectFixed-parameter tractableen
dc.subject.ddc515en
dc.titleSatisfying more than half of a system of linear equations over GF(2): A multivariate approachen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn 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.en
dc.relation.isversionofjnlnameJournal of Computer and System Sciences
dc.relation.isversionofjnlvol80en
dc.relation.isversionofjnlissue4en
dc.relation.isversionofjnldate2014
dc.relation.isversionofjnlpages687-696en
dc.relation.isversionofdoi10.1016/j.jcss.2013.10.002en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelAnalyseen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2016-05-30T12:33:38Z
hal.person.labIds228022*
hal.person.labIds267244*
hal.person.labIds33171*
hal.person.labIds33171*
hal.person.labIds989*
hal.person.labIds267244*
hal.person.labIds187934*
hal.person.labIds35418*
hal.person.labIds254148*
hal.identifierhal-01347776*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record