The Library
On the tradeoff between stability and fit
Tools
Cohen, Edith, Cormode, Graham, Duffield, Nick and Lund, Carsten (2016) On the tradeoff between stability and fit. ACM Transactions on Algorithms , 13 (1). 7. doi:10.1145/2963103 ISSN 1549-6325.
|
PDF
WRAP-on-tradeoff-stability-fit-Cormode-2014.pdf - Accepted Version - Requires a PDF viewer. Download (795Kb) | Preview |
Official URL: http://dx.doi.org/10.1145/2963103
Abstract
In computing, as in many aspects of life, changes incur cost. Many optimization problems are formulated as a one-time instance starting from scratch. However, a common case that arises is when we already have a set of prior assignments and must decide how to respond to a new set of constraints, given that each change from the current assignment comes at a price. That is, we would like to maximize the fitness or efficiency of our system, but we need to balance it with the changeout cost from the previous state.
We provide a precise formulation for this tradeoff and analyze the resulting stable extensions of some fundamental problems in measurement and analytics. Our main technical contribution is a stable extension of Probability Proportional to Size (PPS) weighted random sampling, with applications to monitoring and anomaly detection problems. We also provide a general framework that applies to top-k, minimum spanning tree, and assignment. In both cases, we are able to provide exact solutions and discuss efficient incremental algorithms that can find new solutions as the input changes.
Item Type: | Journal Article | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
|||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
Library of Congress Subject Headings (LCSH): | Mathematical optimization , Mathematical optimization -- Computer programs | |||||||||
Journal or Publication Title: | ACM Transactions on Algorithms | |||||||||
Publisher: | Association for Computing Machinery, Inc. | |||||||||
ISSN: | 1549-6325 | |||||||||
Official Date: | 2016 | |||||||||
Dates: |
|
|||||||||
Volume: | 13 | |||||||||
Number: | 1 | |||||||||
Number of Pages: | 24 | |||||||||
Article Number: | 7 | |||||||||
DOI: | 10.1145/2963103 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Reuse Statement (publisher, data, author rights): | © Author | ACM 2016. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Transactions on Algorithms, http://dx.doi.org/10.1145/2963103 | |||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||
Date of first compliant deposit: | 12 February 2020 | |||||||||
Date of first compliant Open Access: | 25 February 2020 | |||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year