More Web Proxy on the site http://driver.im/

research-article

Choosing Subsets with Maximum Weighted Average

Authors:

David Eppstein,

Daniel S. HirschbergAuthors Info & Claims

Journal of Algorithms, Volume 24, Issue 1

Pages 177 - 193

https://doi.org/10.1006/jagm.1996.0849

Published: 01 July 1997 Publication History

Abstract

Given a set ofnreal values, each with a positive weight, we wish to find the subset ofn kvalues having maximum weighted average. This is equivalent to the following form of parametric selection: givennobjects with values decreasing linearly with time, find the time at which then kmaximum values add to zero. We show that these problems can be solved in timeO(n) (independent ofk). A generalization in which weights are allowed to be negative is NP-complete.

References

[1]

N. Amenta, Helly theorems and generalized linear programming, Discrete Comput . Geom . 12 (1994), 241-261.

[2]

M. Bern, D. Eppstein, L. Guibas, J. Hershberger, S. Suri, and J. Wolter, The centroid of points with approximate weights, in "3rd Eur. Symposium on Algorithms," Lecture Notes in Computer Science, Vol. 979, pp. 460-472, 1995.

[3]

H. Brönnimann and B. Chazelle, Optimal slope selection via cuttings, in "6th Canadian Conference on Computational Geometry," pp. 99-103, 1994.

[4]

B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, Diameter, width, closest line pair, and parametric searching, in "8th ACM Symposium on Computational Geometry," pp. 120-129, 1992.

[5]

K. L. Clarkson, A Las Vegas algorithm for linear programming when the dimension is small, in "29th IEEE Symposium in Foundations of Computer Science," pp. 452-456, 1988.

[6]

R. Cole, J. S. Salowe, W. L. Steiger, and E. Szemerédi, An optimal-time algorithm for slope selection, SIAM J . Comput . 18 (1989), 792-810.

[7]

M. B. Dillencourt, D. M. Mount, and N. S. Netanyahu, A randomized algorithm for slope selection. Int . J . Comput . Geom . Appl . 2 (1992), 1-27.

[8]

D. Eppstein and D. S. Hirschberg, "Choosing Subsets with Maximum Weighted Average, Technical Report 95-12, Department of Information and Computer Science, University of California, Irvine, 1995.

[9]

T. R. Ervolina and S. T. McCormick, Two strongly polynomial cut cancelling algorithms for minimum cost network flow, Discrete Appl . Math . 46 (1993), 133-165.

[10]

B. Gärtner, A subexponential algorithm for abstract optimization problems, in "33rd IEEE Symposium on Foundations of Computer Science," pp. 464-472, 1992.

[11]

A. V. Goldberg and R. E. Tarjan, Finding minimum-cost circulations by cancelling negative cycles, J . Assoc . Comput . Mach . 36 (1989), 873-886.

[12]

M. Hartmann and J. B. Orlin, Finding minimum cost to time ratio cycles with small integral transit times, Networks 23 (1993), 567-574.

[13]

K. Iwano, S. Misono, S. Tezuka, and S. Fujishige, A new scaling algorithm for the maximum mean cut problem, Algorithmica 11 (1994), 243-255.

Digital Library

[14]

R. M. Karp, A characterization of the minimum cycle mean in a digraph, Discrete Math . 23 (1978), 309-311.

[15]

R. M. Karp, Probabilistic recurrence relations, J . Assoc . Comput . Mach . 41 (1994), 1136-1150.

[16]

R. M. Karp and J. B. Orlin, Parametric shortest path algorithms with an application to cyclic staffing, Discrete Appl . Math . 3 (1981), 37-45.

[17]

M. J. Katz and M. Sharir, Optimal slope selection via expanders, Inform . Process . Lett . 47 (1993), 115-122.

[18]

J. Matou¿ek, Randomized optimal algorithm for slope selection, Inform . Process . Lett . 39 (1991), 183-187.

[19]

J. Matou¿ek, Approximations and optimal geometric divide-and-conquer, J . Comput . System Sci . 50 (1995), 203-208.

[20]

J. Matou¿ek, M. Sharir, and E. Welzl, A subexponential bound for linear programming, in "8th ACM Symposium on Computational Geometry," pp. 1-8, 1992.

[21]

T. Radzik and A. V. Goldberg, Tight bounds on the number of minimum-mean cycle cancellations and related results, Algorithmica 11 (1994), 226-242.

Digital Library

[22]

R. Seidel, Linear programming and convex hulls made easy, Discrete Comput . Geom . 6 (1991), 423-434.

[23]

L. Shafer and W. Steiger, Randomizing optimal geometric algorithms, in "5th Canadian Conference on Computational Geometry," pp. 133-138, 1993.

[24]

N. E. Young, R. E. Tarjan, and J. B. Orlin, Faster parametric shortest path and minimum-balance algorithms, Networks 21 (1991), 205-221.

Cited By

Belfodil ADuivesteijn WPlantevit MCazalens SLamarre P(2019)DEvIANT: Discovering Significant Exceptional (Dis-)Agreement Within GroupsMachine Learning and Knowledge Discovery in Databases10.1007/978-3-030-46150-8_1(3-20)Online publication date: 16-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-46150-8_1
Shi ZTang ZTran-Thanh LSingh RFang F(2018)Designing the game to playProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304415.3304488(512-518)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304415.3304488
Roy SChiticariu LFeldman VReiss FZhu HRoss KSrivastava DPapadias D(2013)Provenance-based dictionary refinement in information extractionProceedings of the 2013 ACM SIGMOD International Conference on Management of Data10.1145/2463676.2465284(457-468)Online publication date: 22-Jun-2013
https://dl.acm.org/doi/10.1145/2463676.2465284
Show More Cited By

Index Terms

Choosing Subsets with Maximum Weighted Average
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
  2. Mathematical software
2. Theory of computation

Recommendations

Cohen's linearly weighted kappa is a weighted average

An n n agreement table F = {f ij } with n 3 ordered categories can for fixed m (2 m n 1) be collapsed into $${\binom{n-1}{m-1}}$$ distinct m m tables by combining adjacent categories. It is shown that the components (observed and expected agreement) of ...
Efficient computation of maximum weighted independent sets on weighted dynamic graph
Abstract
An independent set is a set of vertices in a graph in which no two vertices are adjacent to each other. The maximum weighted independent set is the independent set with the largest sum of weights in a weighted graph. Considering that existing ...
Total list weighting of graphs with bounded maximum average degree
Abstract
A proper total weighting of a graph G is a mapping ϕ which assigns to each vertex and each edge of G a real number as its weight so that for any edge u v of G, ∑ e ∈ E ( v ) ϕ ( e ) + ϕ ( v ) ≠ ∑ e ∈ E ( u ) ϕ ( e ) + ϕ ( u ). A ( k , ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Algorithms

Journal of Algorithms Volume 24, Issue 1

July 1997

221 pages

ISSN:0196-6774

Editors:
Zvi Galil
Columbia Univ., New York, NY
,
David S. Johnson
AT&T Bell Labs., Murray Hill, NJ
,
Donald E. Knuth
Stanford Univ., Stanford, CA

Issue’s Table of Contents

Copyright © Academic Press.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 July 1997

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Belfodil ADuivesteijn WPlantevit MCazalens SLamarre P(2019)DEvIANT: Discovering Significant Exceptional (Dis-)Agreement Within GroupsMachine Learning and Knowledge Discovery in Databases10.1007/978-3-030-46150-8_1(3-20)Online publication date: 16-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-46150-8_1
Shi ZTang ZTran-Thanh LSingh RFang F(2018)Designing the game to playProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304415.3304488(512-518)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304415.3304488
Roy SChiticariu LFeldman VReiss FZhu HRoss KSrivastava DPapadias D(2013)Provenance-based dictionary refinement in information extractionProceedings of the 2013 ACM SIGMOD International Conference on Management of Data10.1145/2463676.2465284(457-468)Online publication date: 22-Jun-2013
https://dl.acm.org/doi/10.1145/2463676.2465284
Wu BKshemkalyani A(2006)Objective-Optimal Algorithms for Long-Term Web PrefetchingIEEE Transactions on Computers10.1109/TC.2006.1255:1(2-17)Online publication date: 1-Jan-2006
https://dl.acm.org/doi/10.1109/TC.2006.12
McGrail RMcGrail T(2004)A grading dilemma or the abyss between sorting and the knapsack problemJournal of Computing Sciences in Colleges10.5555/1060081.106009619:5(97-107)Online publication date: 1-May-2004
https://dl.acm.org/doi/10.5555/1060081.1060096

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents