Escaping a dominance region at minimum cost

Youngdae Kim, Gae Won You, Seung Won Hwang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)


Skyline queries have gained attention as an effective way to identify desirable objects that are "not dominated" by another object in the dataset. From market perspective, such objects can be viewed as marketable, as each of such objects has at least one competitive edge against all the other objects, or not dominated. In other words, non-skyline objects are not marketable, as there always exists another product excelling in all the attributes. The goal of this paper is, for such non-skyline objects, to identify the cost-minimal enhancement to become a skyline point to gain marketability. More specifically, we abstract this problem as a mixed integer programming problem and develop a novel algorithm for efficiently identifying the optimal solution. Through extensive experiments using synthetic datasets, we show that our proposed framework is both efficient and scalable over extensive experiment settings.

Original languageEnglish
Title of host publicationDatabase and Expert Systems Applications - 19th International Conference, DEXA 2008, Proceedings
Number of pages8
Publication statusPublished - 2008
Event19th International Conference on Database and Expert Systems Applications, DEXA 2008 - Turin, Italy
Duration: 2008 Sept 12008 Sept 5

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5181 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other19th International Conference on Database and Expert Systems Applications, DEXA 2008

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Escaping a dominance region at minimum cost'. Together they form a unique fingerprint.

Cite this