{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,20]],"date-time":"2026-06-20T16:54:11Z","timestamp":1781974451016,"version":"3.54.5"},"reference-count":92,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2019,2,12]],"date-time":"2019-02-12T00:00:00Z","timestamp":1549929600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The next few years will be exciting as prototype universal quantum processors emerge, enabling the implementation of a wider variety of algorithms. Of particular interest are quantum heuristics, which require experimentation on quantum hardware for their evaluation and which have the potential to significantly expand the breadth of applications for which quantum computers have an established advantage. A leading candidate is Farhi et al.\u2019s quantum approximate optimization algorithm, which alternates between applying a cost function based Hamiltonian and a mixing Hamiltonian. Here, we extend this framework to allow alternation between more general families of operators. The essence of this extension, the quantum alternating operator ansatz, is the consideration of general parameterized families of unitaries rather than only those corresponding to the time evolution under a fixed local Hamiltonian for a time specified by the parameter. This ansatz supports the representation of a larger, and potentially more useful, set of states than the original formulation, with potential long-term impact on a broad array of application areas. For cases that call for mixing only within a desired subspace, refocusing on unitaries rather than Hamiltonians enables more efficiently implementable mixers than was possible in the original framework. Such mixers are particularly useful for optimization problems with hard constraints that must always be satisfied, defining a feasible subspace, and soft constraints whose violation we wish to minimize. More efficient implementation enables earlier experimental exploration of an alternating operator approach, in the spirit of the quantum approximate optimization algorithm, to a wide variety of approximate optimization, exact optimization, and sampling problems. In addition to introducing the quantum alternating operator ansatz, we lay out design criteria for mixing operators, detail mappings for eight problems, and provide a compendium with brief descriptions of mappings for a diverse array of problems.<\/jats:p>","DOI":"10.3390\/a12020034","type":"journal-article","created":{"date-parts":[[2019,2,13]],"date-time":"2019-02-13T02:49:44Z","timestamp":1550026184000},"page":"34","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":657,"title":["From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4607-3921","authenticated-orcid":false,"given":"Stuart","family":"Hadfield","sequence":"first","affiliation":[{"name":"Quantum Artificial Intelligence Laboratory (QuAIL), NASA Ames Research Center, Moffett Field, CA 94035, USA"},{"name":"USRA Research Institute for Advanced Computer Science (RIACS), Mountain View, CA 94043, USA"},{"name":"Department of Computer Science, Columbia University, New York, NY 10027, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhihui","family":"Wang","sequence":"additional","affiliation":[{"name":"Quantum Artificial Intelligence Laboratory (QuAIL), NASA Ames Research Center, Moffett Field, CA 94035, USA"},{"name":"USRA Research Institute for Advanced Computer Science (RIACS), Mountain View, CA 94043, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bryan","family":"O\u2019Gorman","sequence":"additional","affiliation":[{"name":"Quantum Artificial Intelligence Laboratory (QuAIL), NASA Ames Research Center, Moffett Field, CA 94035, USA"},{"name":"Stinger Ghaffarian Technologies, Inc., Greenbelt, MD 20770, USA"},{"name":"Berkeley Quantum Information and Computation Center and Departments of Chemistry and Computer Science, University of California, Berkeley, CA 94720, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eleanor G.","family":"Rieffel","sequence":"additional","affiliation":[{"name":"Quantum Artificial Intelligence Laboratory (QuAIL), NASA Ames Research Center, Moffett Field, CA 94035, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0452-7603","authenticated-orcid":false,"given":"Davide","family":"Venturelli","sequence":"additional","affiliation":[{"name":"Quantum Artificial Intelligence Laboratory (QuAIL), NASA Ames Research Center, Moffett Field, CA 94035, USA"},{"name":"USRA Research Institute for Advanced Computer Science (RIACS), Mountain View, CA 94043, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rupak","family":"Biswas","sequence":"additional","affiliation":[{"name":"Quantum Artificial Intelligence Laboratory (QuAIL), NASA Ames Research Center, Moffett Field, CA 94035, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2019,2,12]]},"reference":[{"key":"ref_1","unstructured":"Farhi, E., Goldstone, J., and Gutmann, S. (2019, February 11). A quantum approximate optimization algorithm. Available online: https:\/\/arxiv.org\/abs\/1411.4028."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/j.parco.2016.11.002","article-title":"A NASA perspective on quantum computing: Opportunities and challenges","volume":"64","author":"Biswas","year":"2017","journal-title":"Parallel Comput."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s11128-014-0892-x","article-title":"A case study in programming a quantum annealer for hard operational planning problems","volume":"14","author":"Rieffel","year":"2015","journal-title":"Quant. Inform. Process."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"5","DOI":"10.3389\/fphy.2014.00005","article-title":"Ising formulations of many NP problems","volume":"2","author":"Lucas","year":"2014","journal-title":"Front. Phys."},{"key":"ref_5","unstructured":"Hadfield, S. (2019, February 11). On the representation of Boolean and real functions as Hamiltonians for quantum computing. Available online: https:\/\/arxiv.org\/pdf\/1804.09130.pdf."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"034007","DOI":"10.1103\/PhysRevApplied.5.034007","article-title":"Quantum annealing for constrained optimization","volume":"5","author":"Hen","year":"2016","journal-title":"Phys. Rev. Appl."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"062312","DOI":"10.1103\/PhysRevA.93.062312","article-title":"Driver Hamiltonians for constrained optimization in quantum annealing","volume":"93","author":"Hen","year":"2016","journal-title":"Phys. Rev."},{"key":"ref_8","unstructured":"Rieffel, E.G., and Polak, W. (2011). Quantum Computing: A Gentle Introduction, MIT Press."},{"key":"ref_9","unstructured":"IBM (2017, September 01). IBM Q and Quantum Computing. Available online: https:\/\/www.research.ibm.com\/ibm-q\/."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"10327","DOI":"10.1038\/ncomms10327","article-title":"Computational multiqubit tunnelling in programmable quantum annealers","volume":"7","author":"Boixo","year":"2016","journal-title":"Nat. Commun."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Sete, E.A., Zeng, W.J., and Rigetti, C.T. (2016, January 17\u201319). A functional architecture for scalable quantum computing. Proceedings of the 2016 IEEE International Conference on Rebooting Computing (ICRC), San Diego, CA, USA.","DOI":"10.1109\/ICRC.2016.7738703"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1038\/543171a","article-title":"Commercialize quantum technologies in five years","volume":"543","author":"Mohseni","year":"2017","journal-title":"Nature"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1038\/nature18648","article-title":"Demonstration of a small programmable quantum computer with atomic qubits","volume":"536","author":"Debnath","year":"2016","journal-title":"Nature"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"202001","DOI":"10.1088\/0953-4075\/49\/20\/202001","article-title":"Quantum computing with atomic qubits and Rydberg interactions: progress and challenges","volume":"49","author":"Saffman","year":"2016","journal-title":"J. Phys. B Atom. Mol. Opt. Phys."},{"key":"ref_15","unstructured":"Zahedinejad, E., and Zaribafiyan, A. (2019, February 11). Combinatorial optimization on gate model quantum computers: A survey. Available online: https:\/\/arxiv.org\/pdf\/1708.05294.pdf."},{"key":"ref_16","unstructured":"Farhi, E., Goldstone, J., and Gutmann, S. (2019, February 11). A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem. Available online: https:\/\/arxiv.org\/pdf\/1412.6062.pdf."},{"key":"ref_17","unstructured":"Farhi, E., and Harrow, A.W. (2019, February 11). Quantum supremacy through the quantum approximate optimization algorithm. Available online: https:\/\/arxiv.org\/pdf\/1602.07674.pdf."},{"key":"ref_18","first-page":"021027","article-title":"Optimizing variational quantum algorithms using Pontryagin\u2019s minimum principle","volume":"7","author":"Yang","year":"2017","journal-title":"Phys. Rev. X"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"062317","DOI":"10.1103\/PhysRevA.95.062317","article-title":"Near-optimal quantum circuit for Grover\u2019s unstructured search using a transverse field","volume":"95","author":"Jiang","year":"2017","journal-title":"Phys. Rev. A"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"022309","DOI":"10.1103\/PhysRevA.94.022309","article-title":"Training a quantum optimizer","volume":"94","author":"Wecker","year":"2016","journal-title":"Phys. Rev. A"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"022304","DOI":"10.1103\/PhysRevA.97.022304","article-title":"Quantum approximate optimization algorithm for MaxCut: A fermionic view","volume":"97","author":"Wang","year":"2018","journal-title":"Phys. Rev. A"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"025004","DOI":"10.1088\/2058-9565\/aaa331","article-title":"Compiling quantum circuits to realistic hardware architectures using temporal planners","volume":"3","author":"Venturelli","year":"2018","journal-title":"Quantum Sci. Tech."},{"key":"ref_23","unstructured":"Barak, B., Moitra, A., O\u2019Donnell, R., Raghavendra, P., Regev, O., Steurer, D., Trevisan, L., Vijayaraghavan, A., Witmer, D., and Wright, J. (2019, February 11). Beating the random assignment on constraint satisfaction problems of bounded degree. Available online: https:\/\/arxiv.org\/pdf\/1505.03424.pdf."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Hadfield, S., Wang, Z., Rieffel, E.G., O\u2019Gorman, B., Venturelli, D., and Biswas, R. (2017, January 12\u201317). Quantum Approximate Optimization with Hard and Soft Constraints. Proceedings of the Second International Workshop on Post Moores Era Supercomputing, Denver, CO, USA.","DOI":"10.1145\/3149526.3149530"},{"key":"ref_25","unstructured":"Fingerhuth, M., Babej, T., and Ing, C. (2019, February 11). A quantum alternating operator ansatz with hard and soft constraints for lattice protein folding. Available online: https:\/\/arxiv.org\/pdf\/1810.13411.pdf."},{"key":"ref_26","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., and Neven, H. (2019, February 11). Quantum algorithms for fixed qubit architectures. Available online: https:\/\/arxiv.org\/pdf\/1703.06199.pdf."},{"key":"ref_27","unstructured":"Lechner, W. (2019, February 11). Quantum approximate optimization with parallelizable gates. Available online: https:\/\/arxiv.org\/pdf\/1802.01157.pdf."},{"key":"ref_28","unstructured":"Ho, W.W., and Hsieh, T.H. (2019, February 11). Efficient preparation of non-trivial quantum states using the quantum approximate optimization algorithm. Available online: https:\/\/arxiv.org\/pdf\/1803.00026.pdf."},{"key":"ref_29","unstructured":"Verdon, G., Broughton, M., and Biamonte, J. (2019, February 11). A quantum algorithm to train neural networks using low-depth circuits. Available online: https:\/\/arxiv.org\/pdf\/1712.05304.pdf."},{"key":"ref_30","unstructured":"Otterbach, J., Manenti, R., Alidoust, N., Bestwick, A., Block, M., Bloom, B., Caldwell, S., Didier, N., Fried, E.S., and Hong, S. (2019, February 11). Unsupervised machine learning on a hybrid quantum computer. Available online: https:\/\/arxiv.org\/pdf\/1712.05771.pdf."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s11128-019-2171-3","article-title":"A quantum walk-assisted approximate algorithm for bounded NP optimisation problems","volume":"18","author":"Marsh","year":"2019","journal-title":"Quant. Inform. Process."},{"key":"ref_32","unstructured":"Lloyd, S. (2019, February 11). Quantum approximate optimization is computationally universal. Available online: https:\/\/arxiv.org\/pdf\/1812.11075.pdf."},{"key":"ref_33","unstructured":"Guerreschi, G.G., and Smelyanskiy, M. (2019, February 11). Practical optimization for hybrid quantum-classical algorithms. Available online: https:\/\/arxiv.org\/pdf\/1701.01450.pdf."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"McClean, J.R., Boixo, S., Smelyanskiy, V.N., Babbush, R., and Neven, H. (2019, February 11). Barren plateaus in quantum neural network training landscapes. Available online: https:\/\/arxiv.org\/pdf\/1803.11173.pdf.","DOI":"10.1038\/s41467-018-07090-4"},{"key":"ref_35","unstructured":"Booth, K.E.C., Do, M., Beck, J.C., Rieffel, E., Venturelli, D., and Frank, J. (2019, February 11). Comparing and integrating constraint programming and temporal planning for quantum circuit compilation. Available online: https:\/\/arxiv.org\/pdf\/1803.06775.pdf."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"012310","DOI":"10.1103\/PhysRevA.64.012310","article-title":"Encoding a qubit in an oscillator","volume":"64","author":"Gottesman","year":"2001","journal-title":"Phys. Rev. A"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"052316","DOI":"10.1103\/PhysRevA.65.052316","article-title":"Quantum encodings in spin systems and harmonic oscillators","volume":"65","author":"Bartlett","year":"2002","journal-title":"Phys. Rev. A"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"032316","DOI":"10.1103\/PhysRevA.79.032316","article-title":"Quantum circuits for strongly correlated quantum systems","volume":"79","author":"Verstraete","year":"2009","journal-title":"Phys. Rev. A"},{"key":"ref_39","unstructured":"Chow, J.M. (2010). Quantum Information Processing with Superconducting Qubits. [Ph.D. Thesis, Yale University]."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Soifer, A. (2008). The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators, Springer.","DOI":"10.1007\/978-0-387-74642-5"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"1293","DOI":"10.1137\/S0097539794266407","article-title":"On unapproximable versions of NP-complete problems","volume":"25","author":"Zuckerman","year":"1996","journal-title":"SIAM J. Comput."},{"key":"ref_42","unstructured":"Papadimitriou, C.H. (1994). Computational Complexity, John Wiley and Sons."},{"key":"ref_43","first-page":"1052","article-title":"Complexity and completeness of finding another solution and its application to puzzles","volume":"86","author":"Yato","year":"2003","journal-title":"IEICE Trans. Fund. Electron. Commun. Comput. Sci."},{"key":"ref_44","unstructured":"Ueda, N., and Nagao, T. (2017, August 30). NP-Completeness Results for NONOGRAM via Parsimonious Reductions. Available online: https:\/\/pdfs.semanticscholar.org\/1bb2\/3460c7f0462d95832bb876ec2ee0e5bc46cf.pdf."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Bremner, M.J., Jozsa, R., and Shepherd, D.J. (2010). Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. R. Soc. Lond. Math. Phys. Sci., 467.","DOI":"10.1098\/rspa.2010.0301"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Li, G., Ding, Y., and Xie, Y. (2019, February 11). Tackling the qubit mapping problem for NISQ-Era quantum devices. Available online: https:\/\/arxiv.org\/pdf\/1809.02573.pdf.","DOI":"10.1145\/3297858.3304023"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"080501","DOI":"10.1103\/PhysRevLett.117.080501","article-title":"Average-case complexity versus approximate simulation of commuting quantum computations","volume":"117","author":"Bremner","year":"2016","journal-title":"Phys. Rev. Lett."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"8","DOI":"10.22331\/q-2017-04-25-8","article-title":"Achieving quantum supremacy with sparse and noisy commuting quantum computations","volume":"1","author":"Bremner","year":"2017","journal-title":"Quantum"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Trevisan, L. (2014). Inapproximability of combinatorial optimization problems. Paradigms of Combinatorial Optimization, John Wiley and Sons. [2nd ed.].","DOI":"10.1002\/9781119005353.ch13"},{"key":"ref_50","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., and Protasi, M. (2012). Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","article-title":"Optimization, approximation, and complexity classes","volume":"43","author":"Papadimitriou","year":"1991","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1137\/S0097539795286612","article-title":"On syntactic versus computational views of approximability","volume":"28","author":"Khanna","year":"1998","journal-title":"SIAM J. Comput."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","article-title":"Some optimal inapproximability results","volume":"48","year":"2001","journal-title":"J. ACM"},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","article-title":"Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming","volume":"42","author":"Goemans","year":"1995","journal-title":"J. ACM"},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1137\/S0097539705447372","article-title":"Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?","volume":"37","author":"Khot","year":"2007","journal-title":"SIAM J. Comput."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/S0196-6774(02)00005-6","article-title":"Improved approximation of Max-Cut on graphs of bounded degree","volume":"43","author":"Feige","year":"2002","journal-title":"J. Algorithms"},{"key":"ref_57","doi-asserted-by":"crossref","unstructured":"Lewin, M., Livnat, D., and Zwick, U. (2002, January 27\u201329). Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems. Proceedings of the International Conference on Integer Programming and Combinatorial Optimization, Cambridge, MA, USA.","DOI":"10.1007\/3-540-47867-1_6"},{"key":"ref_58","unstructured":"Karloff, H., and Zwick, U. (1997, January 20\u201322). A 7\/8-approximation algorithm for MAX 3SAT?. Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Miami Beach, FL, USA."},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1137\/S0895480191220836","article-title":"The minimum satisfiability problem","volume":"7","author":"Kohli","year":"1994","journal-title":"SIAM J. Discrete Math."},{"key":"ref_60","doi-asserted-by":"crossref","unstructured":"Dinur, I., and Safra, S. (2002, January 19\u201321). The importance of being biased. Proceedings of the 34th Annual ACM Symposium on the Theory of Computing, Montreal, ON, Canada.","DOI":"10.1145\/509907.509915"},{"key":"ref_61","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/s00224-005-1140-7","article-title":"Approximating MIN 2-SAT and MIN 3-SAT","volume":"38","author":"Avidor","year":"2005","journal-title":"Theor. Comput. Syst."},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/S0167-6377(99)00010-3","article-title":"On dependent randomized rounding algorithms","volume":"24","author":"Bertsimas","year":"1999","journal-title":"Oper. Res. Lett."},{"key":"ref_63","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/S0020-0190(98)00021-0","article-title":"Better approximation algorithms for set splitting and Not-All-Equal SAT","volume":"65","author":"Andersson","year":"1998","journal-title":"Inform. Process. Lett."},{"key":"ref_64","unstructured":"Zwick, U. (1998, January 25\u201327). Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA."},{"key":"ref_65","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01202286","article-title":"The hardness of approximation: Gap location","volume":"4","author":"Petrank","year":"1994","journal-title":"Comput. Complex."},{"key":"ref_66","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/j.dam.2002.07.001","article-title":"Improved approximations for max set splitting and max NAE SAT","volume":"142","author":"Zhang","year":"2004","journal-title":"Discrete Appl. Math."},{"key":"ref_67","unstructured":"Lov\u00e1sz, L. (1973, January 5\u20138). Coverings and colorings of hypergraphs. Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, USA."},{"key":"ref_68","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s00453-003-1072-z","article-title":"Inapproximability results for set splitting and satisfiability problems with no mixed clauses","volume":"38","author":"Guruswami","year":"2004","journal-title":"Algorithmica"},{"key":"ref_69","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1016\/j.tcs.2005.03.007","article-title":"Completeness in standard and differential approximation classes: Poly-(D) APX-and (D) PTAS-completeness","volume":"339","author":"Bazgan","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"ref_70","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/BF01994876","article-title":"Approximating maximum independent sets by excluding subgraphs","volume":"32","author":"Boppana","year":"1992","journal-title":"BIT Numer. Math."},{"key":"ref_71","doi-asserted-by":"crossref","unstructured":"Zuckerman, D. (2006, January 21\u201323). Linear degree extractors and the inapproximability of max clique and chromatic number. Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, Seattle, WA, USA.","DOI":"10.1145\/1132516.1132612"},{"key":"ref_72","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1145\/1597036.1597045","article-title":"A better approximation ratio for the vertex cover problem","volume":"5","author":"Karakostas","year":"2009","journal-title":"ACM Trans. Algorithms"},{"key":"ref_73","doi-asserted-by":"crossref","first-page":"439","DOI":"10.4007\/annals.2005.162.439","article-title":"On the hardness of approximating minimum vertex cover","volume":"162","author":"Dinur","year":"2005","journal-title":"Ann. Math."},{"key":"ref_74","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0020-0190(96)00031-2","article-title":"On approximation algorithms for the minimum satisfiability problem","volume":"58","author":"Marathe","year":"1996","journal-title":"Inform. Process. Lett."},{"key":"ref_75","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1007\/s00037-006-0205-6","article-title":"On the complexity of approximating k-set packing","volume":"15","author":"Hazan","year":"2006","journal-title":"Comput. Complex."},{"key":"ref_76","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0166-218X(99)00124-9","article-title":"Independent sets with domination constraints","volume":"99","author":"Telle","year":"2000","journal-title":"Discrete Appl. Math."},{"key":"ref_77","unstructured":"Johnson, D.S. (May, January 30). Approximation algorithms for combinatorial problems. Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, Austin, TX, USA."},{"key":"ref_78","unstructured":"Dinur, I., and Steurer, D. (June, January 31). Analytical approach to parallel repetition. Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, New York, NY, USA."},{"key":"ref_79","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/BF02523688","article-title":"Improved approximation algorithms for MAXk-CUT and MAX BISECTION","volume":"18","author":"Frieze","year":"1997","journal-title":"Algorithmica"},{"key":"ref_80","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1137\/050640904","article-title":"A polylogarithmic approximation of the minimum bisection","volume":"48","author":"Krauthgamer","year":"2006","journal-title":"SIAM Rev."},{"key":"ref_81","doi-asserted-by":"crossref","unstructured":"Panconesi, A., and Ranjan, D. (1990, January 13\u201317). Quantifiers and approximation. Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA.","DOI":"10.1145\/100216.100275"},{"key":"ref_82","unstructured":"Halld\u00f3rsson, M.M. (1995, January 22\u201324). Approximating Discrete Collections via Local Improvements. Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA."},{"key":"ref_83","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","article-title":"A still better performance guarantee for approximate graph coloring","volume":"45","year":"1993","journal-title":"Inform. Process. Lett."},{"key":"ref_84","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1137\/0403035","article-title":"On the 1.1 edge-coloring of multigraphs","volume":"3","author":"Nishizeki","year":"1990","journal-title":"SIAM J. Discrete Math."},{"key":"ref_85","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","article-title":"On the hardness of approximating minimization problems","volume":"41","author":"Lund","year":"1994","journal-title":"J. ACM"},{"key":"ref_86","unstructured":"Orponen, P., and Mannila, H. (2017, August 30). On Approximation Preserving Reductions: Complete Problems and Robust Measures (Revised Version). Available online: https:\/\/pdfs.semanticscholar.org\/d7d4\/44112250080800b25794352814e4f42ae0b0.pdf."},{"key":"ref_87","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.18.1.1","article-title":"The traveling salesman problem with distances one and two","volume":"18","author":"Papadimitriou","year":"1993","journal-title":"Math. Oper. Res."},{"key":"ref_88","unstructured":"Christofides, N. (1976). Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem, Carnegie-Mellon Univ. Technical Report, Management Sciences Research Group."},{"key":"ref_89","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1016\/j.cor.2011.07.018","article-title":"Minimizing the weighted sum of squared tardiness on a single machine","volume":"39","author":"Schaller","year":"2012","journal-title":"Comput. Oper. Res."},{"key":"ref_90","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/j.ejor.2004.04.013","article-title":"Single machine scheduling to minimize total weighted tardiness","volume":"165","author":"Cheng","year":"2005","journal-title":"Eur. J. Oper. Res."},{"key":"ref_91","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","article-title":"Complexity of machine scheduling problems","volume":"1","author":"Lenstra","year":"1977","journal-title":"Ann. Discrete Math."},{"key":"ref_92","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1137\/S089548019936223X","article-title":"Single machine scheduling with release dates","volume":"15","author":"Goemans","year":"2002","journal-title":"SIAM J. Discrete Math."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/2\/34\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:31:30Z","timestamp":1760185890000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/2\/34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,12]]},"references-count":92,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2019,2]]}},"alternative-id":["a12020034"],"URL":"https:\/\/doi.org\/10.3390\/a12020034","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,12]]}}}