L. G. Babat, "Approximate Computation of Linear Functions on Vertices of the Unit N-dimensional Cube", in Studies in Discrets Optimization, pp. 156--169, A. A. Fridman (ed.) Nauka, Moscow, 1976 (Russian).

Google Scholar

[3]

L. G. Babat, "A Fixed-Charge Problem", Izv. Akad. Nauk SSSR, Techn. Kibernet. 3, 25--31 (1978) (Russian).

Google Scholar

[4]

I. S. Belov and Stolin Ja. I., "An Algorithm for a Flow-shop Scheduling Problem", in Mathematical Economics and Functional Analysis, pp. 218--257, B. S. Mityagin (ed.), Nauka, Moscow, 1974 (Russian).

Google Scholar

[5]

S. A. Cook, "The Complexity of Theorem Proving Procedures" Proc. 3-rd Annual ACM Symposium on the Theory of Computing, pp. 151--159, Shaker Heights, Ohio, 1971.

Digital Library

Google Scholar

[6]

G. Cornuejols, M. L. Fisher and G. L. Nemhauser, "Location of Bank Accounts to Optimize Floats", Manag. Sci. 23, 789--810, (1977).

Digital Library

Google Scholar

[7]

E. A. Dinic, "A Boolean Programming Problem", in Soft-Ware Systems for Optimal Planning Problems, Proc. V All-Union Symposium pp. 190--191, Central Economic and Mathematical Institute, Moscow, 1978, (Russian).

Google Scholar

[8]

E. A. Dinic, A. V. Karzanov, "A Boolean Optimization Problem with Special Constraints". Moscow, All-Union Institute of System Research, 1978 (Russian).

Google Scholar

[9]

Ju. Ju. Finkel' stein, Approximation Methods and Applied Discrete Programming Problems, Nauka, Moscow, (1976) (Russian).

Google Scholar

[10]

Ju. Ju. Finkel' stein, "An e-approach to the Multidimensional Knapsack Problem", Zur. Vychisl. Mat. i Mat. Fiz. 17, 1040--1042, (1977) (Russian).

Google Scholar

[11]

A. A. Fridman, M. A. Frumkin, Ju. I Hmelevskii and E. V. Levner, "Study of Algorithm Efficiency for Discrete and Combinatorial Problems. Theory of Problem Reducibility and Universal Problems". Report No GR-76060393, Moscow, Central Economic and Mathematical Institute, USSR Academy of Sciences. 1976 (Russian).

Google Scholar

[12]

A. A. Fridman "New Directions in Discrete Optimization", Ekon. i Mat. Metody 13, 1115--1131 (1977) (Russian).

Google Scholar

[13]

M. R. Garey, R. L. Graham and D. S. Johnson, "Performance Guarantees for Scheduling Algorithms", Oper. Res. 26, 3--21, (1978).

Digital Library

Google Scholar

[14]

M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman, San Francisco, 1979.

Digital Library

Google Scholar

[15]

G. V. Gens and E. V. Levner, "On Approximation Algorithms for Universal Scheduling Problems", Izv. Akad. Nauk SSSR, Tehn. Kibernet. 6, 38--43 (1978) (Russian).

Google Scholar

[16]

G. V. Gens and E. V. Levner, "Computational Complexity of Approximation Algorithms for Combinatorial Problems", Proc. 8th Symposium on Mathematical Foundations of Computer Science, Olomouc, Czechoslovakia, (1979), Lecture Notes in Computer Science, vol. 74. Springer-Verlag. Berlin-New York, 1979.

Crossref

Google Scholar

[17]

E. H. Gimadi, N. I. Glebov and V. A. Perepelica, "Algorithms with Performance Guarantees for Discrete Optimization Problems". Problems of Cybernetics, book 31, Nauka, Moscow, 1976 (Russian).

Google Scholar

[18]

R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, "Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey", Annals of Discrete Mathematics, 5 (1978).

Google Scholar

[19]

D. Yu. Grigoryev, "An Application of Separability and Independence Notions for Proving Lower Bounds of Circuit Complexity", in Studies on Constructive Mathematics and Mathematical Logic, pp. 38--48, Yu. V. Matiyasevich and A. O. Slisenko (eds.). Zap. nauchm. seminarov Leningrad. otd. Mat. Inst. AN SSSR, 60, Nauka, Leningrad, 1976 (Russian).

Google Scholar

[20]

O. H. Ibarra, C. E. Kim "Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems", J. ACM., 22, 463--468, (1975).

Digital Library

Google Scholar

[21]

D. S. Johnson, "Approximation algorithms for Combinatorial Problems", J. Comput. Systems Sci., 9, 256--278 (1974).

Digital Library

Google Scholar

[22]

R. M. Karp, "Reducibility among Combinatorial Problems", in "Complexity of Computer Computations", pp. 85--109, R. E. Miller and T. W. Thatcher (eds.), Plenum Press, New York, 1972.

Crossref

Google Scholar

[23]

R. M. Karp, "The Probabilistic Analysis of Some Combinatorial Search Algorithms", in Algorithms and Complexity, pp. 1--19, J. B. Traub (ed.), Academic Press, New York, 1976.

Google Scholar

[24]

M. T. Kaufman, "An Almost-optimal Algorithm for the Assembly Line Scheduling Problem", LEEE Trans. on Comp., C-23, (1974), 1169--1174.

Digital Library

Google Scholar

[25]

L. G. Khachiyan, "A Polynomial Algorithm for the Linear programming Problem", Dokl. Akad. Nauk SSSR, 244, No 5 (1979) (Russian).

Google Scholar

[26]

V. K. Korobkov, R. E. Krichevskii, "Algorithms for the Traveling Salesman Problem", in Mathematical Models and Methods of Optimal Planning, pp. 106--108, Nauka, Novosibirsk, 1966 (Russian).

Google Scholar

[27]

E. L. Lawler, "Fast Approximation Algorithms for Knapsack Problem", Memorandum No UCB/ERL M 77/45, Electronics Research Laboratory, University of California, Berkeley, June 1977.

Google Scholar

[28]

V. K. Leont'ev, "Study of an Algorithm for Solving Traveling Salesman Problem", Zur. Vych.Mat. i Mat Fiz., 13, 1228--1236 (1973) (Russian).

Google Scholar

[29]

V. K. Leont'ev, "Discrete Extremal Problems", in Theory of Probability. Mathematical Statistics. Theoretical Cybernetics, pp. 39--101, R. V. Gamkrelidze (Ed.) VINITI, Moscow, 1979, (Russian).

Google Scholar

[30]

L. A. Levin, "Universal Problems of Combinatorial Search", Problemy Peredachy Informacii, 9, 115--116, (1973) (Russian).

Google Scholar

[31]

E. V. Levner and G. V. Gens, "On ε-Algorithms for Universal Discrete Problems", Proc. IV All-Union Conf. on Problems of Theoret. Cybern., pp. 95--96, Inst. Mat., Novosibirsk, (1977).

Google Scholar

[32]

E. V. Levner, and G. V. Gens, Discrete Optimization Problems and Efficient Approximation Algorithms, Moscow, Central Economic and Mathem. Institute, 1978 (Russian).

Google Scholar

[33]

E. V. Levner and G. V. Gens. "Fast Approximation Algorithms for knapsack type problems", Proc. IX Conf. IFIP on Optimization Techniques, Warsaw, September 1979, Lecture Notes in Computer Science, Springer-Verlag, Berlin - New York. 1979.

Google Scholar

[34]

E. M. Livshic, "Analysis of Algorithms for Network Model Optimization", Ekon. i Mat. Metody, 4, 768--775 (1968) (Russian).

Google Scholar

[35]

E. M. Livashic, "Performance Bounds for Approximate Solutions of Optimization Network Problems" in Proc. I Winter School on Math. Programming, book 3, pp. 477--497, Central Economic and Mathem. Institute, Moscow, 1969 (Russian).

Google Scholar

[36]

E. M. Livshic and V. I. Rublineckii, "On Relative Complexity of Discrete Optimization Problems" in Vych. Mat i Vych. Teh. 3, 78--95, Kharkov, 1972 (Russian).

Google Scholar

[37]

R. G. Nigmatullin, "The Fastest Descent Method for Covering Problems", Proc. Symposium on Questions of Precision and Efficiency of Computer Algorithms, book 5, 116--126, Kiev, 1969 (Russian).

Google Scholar

[38]

R. G. Nigmatullin, "Complexity of Approximate Solution of Combinatorial Problems", Dokl. Akad. Nauk SSSR, 224, No 2, (1975), (Russian).

Google Scholar

[39]

R. G. Nigmatullin, "On Approximate Algorithms with Bounded Absolute Error for Discrete Extremal Problems", Kybernetika, 1, 96--101, (1978) (Russian).

Google Scholar

[40]

D. J. Rosenkrantz, R. E. Stearns and P. M. Lewis, "Approximate Algorithms for the Traveling Salesman Problem", Proc 15th Annual IEEE Symp. on Switching and Automata Theory. pp. 33--42, (1974).

Digital Library

Google Scholar

[41]

V. I. Rublineckii, "On Procedures with Performance Guarantees for Traveling Salesman Problem", Vych Mat. i Vych Tehn. 4, 18--23, Kharkov, 1973 (Russian).

Google Scholar

[42]

S. Sahni, "Algorithms for Scheduling Independent Tasks", J. ACM, 23, 114--127, (1976).

Digital Library

Google Scholar

[43]

S. Sahni and T. Gonzales "p - complete Approximation Problems", J. ACM, 23, 555--565 (1976).

Digital Library

Google Scholar

[44]

S. Sahni and E. Horowitz. Combinatorial Problems: Reducibility and Approximation, Oper. Res. 26, 718--759 (1978).

Digital Library

Google Scholar

[45]

S. V. Sevost'yanov. "On Asymtolic Approach to Scheduling Problems, in Upravl. Systemi (upravl. procesi), v. 14, Novosibirsk, Nauka, 1975, pp. 40--51. (Russian).

Google Scholar

[46]

S. B. Sevost'yanov, "On Approximate Solution of Scheduling Problems", in Metody Discret. Analyza v Synt. Uprav. System, 32, (1978), Novosibirsk, 66--75 (Russian).

Google Scholar

[47]

V. G. Vizing, "The Object Function Values in Sequencing Problems Dominated by an Average Value", Kibernetika, 5, 76--78, (1973), (Russian).

Google Scholar

[48]

D. B. Yudin, A. S. Nemirovskii, "Bounds for Information Complexity of Mathematical Programming Problems", Ekonom, i Mat. Metody. 12, 123--142, (1976) (Russian).

Google Scholar

Cited By

View all

Romero DViet PShrestha R(2024)Aerial Base Station Placement via Propagation Radio MapsIEEE Transactions on Communications10.1109/TCOMM.2024.338311172:9(5349-5364)Online publication date: Sep-2024
https://doi.org/10.1109/TCOMM.2024.3383111
Wang YSu LChen JWang NLi Z(2024)Adaptive Pricing and Online Scheduling for Distributed Machine Learning JobsIEEE Internet of Things Journal10.1109/JIOT.2023.333675711:7(12966-12983)Online publication date: 1-Apr-2024
https://doi.org/10.1109/JIOT.2023.3336757
Huang CObscura Acosta NYingchareonthawornchai S(2024)An FPTAS for Connectivity InterdictionInteger Programming and Combinatorial Optimization10.1007/978-3-031-59835-7_16(210-223)Online publication date: 3-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-59835-7_16
Show More Cited By

Complexity of approximation algorithms for combinatorial problems: a survey
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems

In this paper we study the (in)approximability of two distance-based relaxed variants of the maximum clique problem (Max Clique), named Max d-Clique and Max d-Club: A d-clique in a graph $$G = (V, E)$$G=(V,E) is a subset $$S\subseteq V$$S⊆V of vertices ...
Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems
COCOA 2015: Proceedings of the 9th International Conference on Combinatorial Optimization and Applications - Volume 9486

A d-clique in a graph $$G = V, E$$G=V,E is a subset $$S\subseteq V$$S⊆V of vertices such that for pairs of vertices $$u, v\in S$$u,v∈S, the distance between u and v is at most d in G. A d-club in a graph $$G = V, E$$G=V,E is a subset $$S'\subseteq V$$S'⊆...
Approximation Algorithms for Multi-Criteria Traveling Salesman Problems

We analyze approximation algorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with ź-triangle inequality. For this problem, we present a deterministic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGACT News Volume 12, Issue 3

Fall 1980

65 pages

ISSN:0163-5700

DOI:10.1145/1008861

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1980

Published in SIGACT Volume 12, Issue 3

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

36
Total Citations
View Citations
1,199
Total Downloads

Downloads (Last 12 months)112
Downloads (Last 6 weeks)14

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Romero DViet PShrestha R(2024)Aerial Base Station Placement via Propagation Radio MapsIEEE Transactions on Communications10.1109/TCOMM.2024.338311172:9(5349-5364)Online publication date: Sep-2024
https://doi.org/10.1109/TCOMM.2024.3383111
Wang YSu LChen JWang NLi Z(2024)Adaptive Pricing and Online Scheduling for Distributed Machine Learning JobsIEEE Internet of Things Journal10.1109/JIOT.2023.333675711:7(12966-12983)Online publication date: 1-Apr-2024
https://doi.org/10.1109/JIOT.2023.3336757
Huang CObscura Acosta NYingchareonthawornchai S(2024)An FPTAS for Connectivity InterdictionInteger Programming and Combinatorial Optimization10.1007/978-3-031-59835-7_16(210-223)Online publication date: 3-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-59835-7_16
van Zyl JEngelbrecht A(2023)Set-Based Particle Swarm Optimisation: A ReviewMathematics10.3390/math1113298011:13(2980)Online publication date: 4-Jul-2023
https://doi.org/10.3390/math11132980
Zhou RPang JZhang QWu CJiao LZhong YLi Z(2023)Online Scheduling Algorithm for Heterogeneous Distributed Machine Learning JobsIEEE Transactions on Cloud Computing10.1109/TCC.2022.314315311:2(1514-1529)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TCC.2022.3143153
Gosrich WMayya SNarayan SMalencia MAgarwal SKumar V(2023)Multi-Robot Coordination and Cooperation with Task Precedence Relationships2023 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA48891.2023.10160998(5800-5806)Online publication date: 29-May-2023
https://doi.org/10.1109/ICRA48891.2023.10160998
Wang NZhou RHan LChen HLi Z(2022)Online Scheduling of Distributed Machine Learning Jobs for Incentivizing Sharing in Multi-Tenant SystemsIEEE Transactions on Computers10.1109/TC.2022.3174566(1-1)Online publication date: 2022
https://doi.org/10.1109/TC.2022.3174566
Su LWang NZhou RLi Z(2022)Dynamic service placement and request scheduling for edge networksComputer Networks10.1016/j.comnet.2022.108997213(108997)Online publication date: Aug-2022
https://doi.org/10.1016/j.comnet.2022.108997
Xu QYan XWu KWang JLu KWu W(2021)Leveraging Multiplexing Gain in Network Slice BundlesIEEE Transactions on Network Science and Engineering10.1109/TNSE.2020.30313478:1(149-162)Online publication date: 1-Jan-2021
https://doi.org/10.1109/TNSE.2020.3031347
Zhang QZhou RWu CJiao LLi ZMelodia TEkici EAbouzeid AChen M(2020)Online scheduling of heterogeneous distributed machine learning jobsProceedings of the Twenty-First International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing10.1145/3397166.3409128(111-120)Online publication date: 11-Oct-2020
https://dl.acm.org/doi/10.1145/3397166.3409128
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Abstract

References

Cited By

Recommendations

Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems

Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems

Approximation Algorithms for Multi-Criteria Traveling Salesman Problems

Comments

Information

Published In

Publisher

Publication History

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations