4 papers
Filling Crosswords is Very Hard
Laurent Gourvès, Ararat Harutyunyan, Michael Lampis +1
We revisit a classical crossword filling puzzle which already appeared in Garey\&Jonhson's book. We are given a grid with vertical and horizontal slots and a dictionary with $m…
(In)approximability of Maximum Minimal FVS
Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei +2
We study the approximability of the NP-complete \textsc{Maximum Minimal Feedback Vertex Set} problem. Informally, this natural problem seems to lie in an intermediate space between…
Approximation Schemes for Subset Sum Ratio Problems
Nikolaos Melissinos, Aris Pagourtzis, Theofilos Triommatis
We consider the Subset Sum Ratio Problem (), in which given a set of integers the goal is to find two subsets such that the ratio of their sums is as close to~1 as possible, a…
A Faster FPTAS for the Subset-Sums Ratio Problem
Nikolaos Melissinos, Aris Pagourtzis
The Subset-Sums Ratio problem (SSR) is an optimization problem in which, given a set of integers, the goal is to find two subsets such that the ratio of their sums is as close to 1…