DSpace About DSpace Software

SEIKEI University Repository >
01:紀要(Bulletin) >
09:理工学研究報告 >
第51巻第2号 >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10928/606

Title: 最大充足可能性問題の疎な例題に対する厳密アルゴリズム
Other Titles: Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction
Authors: 脊戸, 和寿
SETO, Kazuhisa
Keywords: exponential time algorithm
polynomial space
Issue Date: 1-Dec-2014
Publisher: 成蹊大学理工学部
Abstract: We present a moderately exponential time polynomial space algorithm for sparse instances of Max SAT. For instances with n variables and cn clauses, our algorithm runs in time O(2^<(1-μ(c))n)>, where μ(c) = O(1/c^2log^2 c). Previously, an exponential space algorithm with μ(c) = O(1/clog c) was shown by Dantsin and Wolpert [SAT 2006] and a polynomial space algorithm with μ(c) = O(1/2^<O(c)>) was shown by Kulikov and Kutzkov [CSR 2007]. Our algorithm is based on the combination of two techniques, width reduction of Schuler and greedy restriction of Santhanam.
URI: http://hdl.handle.net/10928/606
Appears in Collections:第51巻第2号

Files in This Item:

File Description SizeFormat
rikougaku-51-2_19-21.pdf704.25 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback