article

Local ratio: A unified framework for approximation algorithms. In Memoriam: Shimon Even 1935-2004

Authors:

Reuven Bar-Yehuda,

Keren Bendel,

Ari Freund,

Dror RawitzAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 36, Issue 4

Pages 422 - 463

https://doi.org/10.1145/1041680.1041683

Published: 01 December 2004 Publication History

Get Access

Abstract

The local ratio technique is a methodology for the design and analysis of algorithms for a broad range of optimization problems. The technique is remarkably simple and elegant, and yet can be applied to several classical and fundamental problems (including covering problems, packing problems, and scheduling problems). The local ratio technique uses elementary math and requires combinatorial insight into the structure and properties of the problem at hand. Typically, when using the technique, one has to invent a weight function for a problem instance under which every "reasonable" solution is "good." The local ratio technique is closely related to the primal-dual schema, though it is not based on weak LP duality (which is the basis of the primal-dual approach) since it is not based on linear programming.In this survey we, introduce the local ratio technique and demonstrate its use in the design and analysis of algorithms for various problems. We trace the evolution path of the technique since its inception in the 1980's, culminating with the most recent development, namely, fractional local ratio, which can be viewed as a new LP rounding technique.

References

[1]

Agrawal, A., Klein, P., and Ravi, R. 1995. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J Comput 24, 3, 440--456.]]

Digital Library

Google Scholar

[2]

Akcoglu, K., Aspnes, J., DasGupta, B., and Kao, M.-Y. 2002. Opportunity cost algorithms for combinatorial auctions. In Applied Optimization: Computational Methods in Decision-Making Economics and Finance, E. J. Kontoghiorghes, B. Rustem, and S. Siokos, Eds. Kluwer Academic Publishers.]]

Google Scholar

[3]

Albers, S., Arora, S., and Khanna, S. 1999. Page replacement for general caching problems. In 10th Annual ACM-SIAM Symposium on Discrete Algorithms. 31--40.]]

Digital Library

Google Scholar

[4]

Arkin, E. M. and Silverberg, E. B. 1987. Scheduling jobs with fixed start and end times. Disc. Appl. Math. 18, 1--8.]]

Digital Library

Google Scholar

[5]

Bafna, V., Berman, P., and Fujito, T. 1999. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Dis. Math. 12, 3, 289--297.]]

Digital Library

Google Scholar

[6]

Bafna, V., Narayanan, B., and Ravi, R. 1996. Nonoverlapping local alignments (weighted independent sets of axis parallel rectangles). Disc. Appl. Math. 71, (Special issue on Computational Molecular Biolagy). 41--53.]]

Digital Library

Google Scholar

[7]

Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., and Shieber, B. 2001a. A unified approach to approximating resource allocation and schedualing. J. ACM 48, 5, 1069--1090.]]

Digital Library

Google Scholar

[8]

Bar-Noy, A., Guha, S., Katz, Y., Naor, J., Schieber, B., and Shachnai, H. 2002. Throughput maximization of real-time scheduling with batching. In 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 742--751.]]

Digital Library

Google Scholar

[9]

Bar-Noy, A., Guha, S., Naor, J., and Schieber, B. 2001b. Approximating the throughput of multiple machines in real-time scheduling. SIAMJ. Comput. 31, 2, 331--352.]]

Digital Library

Google Scholar

[10]

Bar-Yehuda. 2001. Using homogeneous weights for approximating the partial cover problem. J. Algor. 39, 137--144.]]

Digital Library

Google Scholar

[11]

Bar-Yehuda, R. 2000. One for the price of two: A unified approach for approximating covering problems. Algorithmica 27, 2, 131--144.]]

Crossref

Google Scholar

[12]

Bar-Yehuda, R. and Even, S. 1981. A linear time approximation algorithm for the weighted vertex cover problem. J. Algor. 2, 198--203.]]

Crossref

Google Scholar

[13]

Bar-Yehuda, R. and Even, S. 1985. A local-ratio theorem for approximating the weighted vertex cover problem. Ann. Discr. Math. 25, 27--46.]]

Google Scholar

[14]

Bar-Yehuda, R., Geiger, D., Naor, J., and Roth, R. M. 1998. Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and bayesian inference. SIAM J. Comput. 27, 4, 942--959.]]

Digital Library

Google Scholar

[15]

Bar-Yehuda, R., Halldórsson, M. M., Naor, J., Shachnai, H., and Shapira, I. 2002. Scheduling split intervals. In 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 732--741.]]

Digital Library

Google Scholar

[16]

Bar-Yehuda, R. and Rawitz, D. 2001. On the equivalence between the primal-dual schema and the local-ratio technique. In 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. Lecture Notes in Computer Science, vol. 2129. 24--35.]]

Digital Library

Google Scholar

[17]

Bar-Yehuda, R. and Rawitz, D. 2002. Approximating element-weighted vertex deletion problems for the complete <>k</>-partite property. J. Algor. 42, 1, 20--40.]]

Digital Library

Google Scholar

[18]

Bar-Yehuda, R. and Rawitz, D. 2004. Local ratio with negative weights. Oper. Resear. Letters 32, 6, 540--546.]]

Digital Library

Google Scholar

[19]

Becker, A. and Geiger, D. 1996. Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artif. Intell. 83, 1, 167--188.]]

Digital Library

Google Scholar

[20]

Berman, P. and DasGupta, B. 2000. Multi-phase algorithms for throughput maximization for real-time scheduling. J. Combin. Optimi. 4, 3, 307--323.]]

Crossref

Google Scholar

[21]

Bertsimas, D. and Teo, C. 1998. From valid inequalities to heuristics: A unified view of primal-dual approximation algorithms in covering problems. Operat. Resear. 46, 4, 503--514.]]

Digital Library

Google Scholar

[22]

Bhatia, R., Chuzhoy, J., Freund, A., and Naor, J. 2003. Algorithmic aspects of bandwidth trading. In 30th International Colloquium on Automata, Languages, and Programming. Lecture Notes in Computer Science, vol. 2719. 751--766.]]

Digital Library

Google Scholar

[23]

Bshouty, N. H. and Burroughs, L. 1998. Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem. In 15th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 1373. Springer, 298--308.]]

Digital Library

Google Scholar

[24]

Cai, M., Deng, X., and Zang, W. 2001. An approximation algorithm for feedback vertex sets in tournaments. SIAM J. Comput. 30, 6, 1993--2007.]]

Digital Library

Google Scholar

[25]

Chudak, F. A., Goemans, M. X., Hochbaum, D. S., and Williamson, D. P. 1998. A primal-dual interpretation of recent 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Operat. Resear. Letters 22, 111--118.]]

Digital Library

Google Scholar

[26]

Chuzhoy, J., Ostrovsky, R., and Rabani, Y. 2001. Approximation algorithms for the job interval selection problem and related scheduling problems. In 42nd IEEE Symposium on Foundations of Computer Science. 348--356.]]

Digital Library

Google Scholar

[27]

Chvátal, V. 1979. A greedy heuristic for the set-covering problem. Math. Operat. Resear. 4, 3, 233--235.]]

Digital Library

Google Scholar

[28]

Cormen, T. H., Leiserson, C. E., and Rivest, R. L. 1990. Introduction to Algorithms. The MIT Press.]]

Digital Library

Google Scholar

[29]

Dinur, I. and Safra, S. 2002. The importance of being biased. In 34th ACM Symposium on the Theory of Computing. 33--42.]]

Digital Library

Google Scholar

[30]

Erdös, P. and Pósa, L. 1962. On the maximal number of disjoint circuits of a graph. Publ. Math. Debrecen 9, 3--12.]]

Google Scholar

[31]

Even, S. 1979. Graph Algorithms. Computer Science Press.]]

Digital Library

Google Scholar

[32]

Feige, U. 1996. A threshold of ln n for approximating set cover. In 28th Annual Symposium on the Theory of Computing. 314--318.]]

Digital Library

Google Scholar

[33]

Ford, L. R. and Fulkerson, D. R. 1956. Maximal flow through a network. Canadian J. Math. 8, 399--404.]]

Crossref

Google Scholar

[34]

Freund, A. and Rawitz, D. 2003. Combinatorial interpretations of dual fitting and primal fitting. In 1st International Workshop on Approximation and Online Algorithms. Lecture Notes in Computer Science, vol. 2909. Springer-Verlag, 137--150.]]

Google Scholar

[35]

Fujito, T. 1998. A unified approximation algorithm for node-deletion problems. Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science 86, 213--231.]]

Digital Library

Google Scholar

[36]

Gabow, H. N., Goemans, M. X., and Williamson, D. P. 1993. An efficient approximation algorithm for the survivable network design problem. In 3rd MPS Conference on Integer Programming and Combinatorial Optimization.]]

Google Scholar

[37]

Gandhi, R., Khuller, S., and Srinivasan, A. 2001. Approximation algorithms for partial covering problems. In 28th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 2076, 225--236.]]

Digital Library

Google Scholar

[38]

Garey, M. R., Graham, R. L., Johnson, D. S., and Yao, A. C.-C. 1976a. Resource constrained scheduling as generalized bin packing. J. Combin. Theor. (A) 21, 257--298.]]

Crossref

Google Scholar

[39]

Garey, M. R., Graham, R. L., and Ullman, J. D. 1972. Worst-case analysis of memory allocation algorithms. In 4th Annual ACM Symposium on Theory of Computing. 143--150.]]

Digital Library

Google Scholar

[40]

Garey, M. R. and Johnson, D. S. 1979. Computers and Intractability; A Guide to the Theory of NP-Completeness. W.H. Freeman and Company.]]

Digital Library

Google Scholar

[41]

Garey, M. R., Johnson, D. S., and Stockmeyer, L. 1976b. Some simplified np-complete graph problems. Theo. Comput. Sci. 1, 237--267.]]

Crossref

Google Scholar

[42]

Goemans, M. X., Goldberg, A., S.Plotkin, Shmoys, D., Tardos, E., and Williamson, D. P. 1994. Improved approximation algorithms for network design problems. In 5th Annual ACM-SIAM Symposium on Discrete Algorithms. 223--232.]]

Digital Library

Google Scholar

[43]

Goemans, M. X. and Williamson, D. P. 1995. A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 2, 296--317.]]

Digital Library

Google Scholar

[44]

Goemans, M. X. and Williamson, D. P. 1997. The primal-dual method for approximation algorithms and its application to network design problems. See Hochbaum {1997}, Chapter 4, 144--191.]]

Digital Library

Google Scholar

[45]

Golumbic, M. C. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press.]]

Digital Library

Google Scholar

[46]

Grötschel, M., Lovász, L., and Schrijver, A. 1988. Geometric algorithms and combinatorial optimization. Springer-Verlag, Berlin.]]

Google Scholar

[47]

Guha, S., Hassin, R., Khuller, S., and Or, E. 2002. Capacitated vertex covering with applications. In 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 858--865.]]

Digital Library

Google Scholar

[48]

Halperin, E. 2000. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. In 11th Annual ACM-SIAM Symposium on Discrete Algorithms. 329--337.]]

Digital Library

Google Scholar

[49]

HÅstad, J. 1996. Clique is hard to approximate within n1−ε. In 37th IEEE Symposium on Foundations of Computer Science. 627--636.]]

Digital Library

Google Scholar

[50]

HÅstad, J. 1997. Some optimal inapproximability results. In 29th Annual ACM Symposium on the Theory of Computing. 1--10.]]

Digital Library

Google Scholar

[51]

Hochbaum, D. S. 1982. Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput. 11, 3, 555--556.]]

Digital Library

Google Scholar

[52]

Hochbaum, D. S. 1983. Efficient bounds for the stable set, vertex cover and set packing problems. Disc. App. Math. 6, 243--254.]]

Crossref

Google Scholar

[53]

Hochbaum, D. S. 1997. In Approximation Algorithms for NP-Hard Problem, D. S. Hochbaum Ed. PWS Publishing Company.]]

Digital Library

Google Scholar

[54]

Hochbaum, D. S. 1998. Approximating clique and biclique problems. J. Algor. 29, 1, 174--200.]]

Digital Library

Google Scholar

[55]

Hochbaum, D. S. 2002. Solving integer programs over monotone inequalities in three variables: a framework of half integrality and good approximations. European J. Oper. Resear. 140, 2, 291--321.]]

Crossref

Google Scholar

[56]

Imielińska, C., Kalantari, B., and Khachiyan, L. 1993. A greedy heuristic for a minimum-weight forest problem. Operat. Resear. Letters 14, 65--71.]]

Digital Library

Google Scholar

[57]

Jain, K. 1998. A factor 2 approximation algorithm for the generalized steiner network problem. In 39th IEEE Symposium on Foundations of Computer Science. 448--457.]]

Digital Library

Google Scholar

[58]

Jain, K., Mahdian, M., and Saberi, A. 2002. A new greedy approach for facility location problems. In 34th ACM Symposium on the Theory of Computing. 731--740.]]

Digital Library

Google Scholar

[59]

Johnson, D. S. 1974. Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9, 256--278.]]

Digital Library

Google Scholar

[60]

Karp, R. M. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds. Plenum Press, New York, 85--103.]]

Google Scholar

[61]

Kearns, M. 1990. The Computational Complexity of Machine Learning. M.I.T. Press.]]

Digital Library

Google Scholar

[62]

Kruskal, J. 1956. On the shortest spanning subtree of a graph and the traveling salesman problem. In The American Mathematical Society. Vol. 7, 48--50.]]

Crossref

Google Scholar

[63]

Laporte, G. 1988. Location-routing problems. In Vehicle Routing: Methods and Studies, B. L. Golden and A. A. Assad, Eds. 163--197.]]

Google Scholar

[64]

Laporte, G., Nobert, Y., and Pelletier, P. 1983. Hamiltonian location problems. European J. Oper. Resear. 12, 82--89.]]

Crossref

Google Scholar

[65]

Lewis, J. M. and Yannakakis, M. 1980. The node-deletion problem for hereditary problems is NP-complete. J. Comput. Syst. Sci. 20, 219--230.]]

Crossref

Google Scholar

[66]

Lovász, L. 1975. On the ratio of optimal integral and fractional covers. Discr. Math. 13, 383--390.]]

Digital Library

Google Scholar

[67]

Lund, C. and Yannakakis, M. 1993. The approximation of maximum subgraph problems. In 20th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 700. 40-- 51.]]

Digital Library

Google Scholar

[68]

Monien, B. and Shultz, R. 1981. Four approximation algorithms for the feedback vertex set problem. In 7th Conference on Graph Theoretic Concepts of Computer Science. 315--390.]]

Google Scholar

[69]

Monien, B. and Speckenmeyer, E. 1985. Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Inform. 22, 115--123.]]

Digital Library

Google Scholar

[70]

Nemhauser, G. L. and Trotter, L. E. 1975. Vertex packings: structural properties and algorithms. Math. Programm. 8, 232--248.]]

Digital Library

Google Scholar

[71]

Nicholson, T. T. J. 1966. Finding the shortest route between two points in a network. Comput. J. 9, 275--280.]]

Crossref

Google Scholar

[72]

Ravi, R. and Klein, P. 1993. When cycles collapse: A general approximation technique for constrained two-connectivity problems. In 3rd Conference on Integer Programming and Combinatorial Optimization. 39--56.]]

Google Scholar

[73]

Rosenkrantz, D. J., Stearns, R. E., and Lewis, II, P. M. 1977. An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6, 3, 563--581.]]

Digital Library

Google Scholar

[74]

Slavík, P. 1997. Improved performance of the greedy algorithm for partial cover. Inform. Process. Letters 64, 5, 251--254.]]

Digital Library

Google Scholar

[75]

Spieksma, F. C. R. 1999. On the approximability of an interval scheduling problem. J. Schedul. 2, 5, 215--227.]]

Crossref

Google Scholar

[76]

West, D. and Shmoys, D. 1984. Recognizing graphs with fixed interval number is NP-complete. Dis. Appl. Math. 8, 295--305.]]

Crossref

Google Scholar

[77]

Williamson, D. P. 2002. The primal dual method for approximation algorithms. Mathemat. Programm. (Series B) 91, 3, 447--478.]]

Digital Library

Google Scholar

[78]

Williamson, D. P., Goemans, M. X., Mihail, M., and Vazirani, V. V. 1995. A primal-dual approximation algorithm for generalized Steiner network problems. Combinatorica 15, 435--454.]]

Crossref

Google Scholar

Cited By

View all

Halldórsson MRawitz D(2024)Distributed Fractional Local Ratio and Independent Set ApproximationInformation and Computation10.1016/j.ic.2024.105238(105238)Online publication date: Nov-2024
https://doi.org/10.1016/j.ic.2024.105238
Liu QHou BZhang GLiu W(2024)An approximation algorithm for the k-prize-collecting hitting set problemOptimization Letters10.1007/s11590-024-02155-4Online publication date: 13-Oct-2024
https://doi.org/10.1007/s11590-024-02155-4
Halldórsson MRawitz D(2024)Online Multiset Submodular CoverAlgorithmica10.1007/s00453-024-01234-386:7(2393-2411)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s00453-024-01234-3
Show More Cited By

Index Terms

Local ratio: A unified framework for approximation algorithms. In Memoriam: Shimon Even 1935-2004
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
2. Theory of computation

Recommendations

On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique

We discuss two approximation paradigms that were used to construct many approximation algorithms during the last two decades, the primal-dual schema and the local ratio technique. Recently, primal-dual algorithms were devised by first constructing a ...
Integrality Ratio for Group Steiner Trees and Directed Steiner Trees

The natural relaxation for the group Steiner tree problem, as well as for its generalization, the directed Steiner tree problem, is a flow-based linear programming relaxation. We prove new lower bounds on the integrality ratio of this relaxation. For ...
Adaptive Local Ratio

Local ratio is a well-known paradigm for designing approximation algorithms for combinatorial optimization problems. At a very high level, a local-ratio algorithm first decomposes the input weight function $w$ into a positive linear combination of ...

Reviews

Reviewer: Ranan B. Banerji

The authors describe this survey as a small textbook, and I agree wholeheartedly. But, it is a textbook summarizing about 80 related papers in 41 pages, so the interested reader is required to read it slowly, and with a lot of thought. Nevertheless, the guidance provided is excellent. The paper primarily considers graph-theoretic and set-theoretic problems. Most of the problems are nondeterministic polynomial time (NP) hard, although pedagogy may have demanded that a few other problems be addressed by the very generalized methods the authors use, to tie a wide range of optimization problems together under one model. An r -approximate algorithm for the solution of an optimization problem is defined as one that yields a solution whose value is within a factor r of the optimal cost ( r will be greater than 1 for minimization problems and less than 1 for maximization problems). Local ratio algorithms apply in the case where a solution can be represented by a vector, and the solution's cost can be represented by the scalar product of the solution vector and a "weight vector" gleaned from the problem. The representation of a problem in this form is where the ingenuity of the designer is required. Many graph problems are classified into the general class of "graph editing" problems. The authors address solutions of partial problems whose weight and solution vectors can be seen as the sum of two partial weight and solution vectors. The local ratio theorem shows that, if the partial solutions are r -approximate, then so is their sum. The authors present a generic r -approximate solution as consisting of the recursion of a three-way "if-then" algorithm, with the three "then" parts of the algorithm called weight decomposition, problem reduction, and optimum solution. The above concepts and their applications are illustrated using many examples. The examples are used to introduce the concepts, and also to illustrate their application in a step-by-step manner. The authors discuss the challenges associated with the application of the model as they arise, and illustrate the way the challenges are met. In my experience, most approximate algorithms are described in the literature as being developed on an ad hoc basis for a specific problem. This survey is a laudable effort toward tying them into a uniform approach, and will be appreciated by disciplined and dedicated readers. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM Computing Surveys Volume 36, Issue 4

December 2004

129 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/1041680

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2004

Published in CSUR Volume 36, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

91
Total Citations
View Citations
2,619
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)2

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Halldórsson MRawitz D(2024)Distributed Fractional Local Ratio and Independent Set ApproximationInformation and Computation10.1016/j.ic.2024.105238(105238)Online publication date: Nov-2024
https://doi.org/10.1016/j.ic.2024.105238
Liu QHou BZhang GLiu W(2024)An approximation algorithm for the k-prize-collecting hitting set problemOptimization Letters10.1007/s11590-024-02155-4Online publication date: 13-Oct-2024
https://doi.org/10.1007/s11590-024-02155-4
Halldórsson MRawitz D(2024)Online Multiset Submodular CoverAlgorithmica10.1007/s00453-024-01234-386:7(2393-2411)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s00453-024-01234-3
Halldórsson MRawitz D(2024)Distributed Fractional Local Ratio and Independent Set ApproximationStructural Information and Communication Complexity10.1007/978-3-031-60603-8_16(281-299)Online publication date: 27-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-60603-8_16
Gupta SModak SSaurabh SSeetharaman S(2024)Quick-Sort Style Approximation Algorithms for Generalizations of Feedback Vertex Set in TournamentsLATIN 2024: Theoretical Informatics10.1007/978-3-031-55598-5_15(225-240)Online publication date: 6-Mar-2024
https://doi.org/10.1007/978-3-031-55598-5_15
Garg PJordan LSvensson O(2022)Semi-streaming algorithms for submodular matroid intersectionMathematical Programming: Series A and B10.1007/s10107-022-01858-9197:2(967-990)Online publication date: 27-Jul-2022
https://dl.acm.org/doi/10.1007/s10107-022-01858-9
Bansal NHarris D(2022)Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjectureRandom Structures & Algorithms10.1002/rsa.2108662:1(52-67)Online publication date: 16-Apr-2022
https://doi.org/10.1002/rsa.21086
Katz ORawitz DRaz D(2021)Containers Resource Allocation in Dynamic Cloud Environments2021 IFIP Networking Conference (IFIP Networking)10.23919/IFIPNetworking52078.2021.9472812(1-9)Online publication date: 21-Jun-2021
https://doi.org/10.23919/IFIPNetworking52078.2021.9472812
Yadav AChandra JSairam A(2021)A Budget and Deadline Aware Task Assignment Scheme for Crowdsourcing EnvironmentIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2021.3062843(1-1)Online publication date: 2021
https://doi.org/10.1109/TETC.2021.3062843
Halldórsson Mde Lima M(2021)Query-competitive sorting with uncertaintyTheoretical Computer Science10.1016/j.tcs.2021.03.021867(50-67)Online publication date: May-2021
https://doi.org/10.1016/j.tcs.2021.03.021
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique

Integrality Ratio for Group Steiner Trees and Directed Steiner Trees

Adaptive Local Ratio

Reviews

Access critical reviews of Computing literature here