This article is cited in 11 papers

On complexity of bilevel problems of location and pricing

A. A. Panin^ab, A. V. Plyasunov<sup>ab

a</sup> S. L. Sobolev Institute of Mathematics, SB RAS, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
^b Novosibirsk State University, 2 Pirogov St., 630090 Novosibirsk, Russia

Abstract: We study complexity of bilevel problems with different pricing strategies: uniform, mill and discriminatory. It is shown that these problems are NP-hard in the strong sense, belong to Poly-APX class and are complete in its relative AP-reducibility. Bibliogr. 17.

Keywords: bilevel problem, location, pricing, computational and approximation complexity, NP-hard in the strong sense, AP-reducibility, Poly-APX-completeness.

UDC: 519.87+519.854

Received: 15.10.2013
Revised: 29.01.2014

 English version: Journal of Applied and Industrial Mathematics, 2014, 8:4, 574–581

Bibliographic databases:

•