The complexity of approximately counting stable roommate assignments

We investigate the complexity of approximately counting stable roommate assignments in two models: (i) the k-attribute model, in which the preference lists are determined by dot products of “preference vectors” with “attribute vectors” and (ii) the k-Euclidean model, in which the preference lists are determined by the closeness of the “positions” of the people to their “preferred positions”. Exactly counting the number of assignments is #P-complete, since Irving and Leather demonstrated #P-completeness for the special case of the stable marriage problem (Irving and Leather, 1986 [11]). We show that counting the number of stable roommate assignments in the k-attribute model (#k-attribute SR, $k?4$) and the 3-Euclidean model (#k-Euclidean SR, $k?3$) is interreducible, in an approximation-preserving sense, with counting independent sets (of all sizes) ($\mathrm{\#}\mathit{IS}$) in a graph, or counting the number of satisfying assignments of a Boolean formula ($\mathrm{\#}\mathit{SAT}$). This means that there can be no FPRAS for any of these problems unless NP = RP. As a consequence, we infer that there is no FPRAS for counting stable roommate assignments ($\mathrm{\#}\mathit{SR}$) unless NP = RP. Utilizing previous results by Chebolu, Goldberg and Martin (2010) [3], we give an approximation-preserving reduction from counting the number of independent sets in a bipartite graph ($\mathrm{\#}\mathit{BIS}$) to counting the number of stable roommate assignments both in the 3-attribute model and in the 2-Euclidean model. $\mathrm{\#}\mathit{BIS}$ is complete with respect to approximation-preserving reductions in the logically-defined complexity class $\mathrm{\#}\mathrm{RH}{\mathrm{\Pi }}_1$. Hence, our result shows that an FPRAS for counting stable roommate assignments in the 3-attribute model would give an FPRAS for all $\mathrm{\#}\mathrm{RH}{\mathrm{\Pi }}_1$. We also show that the 1-attribute stable roommate problem always has either one or two stable roommate assignments, so the number of assignments can be determined exactly in polynomial time.     

Subtractive reductions and complete problems for counting complexity classes

We introduce and investigate a new type of reductions between counting problems, which we call subtractive reductions. We show that the main counting complexity classes #P, #NP, as well as all higher counting complexity classes $\#·{\Pi }_k\mathrm{P},k⩾2$, are closed under subtractive reductions. We then pursue problems that are complete for these classes via subtractive reductions. We focus on the class #NP (which is the same as the class $\#·\mathrm{coNP}$) and show that it contains natural complete problems via subtractive reductions, such as the problem of counting the minimal models of a Boolean formula in conjunctive normal form and the problem of counting the cardinality of the set of minimal solutions of a homogeneous system of linear Diophantine inequalities.     

Continuous distance-based skyline queries in road networks

In recent years, the research community has introduced various methods for processing skyline queries in road networks. A skyline query retrieves the skyline points that are not dominated by others in terms of static and dynamic attributes (i.e., the road distance). This paper addresses the issue of efficiently processing continuous skyline queries in road networks. Two novel and important distance-based skyline queries are presented, namely, the continuous  _dε-skyline$d_{\epsilon }\mathrm{-}\mathit{skyline}$query   (_Cdε-SQ${\mathit{Cd}}_{\epsilon }\mathrm{-}\mathit{SQ}$) and the continuous k nearest neighbor-skyline query (Cknn-SQ  ). A grid index is first designed to effectively manage the information of data objects and then two algorithms are proposed, the _Cdε-SQ${\mathit{Cd}}_{\epsilon }\mathrm{-}\mathit{SQ}$algorithm   and the _Cdε-SQ⁺${\mathit{Cd}}_{\epsilon }\mathrm{-}{\mathit{SQ}}^{+}$algorithm  , which are combined with the grid index to answer the _Cdε-SQ${\mathit{Cd}}_{\epsilon }\mathrm{-}\mathit{SQ}$. Similarly, the Cknn-SQ algorithm and the Cknn-SQ⁺algorithm are developed to efficiently process the Cknn-SQ. Extensive experiments using real road network datasets demonstrate the effectiveness and the efficiency of the proposed algorithms.     

The heuristic concentration-integer and its application to a class of location problems

We propose a new metaheuristic called heuristic concentration-integer (HCI). This metaheuristic is a modified version of the heuristic concentration (HC), oriented to find good solutions for a class of integer programming problems, composed by problems in which p   elements must be selected from a larger set, and each element can be selected more than once. These problems are common in location analysis. The heuristic is explained and general instructions for rewriting integer programming formulations are provided, that make the application of HCI to these problems easier. As an example, the heuristic is applied to the maximal availability location problem (MALP), and the solutions are compared to those obtained using linear programming with branch and bound (LP+B&B)$(\mathrm{LP}+\mathrm{B}\&\mathrm{B})$. For one-third of the instances of MALP, LP+B&B$\mathrm{LP}+\mathrm{B}\&\mathrm{B}$ can be allowed to run until the computer is out of memory without termination, while HCI can find good solutions to the same instances in a reasonable time. In one such case, LP-IP was allowed to run for nearly 100 times longer than HCI and HCI still found a better solution. Furthermore, HCI found the optimal solution in 33.3% of cases and had an objective value gap of less than 1% in 76% of cases. In 18% of the cases, HCI found a solution that is better than LP+B&B. Therefore, in cases where LP+B&B$\mathrm{LP}+\mathrm{B}\&\mathrm{B}$ is unreasonable due to time or memory constraints, HCI is a valuable tool.