The Minimum Feasible Tileset Problem

被引：0

作者：

Disser, Yann ^{[1
]}

Kratsch, Stefan ^{[2
]}

Sorge, Manuel ^{[3
,4
]}

机构：

[1] Tech Univ Darmstadt, Grad Sch CE, Inst Math, Darmstadt, Germany

[2] Humboldt Univ, Inst Informat, Berlin, Germany

[3] TU Berlin, Inst Softwaretech & Theoret Informat, Berlin, Germany

[4] Ben Gurion Univ Negev, Dept Ind Engn & Management, Beer Sheva, Israel

来源：

ALGORITHMICA | 2019年 / 81卷 / 03期

基金：

以色列科学基金会;

关键词：

Set packing; Approximation algorithm; APX hardness; Parameterized complexity; Minimum feasible tileset; APPROXIMATION;

D O I：

10.1007/s00453-018-0460-3

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We introduce and study the Minimum Feasible Tileset problem: given a set of symbols and subsets of these symbols (scenarios), find a smallest possible number of pairs of symbols (tiles) such that each scenario can be formed by selecting at most one symbol from each tile. We show that this problem is APX-hard and that it is NP-hard even if each scenario contains at most three symbols. Our main result is a 4/3-approximation algorithm for the general case. In addition, we show that the Minimum Feasible Tileset problem is fixed-parameter tractable both when parameterized with the number of scenarios and with the number of symbols.

引用

页码：1126 / 1151

页数：26

共 31 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2]

[Anonymous], 2013, LEC NOT ELECT ENG

[3] A NEW APPROXIMATION METHOD FOR SET COVERING PROBLEMS, WITH APPLICATIONS TO MULTIDIMENSIONAL BIN PACKING [J].

Bansal, Nikhil ;

Caprara, Alberto ;

Sviridenko, Maxim .

SIAM JOURNAL ON COMPUTING, 2009, 39 (04) :1256-1278

[4] Balanced vertex-orderings of graphs [J].

Biedl, T ;

Chan, T ;

Ganjali, Y ;

Hajiaghayi, MT ;

Wood, DR .

DISCRETE APPLIED MATHEMATICS, 2005, 148 (01) :27-48

[5]

Buchin Kevin, 2011, Journal of Graph Algorithms and Applications, V15, P533, DOI 10.7155/jgaa.00237

[6] POLYNOMIAL-TIME DATA REDUCTION FOR THE SUBSET INTERCONNECTION DESIGN PROBLEM [J].

Chen, Jiehua ;

Komusiewicz, Christian ;

Niedermeier, Rolf ;

Sorge, Manuel ;

Suchy, Ondrej ;

Weller, Mathias .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2015, 29 (01) :1-25

[7]

Crescenzi P, P 12 ANN IEEE C COMP

[8] Improved approximation for 3-dimensional matching via bounded pathwidth local search [J].

Cygan, Marek .

2013 IEEE 54TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2013, :509-518

[9] Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses [J].

Dell, Holger ;

Van Melkebeek, Dieter .

JOURNAL OF THE ACM, 2014, 61 (04)

[10]

Dell Holger, 2012, P 23 ANN ACM SIAM S, P68, DOI [DOI 10.1137/1.9781611973099.6.2, 10.1137/1.9781611973099.6.2]

← 1 2 3 4 →