HYPERBOLIC 0-1 PROGRAMMING AND QUERY OPTIMIZATION IN INFORMATION-RETRIEVAL

被引：35

作者：

HANSEN, P

DEARAGAO, MVP

RIBEIRO, CC

机构：

[1] GERAD,MONTREAL H3C 3A7,QUEBEC,CANADA

[2] ECOLE POLYTECH,MONTREAL H3C 3A7,QUEBEC,CANADA

[3] PONTIFICIA UNIV CATOLICA RIO DE JANEIRO,BR-22452 RIO DE JANEIRO,BRAZIL

来源：

MATHEMATICAL PROGRAMMING | 1991年 / 52卷 / 02期

关键词：

HYPERBOLIC PROGRAMMING; 0-1; VARIABLES; INFORMATION RETRIEVAL; QUERY OPTIMIZATION;

D O I：

10.1007/BF01582890

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Unconstrained hyperbolic 0-1 programming can be solved in linear time when the numerator and the denominator are linear and the latter is always positive. It is NP-hard, and finding an approximate solution with a value equal to a positive multiple of the optimal one is also NP-hard, if this last hypothesis does not hold. Determining the optimal logical form of a query in information retrieval, given the attributes to be used, can be expressed as a parametric hyperbolic 0-1 program and solved in O(n log n) time, where n is the number of elementary logical conjunctions of the attributes. This allows to characterize the optimal queries for the Van Rijsbergen synthetic criterion.

引用

页码：255 / 263

页数：9