* Coons and Herbert 2018 Coons, M. P.; Herbert, J. M. Quantum chemistry in arbitrary dielectric environments: Theory and implementation of nonequilibrium Poisson boundary conditions and application to compute vertical ionization energies at the air/water interface. _J. Chem. Phys._ 2018, _148_ , 222834
  * Claudino and Mayhall 2019 Claudino, D.; Mayhall, N. J. Automatic Partition of Orbital Spaces Based on Singular Value Decomposition in the Context of Embedding Theories. _J. Chem. Theory Comput._ 2019, _15_ , 1053–1064
  * Cammi and Mennucci 1999 Cammi, R.; Mennucci, B. Linear response theory for the polarizable continuum model. _J. Chem. Phys._ 1999, _110_ , 9877–9886
  * Cossi and Barone 2001 Cossi, M.; Barone, V. Time-dependent density functional theory for molecules in liquid solutions. _J. Chem. Phys._ 2001, _115_ , 4708–4717
  * You et al. 2015 You, Z.-Q.; Mewes, J.-M.; Dreuw, A.; Herbert, J. M. Comparison of the Marcus and Pekar partitions in the context of non-equilibrium, polarizable-continuum solvation models. _J. Chem. Phys._ 2015, _143_ , 204104
  * Cammi and Tomasi 1995 Cammi, R.; Tomasi, J. Nonequilibrium solvation theory for the polarizable continuum model: A new formulation at the SCF level with application to the case of the frequency-dependent linear electric response function. _Int. J. Quantum Chem._ 1995, _56_ , 465–474
  * Cossi and Barone 2000 Cossi, M.; Barone, V. Separation between fast and slow polarizations in continuum solvation models. _J. Phys. Chem. A_ 2000, _104_ , 10614–10622
  * Improta et al. 2006 Improta, R.; Barone, V.; Scalmani, G.; Frisch, M. J. A state-specific polarizable continuum model time dependent density functional theory method for excited state calculations in solution. _J. Chem. Phys._ 2006, _125_ , 054103
  * Shao et al. 2015 Shao, Y.; Gan, Z.; Epifanovsky, E.; Gilbert, A. T. B.; Wormit, M.; Kussmann, J.; Lange, A. W.; Behn, A.; Deng, J.; Feng, X. et al. Advances in molecular quantum chemistry contained in the Q-Chem 4 program package. _Mol. Phys._ 2015, _113_ , 184–215
  * Chipman and Dupuis 2002 Chipman, D. M.; Dupuis, M. Implementation of solvent reaction fields for electronic structure. _Theor. Chem. Acc._ 2002, _107_ , 90–102
  * Mewes et al. 2017 Mewes, J.-M.; Herbert, J. M.; Dreuw, A. On the accuracy of the general, state-specific polarizable-continuum model for the description of correlated ground- and excited states in solution. _Phys. Chem. Chem. Phys._ 2017, _19_ , 1644–1654
  * Lange and Herbert 2011 Lange, A. W.; Herbert, J. M. A simple polarizable continuum solvation model for electrolyte solutions. _J. Chem. Phys._ 2011, _134_ , 204110
  * Blum et al. 2009 Blum, V.; Gehrke, R.; Hanke, F.; Havu, P.; Havu, V.; Ren, X.; Reuter, K.; Scheffler, M. Ab initio molecular simulations with numeric atom-centered orbitals. _Comput. Phys. Commun._ 2009, _180_ , 2175–2196
  * Dovesi et al. 2018 Dovesi, R.; Erba, A.; Orlando, R.; Zicovich-Wilson, C. M.; Civalleri, B.; Maschio, L.; Rérat, M.; Casassa, S.; Baima, J.; Salustro, S. et al. Quantum-mechanical condensed matter simulations with CRYSTAL. _Wiley Interdiscip. Rev. Comput. Mol. Sci._ 2018, _8_ , e1360
  * R. Dovesi, V. R. Saunders, C. Roetti, R. Orlando, C. M. Zicovich-Wilson, F. Pascale, B. Civalleri, K. Doll, N. M. Harrison, I. J. Bush, P. D’Arco, M. Llunell, M. Causà, Y. Noël, L. Maschio, A. Erba, M. Rerat and S. Casassa 2017 R. Dovesi, V. R. Saunders, C. Roetti, R. Orlando, C. M. Zicovich-Wilson, F. Pascale, B. Civalleri, K. Doll, N. M. Harrison, I. J. Bush, P. D’Arco, M. Llunell, M. Causà, Y. Noël, L. Maschio, A. Erba, M. Rerat and S. Casassa, CRYSTAL17 User’s Manual. University of Torino, Torino, 2017
  * Vassetti and Labat 2021 Vassetti, D.; Labat, F. Evaluation of the performances of different atomic charge and nonelectrostatic models in the finite-difference Poisson–Boltzmann approach. _Int. J. Quantum Chem._ 2021, _121_ , e26560
  * Bochevarov et al. 2013 Bochevarov, A. D.; Harder, E.; Hughes, T. F.; Greenwood, J. R.; Braden, D. A.; Philipp, D. M.; Rinaldo, D.; Halls, M. D.; Zhang, J.; Friesner, R. A. Jaguar: A high‐performance quantum chemistry software program with strengths in life and materials sciences. _Int. J. Quantum Chem._ 2013, _113_ , 2110–2142
  * Nicholls and Honig 1991 Nicholls, A.; Honig, B. A rapid finite difference algorithm, utilizing successive over-relaxation to solve the Poisson-Boltzmann equation. _J. Comput. Chem._ 1991, _12_ , 435–445
  * Tannor et al. 1994 Tannor, D. J.; Marten, B.; Murphy, R.; Friesner, R. A.; Sitkoff, D.; Nicholls, A.; Honig, B.; Ringnalda, M.; Goddard, W. A., III Accurate first principles calculation of molecular charge distributions and solvation energies from ab initio quantum mechanics and continuum dielectric theory. _J. Am. Chem. Soc._ 1994, _116_ , 11875–11882
  * Marten et al. 1996 Marten, B.; Kim, K.; Cortis, C.; Friesner, R. A.; Murphy, R. B.; Ringnalda, M. N.; Sitkoff, D.; Honig, B. New Model for Calculation of Solvation Free Energies: Correction of Self-Consistent Reaction Field Continuum Dielectric Theory for Short-Range Hydrogen-Bonding Effects. _J. Phys. Chem._ 1996, _100_ , 11775–11788
  * Kelly et al. 2005 Kelly, C. P.; Cramer, C. J.; Truhlar, D. G. SM6: A Density Functional Theory Continuum Solvation Model for Calculating Aqueous Solvation Free Energies of Neutrals, Ions, and Solute-Water Clusters. _J. Chem. Theory Comput._ 2005, _1_ , 1133–1152
  * Si and Li 2009 Si, D.; Li, H. Heterogeneous conductorlike solvation model. _J. Chem. Phys._ 2009, _131_ , 044123
  * Barca et al. 2020 Barca, G. M. J.; Bertoni, C.; Carrington, L.; Datta, D.; De Silva, N.; Deustua, J. E.; Fedorov, D. G.; Gour, J. R.; Gunina, A. O.; Guidez, E. et al. Recent developments in the general atomic and molecular electronic structure system. _J. Chem. Phys._ 2020, _152_ , 154102
  * Cancès et al. 1997 Cancès, E.; Mennucci, B.; Tomasi, J. A new integral equation formalism for the polarizable continuum model: Theoretical background and applications to isotropic and anisotropic dielectrics. _J. Chem. Phys._ 1997, _107_ , 3032–3041
  * Cancès and Mennucci 1998 Cancès, E.; Mennucci, B. New applications of integral equations methods for solvation continuum models: ionic solutions and liquid crystals. _J. Math. Chem._ 1998, _23_ , 309–326
  * Minezawa et al. 2011 Minezawa, N.; De Silva, N.; Zahariev, F.; Gordon, M. S. Implementation of the analytic energy gradient for the combined time-dependent density functional theory/effective fragment potential method: application to excited-state molecular dynamics simulations. _J. Chem. Phys._ 2011, _134_ , 054111
  * Si and Li 2010 Si, D.; Li, H. Analytic energy gradient in combined time-dependent density functional theory and polarizable force field calculation. _J. Chem. Phys._ 2010, _133_ , 144112
  * Wang and Li 2010 Wang, Y.; Li, H. Excited state geometry of photoactive yellow protein chromophore: a combined conductorlike polarizable continuum model and time-dependent density functional study. _J. Chem. Phys._ 2010, _133_ , 034108
  * Yoo et al. 2008 Yoo, S.; Zahariev, F.; Sok, S.; Gordon, M. S. Solvent effects on optical properties of molecules: a combined time-dependent density functional theory/effective fragment potential approach. _J. Chem. Phys._ 2008, _129_ , 144112
  * Cossi et al. 1998 Cossi, M.; Barone, V.; Mennucci, B.; Tomasi, J. Ab initio study of ionic solutions by a polarizable continuum dielectric model. _Chem. Phys. Lett._ 1998, _286_ , 253–260
  * Frisch et al. 2016 Frisch, M. J.; Trucks, G. W.; Schlegel, H. B.; Scuseria, G. E.; Robb, M. A.; Cheeseman, J. R.; Scalmani, G.; Barone, V.; Petersson, G. A.; Nakatsuji, H. et al. Gaussian˜16 Revision C.01. 2016
  * Mennucci and Cammi 2003 Mennucci, B.; Cammi, R. Ab initio model to predict NMR shielding tensors for solutes in liquid crystals. _Int. J. Quantum Chem._ 2003, _93_ , 121–130
  * Fukuda et al. 2011 Fukuda, R.; Ehara, M.; Nakatsuji, H.; Cammi, R. Nonequilibrium solvation for vertical photoemission and photoabsorption processes using the symmetry-adapted cluster-configuration interaction method in the polarizable continuum model. _J. Chem. Phys._ 2011, _134_ , 104109
  * Cammi et al. 2000 Cammi, R.; Mennucci, B.; Tomasi, J. Fast evaluation of geometries and properties of excited molecules in solution: A Tamm-dancoff model with application to 4-dimethylaminobenzonitrile. _J. Phys. Chem. A_ 2000, _104_ , 5631–5637
  * Scalmani et al. 2006 Scalmani, G.; Frisch, M. J.; Mennucci, B.; Tomasi, J.; Cammi, R.; Barone, V. Geometries and properties of excited states in the gas phase and in solution: theory and application of a time-dependent density functional theory polarizable continuum model. _J. Chem. Phys._ 2006, _124_ , 94107
  * 284 TURBOMOLE V7.2 2017, a development of University of Karlsruhe and Forschungszentrum Karlsruhe GmbH, 1989-2007, TURBOMOLE GmbH, since 2007; available from http://www.turbomole.com
  * Klamt et al. 2015 Klamt, A.; Moya, C.; Palomar, J. A comprehensive comparison of the IEFPCM and SS (V) PE continuum solvation methods with the COSMO approach. _J. Chem. Theory Comput._ 2015, _11_ , 4220–4225
  * Schäfer et al. 2000 Schäfer, A.; Klamt, A.; Sattel, D.; Lohrenz, J. C. W.; Eckert, F. COSMO Implementation in TURBOMOLE: Extension of an efficient quantum chemical code towards liquid systems. _Phys. Chem. Chem. Phys._ 2000, _2_ , 2187–2193
  * Klamt 1996 Klamt, A. Calculation of UV/Vis spectra in solution. _J. Phys. Chem._ 1996, _100_ , 3349–3353
  * Aprà et al. 2020 Aprà, E.; Bylaska, E. J.; de Jong, W. A.; Govind, N.; Kowalski, K.; Straatsma, T. P.; Valiev, M.; van Dam, H. J. J.; Alexeev, Y.; Anchell, J. et al. NWChem: Past, present, and future. _J. Chem. Phys._ 2020, _152_ , 184102
  * York and Karplus 1999 York, D. M.; Karplus, M. A smooth solvation potential based on the conductor-like screening model. _J. Phys. Chem. A_ 1999, _103_ , 11060–11079
  * Mathew et al. 2014 Mathew, K.; Sundararaman, R.; Letchworth-Weaver, K.; Arias, T. A.; Hennig, R. G. Implicit solvation model for density-functional study of nanocrystal surfaces and reaction pathways. _J. Chem. Phys._ 2014, _140_ , 084106
  * Kresse and Furthmüller 1996 Kresse, G.; Furthmüller, J. Efficient iterative schemes for ab initio total-energy calculations using a plane-wave basis set. _Phys. Rev. B_ 1996, _54_ , 11169–11186
  * Garrity et al. 2014 Garrity, K. F.; Bennett, J. W.; Rabe, K. M.; Vanderbilt, D. Pseudopotentials for high-throughput DFT calculations. _Comput. Mater. Sci._ 2014, _81_ , 446–452
  * Giannozzi et al. 2009 Giannozzi, P.; Baroni, S.; Bonini, N.; Calandra, M.; Car, R.; Cavazzoni, C.; Ceresoli, D.; Chiarotti, G. L.; Cococcioni, M.; Dabo, I. et al. QUANTUM ESPRESSO: a modular and open-source software project for quantum simulations of materials. _J. Phys. Condens. Matter_ 2009, _21_ , 395502
  * Giannozzi et al. 2020 Giannozzi, P.; Baseggio, O.; Bonfà, P.; Brunato, D.; Car, R.; Carnimeo, I.; Cavazzoni, C.; de Gironcoli, S.; Delugas, P.; Ferrari Ruffino, F. et al. Quantum ESPRESSO toward the exascale. _J. Chem. Phys._ 2020, _152_ , 154105
  * Giannozzi et al. 2017 Giannozzi, P.; Andreussi, O.; Brumme, T.; Bunau, O.; Buongiorno Nardelli, M.; Calandra, M.; Car, R.; Cavazzoni, C.; Ceresoli, D.; Cococcioni, M. et al. Advanced capabilities for materials modelling with Quantum ESPRESSO. _J. Phys. Condens. Matter_ 2017, _29_ , 465901
  * Dawson et al. 2020 Dawson, W.; Mohr, S.; Ratcliff, L. E.; Nakajima, T.; Genovese, L. Complexity Reduction in Density Functional Theory Calculations of Large Systems: System Partitioning and Fragment Embedding. _J. Chem. Theory Comput._ 2020, _16_ , 2952–2964
  * Mohr et al. 2015 Mohr, S.; Ratcliff, L. E.; Genovese, L.; Caliste, D.; Boulanger, P.; Goedecker, S.; Deutsch, T. Accurate and efficient linear scaling DFT calculations with universal applicability. _Phys. Chem. Chem. Phys._ 2015, _17_ , 31360–31370
  * Mohr et al. 2014 Mohr, S.; Ratcliff, L. E.; Boulanger, P.; Genovese, L.; Caliste, D.; Deutsch, T.; Goedecker, S. Daubechies wavelets for linear scaling density functional theory. _J. Chem. Phys._ 2014, _140_ , 204110
  * Genovese et al. 2008 Genovese, L.; Neelov, A.; Goedecker, S.; Deutsch, T.; Ghasemi, S. A.; Willand, A.; Caliste, D.; Zilberberg, O.; Rayson, M.; Bergman, A. et al. Daubechies wavelets as a basis set for density functional pseudopotential calculations. _J. Chem. Phys._ 2008, _129_ , 014109
  * Ratcliff et al. 2020 Ratcliff, L. E.; Dawson, W.; Fisicaro, G.; Caliste, D.; Mohr, S.; Degomme, A.; Videau, B.; Cristiglio, V.; Stella, M.; D’Alessandro, M. et al. Flexibilities of wavelets as a computational basis set for large-scale electronic structure calculations. _J. Chem. Phys._ 2020, _152_ , 194110
  * Fisicaro et al. 2020 Fisicaro, G.; Filice, S.; Scalese, S.; Compagnini, G.; Reitano, R.; Genovese, L.; Goedecker, S.; Deretzis, I.; La Magna, A. Wet Environment Effects for Ethanol and Water Adsorption on Anatase TiO2 (101) Surfaces. _J. Phys. Chem. C_ 2020, _124_ , 2406–2419
  * Held and Walter 2014 Held, A.; Walter, M. Simplified continuum solvent model with a smooth cavity based on volumetric data. _J. Chem. Phys._ 2014, _141_ , 174108
  * Mortensen et al. 2005 Mortensen, J. J.; Hansen, L. B.; Jacobsen, K. W. Real-space grid implementation of the projector augmented wave method. _Phys. Rev. B_ 2005, _71_ , 035109
  * Enkovaara et al. 2010 Enkovaara, J.; Rostgaard, C.; Mortensen, J. J.; Chen, J.; Dułak, M.; Ferrighi, L.; Gavnholt, J.; Glinsvad, C.; Haikola, V.; Hansen, H. A. et al. Electronic structure calculations with GPAW: a real-space implementation of the projector augmented-wave method. _J. Phys. Condens. Matter_ 2010, _22_ , 253202
  * Otani and Sugino 2006 Otani, M.; Sugino, O. First-principles calculations of charged surfaces and interfaces: A plane-wave nonrepeated slab approach. _Phys. Rev. B_ 2006, _73_ , 115407
  * Jia et al. 2013 Jia, W.; Cao, Z.; Wang, L.; Fu, J.; Chi, X.; Gao, W.; Wang, L.-W. The analysis of a plane wave pseudopotential density functional theory code on a GPU machine. _Comput. Phys. Commun._ 2013, _184_ , 9–18
  * Jia et al. 2013 Jia, W.; Fu, J.; Cao, Z.; Wang, L.; Chi, X.; Gao, W.; Wang, L.-W. Fast plane wave density functional theory molecular dynamics calculations on multi-GPU machines. _J. Comput. Phys._ 2013, _251_ , 102–115
  * Gao and Wang 2020 Gao, G.; Wang, L.-W. Substantial potential effects on single-atom catalysts for the oxygen evolution reaction simulated via a fixed-potential method. _J. Catal._ 2020, _391_ , 530–538
  * Sundararaman et al. 2018 Sundararaman, R.; Letchworth-Weaver, K.; Schwarz, K. A. Improving accuracy of electrochemical capacitance and solvation energetics in first-principles calculations. _J. Chem. Phys._ 2018, _148_ , 144105
  * Petrosyan et al. 2007 Petrosyan, S. A.; Briere, J.-F.; Roundy, D.; Arias, T. A. Joint density-functional theory for electronic structure of solvated systems. _Phys. Rev. B_ 2007, _75_ , 205105
  * Sundararaman et al. 2017 Sundararaman, R.; Letchworth-Weaver, K.; Schwarz, K. A.; Gunceler, D.; Ozhabes, Y.; Arias, T. A. JDFTx: software for joint density-functional theory. _SoftwareX_ 2017, _6_ , 278–284
  * 312 JDFTx: fluid-dielectric-tensor. https://jdftx.org/CommandFluidDielectricTensor.html, Accessed: 2021-7-27
  * Letchworth-Weaver and Arias 2012 Letchworth-Weaver, K.; Arias, T. A. Joint density functional theory of the electrode-electrolyte interface: Application to fixed electrode potentials, interfacial capacitances, and potentials of zero charge. _Phys. Rev. B_ 2012, _86_ , 075140
  * Yin et al. 2017 Yin, W.-J.; Krack, M.; Li, X.; Chen, L.-Z.; Liu, L.-M. Periodic continuum solvation model integrated with first-principles calculations for solid surfaces. _Progress in Natural Science: Materials International_ 2017, _27_ , 283–288
  * Kühne et al. 2020 Kühne, T. D.; Iannuzzi, M.; Del Ben, M.; Rybkin, V. V.; Seewald, P.; Stein, F.; Laino, T.; Khaliullin, R. Z.; Schütt, O.; Schiffmann, F. et al. CP2K: An electronic structure and molecular dynamics software package - Quickstep: Efficient and accurate electronic structure calculations. _J. Chem. Phys._ 2020, _152_ , 194103
  * 316 ”http://www.archer.ac.uk/community/eCSE/eCSE07-06/eCSE07-06.php”, Accessed: 2021-7-27
  * 317 Dziedzic, J.; Womack, J. C.; Bhandari, A.; Bramley, G. ONETEP solvent and electrolyte model. https://www.onetep.org/pmwiki/uploads/Main/Documentation/ImplicitSolventDoc.pdf, Accessed: 2021-7-27
  * Prentice et al. 2020 Prentice, J. C. A.; Aarons, J.; Womack, J. C.; Allen, A. E. A.; Andrinopoulos, L.; Anton, L.; Bell, R. A.; Bhandari, A.; Bramley, G. A.; Charlton, R. J. et al. The ONETEP linear-scaling density functional theory program. _J. Chem. Phys._ 2020, _152_ , 174111
  * Dziedzic et al. 2011 Dziedzic, J.; Helal, H. H.; Skylaris, C.-K.; Mostofi, A. A.; Payne, M. C. Minimal parameter implicit solvent model for ab initio electronic-structure calculations. 2011
  * Bhandari et al. 2020 Bhandari, A.; Anton, L.; Dziedzic, J.; Peng, C.; Kramer, D.; Skylaris, C.-K. Electronic structure calculations in electrolyte solutions: Methods for neutralization of extended charged interfaces. _J. Chem. Phys._ 2020, _153_ , 124101
  * Dziedzic et al. 2020 Dziedzic, J.; Bhandari, A.; Anton, L.; Peng, C.; Womack, J. C.; Famili, M.; Kramer, D.; Skylaris, C.-K. Practical Approach to Large-Scale Electronic Structure Calculations in Electrolyte Solutions via Continuum-Embedded Linear-Scaling Density Functional Theory. _J. Phys. Chem. C_ 2020, _124_ , 7860–7872
  * Clark et al. 2005 Clark, S. J.; Segall, M. D.; Pickard, C. J.; Hasnip, P. J.; Probert, M. I. J.; Refson, K.; Payne, M. C. First principles methods using CASTEP. _Z. Kristallogr. Cryst. Mater._ 2005, _220_ , 567–570
  * Carnahan and Starling 1969 Carnahan, N. F.; Starling, K. E. Equation of State for Nonattracting Rigid Spheres. _J. Chem. Phys._ 1969, _51_ , 635–636
  * Schmickler and Santos 2010 Schmickler, W.; Santos, E. _Interfacial Electrochemistry_ , 2nd ed.; Springer Berlin Heidelberg: Berlin, Heidelberg, 2010; pp XII, 270 S.
  * Choi et al. 2021 Choi, C.; Gu, G. H.; Noh, J.; Park, H. S.; Jung, Y. Understanding potential-dependent competition between electrocatalytic dinitrogen and proton reduction reactions. _Nat. Commun._ 2021, _12_ , 4353
  * Van den Bossche et al. 2019 Van den Bossche, M.; Skúlason, E.; Rose-Petruck, C.; Jónsson, H. Assessment of Constant-Potential Implicit Solvation Calculations of Electrochemical Energy Barriers for H2 Evolution on Pt. _J. Phys. Chem. C_ 2019, _123_ , 4116–4124
  * Ping et al. 2015 Ping, Y.; Sundararaman, R.; Goddard, W. A., 3rd Solvation effects on the band edge positions of photocatalysts from first principles. _Phys. Chem. Chem. Phys._ 2015, _17_ , 30499–30509
  * Blumenthal et al. 2017 Blumenthal, L.; Kahk, J. M.; Sundararaman, R.; Tangney, P.; Lischner, J. Energy level alignment at semiconductor–water interfaces from atomistic and continuum solvation models. _RSC Adv._ 2017, _7_ , 43660–43670
  * Hörmann et al. 2019 Hörmann, N. G.; Guo, Z.; Ambrosio, F.; Andreussi, O.; Pasquarello, A.; Marzari, N. Absolute band alignment at semiconductor-water interfaces using explicit and implicit descriptions for liquid water. _Npj Comput. Mater._ 2019, _5_ , 1–6
  * Bhandari et al. 2021 Bhandari, A.; Peng, C.; Dziedzic, J.; Anton, L.; Owen, J. R.; Kramer, D.; Skylaris, C.-K. Electrochemistry from first-principles in the grand canonical ensemble. _J. Chem. Phys._ 2021, _155_ , 024114
  * Frumkin and Petrii 1975 Frumkin, A.; Petrii, O. Potentials of zero total and zero free charge of platinum group metals. _Electrochimica Acta_ 1975, _20_ , 347–359
  * Trasatti 1990 Trasatti, S. The “absolute” electrode potential—the end of the story. _Electrochim. Acta_ 1990, _35_ , 269–271
  * Trasatti 1991 Trasatti, S. Structure of the metal/electrolyte solution interface: new data for theory. _Electrochim. Acta_ 1991, _36_ , 1659–1667
  * Leung 2010 Leung, K. Surface Potential at the Air–Water Interface Computed Using Density Functional Theory. _J. Phys. Chem. Lett._ 2010, _1_ , 496–499
  * Ambrosio et al. 2018 Ambrosio, F.; Guo, Z.; Pasquarello, A. Absolute Energy Levels of Liquid Water. _J. Phys. Chem. Lett._ 2018, _9_ , 3212–3216
  * Haruyama et al. 2018 Haruyama, J.; Ikeshoji, T.; Otani, M. Electrode potential from density functional theory calculations combined with implicit solvation theory. _Phys. Rev. Mater._ 2018, _2_ , 095801
  * Bramley et al. 2020 Bramley, G.; Nguyen, M.-T.; Glezakou, V.-A.; Rousseau, R.; Skylaris, C.-K. Reconciling Work Functions and Adsorption Enthalpies for Implicit Solvent Models: A Pt (111)/Water Interface Case Study. _J. Chem. Theory Comput._ 2020, _16_ , 2703–2715
  * Bockris et al. 1969 Bockris, J. O.; Argade, S. D.; Gileadi, E. The determination of the potential of zero charge on solid metals. _Electrochim. Acta_ 1969, _14_ , 1259–1283
  * White et al. 1999 White, R. E., Bockris, J. O., Conway, B. E., Eds. _Modern Aspects of Electrochemistry_ , 1st ed.; Modern Aspects of Electrochemistry; Springer US, 1999; Vol. 33
  * Climent et al. 1999 Climent, V.; Gómez, R.; Feliu, J. M. Effect of increasing amount of steps on the potential of zero total charge of Pt(111) electrodes. _Electrochim. Acta_ 1999, _45_ , 629–637
  * Fang et al. 2013 Fang, Y.-H.; Wei, G.-F.; Liu, Z.-P. Theoretical modeling of electrode/electrolyte interface from first-principles periodic continuum solvation method. _Catal. Today_ 2013, _202_ , 98–104
  * Kastlunger et al. 2018 Kastlunger, G.; Lindgren, P.; Peterson, A. A. Controlled-Potential Simulation of Elementary Electrochemical Reactions: Proton Discharge on Metal Surfaces. _J. Phys. Chem. C_ 2018, _122_ , 12771–12781
  * Wasileski and Janik 2008 Wasileski, S. A.; Janik, M. J. A first-principles study of molecular oxygen dissociation at an electrode surface: a comparison of potential variation and coadsorption effects. _Phys. Chem. Chem. Phys._ 2008, _10_ , 3613–3627
  * Schnur and Groß 2011 Schnur, S.; Groß, A. Challenges in the first-principles description of reactions in electrocatalysis. _Catal. Today_ 2011, _165_ , 129–137
  * Frumkin et al. 1980 Frumkin, A. N.; Petrii, O. A.; Damaskin, B. B. In _Comprehensive Treatise of Electrochemistry: The Double Layer_ ; Bockris, J. O., Conway, B. E., Yeager, E., Eds.; Springer US: Boston, MA, 1980; pp 221–289
  * Bell and Hinshelwood 1936 Bell, R. P.; Hinshelwood, C. N. The theory of reactions involving proton transfers. _Proceedings of the Royal Society of London. Series A - Mathematical and Physical Sciences_ 1936, _154_ , 414–429
  * Brønsted and Pedersen 1924 Brønsted, J. N.; Pedersen, K. J. Stöchiometrie und verwandtschaftslehre. _Z. Phys. Chem._ 1924, _108_ , 185–235
  * Evans and Polanyi 1936 Evans, M. G.; Polanyi, M. Further considerations on the thermodynamics of chemical equilibria and reaction rates. _Transactions of the Faraday Society_ 1936, _32_ , 1333
  * Lorenz and Sallé 1962 Lorenz, W.; Sallé, G. Zum Mechanismus der elektrochemischen Phasengrenzreaktion. _Z. Phys. Chem._ 1962, _218O_ , 259–271
  * Vetter and Schultze 1972 Vetter, K. J.; Schultze, J. W. Potentialabhängigkeit von Elektrosorptionsgleichgewichten und die Elektrosorptionswertigkeit $\gamma$. _Ber. Bunsenges. Phys. Chem._ 1972, _76_ , 920–927
  * Vetter and Schultze 1972 Vetter, K. J.; Schultze, J. W. Stromfluß bei Elektrosorptionsprozessen und Elektrosorptionswertigkeit $\gamma$. _Ber. Bunsenges. Phys. Chem._ 1972, _76_ , 927–933
  * Schultze and Vetter 1973 Schultze, J. W.; Vetter, K. J. Experimental determination and interpretation of the electrosorption valency $\gamma$. _J. Electroanal. Chem. Interfacial Electrochem._ 1973, _44_ , 63–81
  * Frumkin et al. 1974 Frumkin, A.; Damaskin, B.; Petrii, O. On the charge transfer in the process of adsorption at the electrode/solution interface. _J. Electroanal. Chem. Interfacial Electrochem._ 1974, _53_ , 57–65
  * Vetter and Schultze 1974 Vetter, K. J.; Schultze, J. W. General aspects of the electrosorption valency thermodynamic problems and nonthermodynamic analysis: Discussion of the paper by A. Frumkin, B. Damaskin and O. Petrii. _J. Electroanal. Chem. Interfacial Electrochem._ 1974, _53_ , 67–76
  * Lorenz and Salié 1977 Lorenz, W.; Salié, G. Partial charge transfer reactions in electrochemical kinetics: Review on the theory of measuring methods for electrode processes with adsorbed intermediates. _J. Electroanal. Chem. Interfacial Electrochem._ 1977, _80_ , 1–56
  * Valette et al. 1978 Valette, G.; Hamelin, A.; Parsons, R. Specific Adsorption on Silver Single Crystals in Aqueous Solutions. _Z. Phys. Chem._ 1978, _113_ , 71–89
  * Foresti et al. 1998 Foresti, M. L.; Innocenti, M.; Forni, F.; Guidelli, R. Electrosorption Valency and Partial Charge Transfer in Halide and Sulfide Adsorption on Ag(111). _Langmuir_ 1998, _14_ , 7008–7016
  * Habib and Bockris 1980 Habib, M. A.; Bockris, J. O. In _Comprehensive Treatise of Electrochemistry: The Double Layer_ ; Bockris, J. O., Conway, B. E., Yeager, E., Eds.; Comprehensive Treatise of Electrochemistry; Springer US: Boston, MA, 1980; Vol. 1; pp 135–219
  * Trasatti and Parsons 1983 Trasatti, S.; Parsons, R. Interphases in systems of conducting phases (Provisional). _J. Macromol. Sci. Part A Pure Appl. Chem._ 1983, _55_ , 1251–1268
  * de Levie 2004 de Levie, R. The electrosorption valency and partial charge transfer. _J. Electroanal. Chem._ 2004, _562_ , 273–276
  * Guidelli and Schmickler 2005 Guidelli, R.; Schmickler, W. In _Modern Aspects of Electrochemistry_ ; Conway, B. E., Vayenas, C. G., White, R. E., Gamboa-Adelco, M. E., Eds.; Springer US: Boston, MA, 2005; pp 303–371
  * Schmickler and Guidelli 1987 Schmickler, W.; Guidelli, R. Ionic adsorption and the surface dipole potential. _J. Electroanal. Chem. Interfacial Electrochem._ 1987, _235_ , 387–392
  * Schmickler 1988 Schmickler, W. The surface dipole moment of species adsorbed from a solution. _J. Electroanal. Chem. Interfacial Electrochem._ 1988, _249_ , 25–33
  * Schmickler and Guidelli 2014 Schmickler, W.; Guidelli, R. The partial charge transfer. _Electrochim. Acta_ 2014, _127_ , 489–505
  * Hörmann et al. 2020 Hörmann, N. G.; Marzari, N.; Reuter, K. Electrosorption at metal surfaces from first principles. _Npj Comput. Mater_ 2020, _6_ , 1–10
  * Hörmann and Reuter 2021 Hörmann, N. G.; Reuter, K. Thermodynamic Cyclic Voltammograms Based on Ab Initio Calculations: Ag(111) in Halide-Containing Solutions. _J. Chem. Theory Comput._ 2021, _17_ , 1782–1794
  * Hörmann and Reuter 2021 Hörmann, N. G.; Reuter, K. Thermodynamic cyclic voltammograms: peak positions and shapes. _J. Phys. Condens. Matter_ 2021, _33_ , 264004
  * Cheng et al. 2009 Cheng, J.; Sulpizi, M.; Sprik, M. Redox potentials and pKa for benzoquinone from density functional theory based molecular dynamics. _J. Chem. Phys._ 2009, _131_ , 154504
  * Cheng and Sprik 2010 Cheng, J.; Sprik, M. Aligning electronic energy levels at theTiO2/H2Ointerface. _Phys. Rev. B_ 2010, _82_ , 081406
  * Cheng et al. 2014 Cheng, J.; Liu, X.; VandeVondele, J.; Sulpizi, M.; Sprik, M. Redox potentials and acidity constants from density functional theory based molecular dynamics. _Acc. Chem. Res._ 2014, _47_ , 3522–3529
  * Hammes-Schiffer 2010 Hammes-Schiffer, S. Introduction: Proton-Coupled Electron Transfer. _Chem. Rev._ 2010, _110_ , 6937–6938
  * Sakaushi et al. 2020 Sakaushi, K.; Kumeda, T.; Hammes-Schiffer, S.; Melander, M. M.; Sugino, O. Advances and challenges for experiment and theory for multi-electron multi-proton transfer at electrified solid–liquid interfaces. _Phys. Chem. Chem. Phys._ 2020, _22_ , 19401–19442
  * Nørskov et al. 2004 Nørskov, J. K.; Rossmeisl, J.; Logadottir, A.; Lindqvist, L.; Kitchin, J. R.; Bligaard, T.; Jónsson, H. Origin of the Overpotential for Oxygen Reduction at a Fuel-Cell Cathode. _J. Phys. Chem. B_ 2004, _108_ , 17886–17892
  * Rossmeisl et al. 2005 Rossmeisl, J.; Logadottir, A.; Nørskov, J. K. Electrolysis of water on (oxidized) metal surfaces. _Chem. Phys._ 2005, _319_ , 178–184
  * Rogal and Reuter 2007 Rogal, J.; Reuter, K. Ab Initio Atomistic Thermodynamics for Surfaces: A Primer. Experiment, Modeling and Simulation of Gas- Surface Interactions for Reactive Flows in Hypersonic Flights. 2007; pp (pp. 2–1 – 2–18). Educational Notes RTO–EN–AVT–142, Paper 2. Neuilly–sur–Seine
  * Todorova and Neugebauer 2014 Todorova, M.; Neugebauer, J. Extending the Concept of Defect Chemistry from Semiconductor Physics to Electrochemistry. _Phys. Rev. Applied_ 2014, _1_ , 014001
  * Griesser et al. 2021 Griesser, C.; Li, H.; Wernig, E.-M.; Winkler, D.; Shakibi Nia, N.; Mairegger, T.; Götsch, T.; Schachinger, T.; Steiger-Thirsfeld, A.; Penner, S. et al. True Nature of the Transition-Metal Carbide/Liquid Interface Determines Its Reactivity. _ACS Catal._ 2021, _11_ , 4920–4928
  * McCrum et al. 2017 McCrum, I. T.; Hickner, M. A.; Janik, M. J. First-Principles Calculation of Pt Surface Energies in an Electrochemical Environment: Thermodynamic Driving Forces for Surface Faceting and Nanoparticle Reconstruction. _Langmuir_ 2017, _33_ , 7043–7052
  * Calle-Vallejo and Koper 2012 Calle-Vallejo, F.; Koper, M. T. M. First-principles computational electrochemistry: Achievements and challenges. _Electrochim. Acta_ 2012, _84_ , 3–11
  * McCrum et al. 2015 McCrum, I. T.; Akhade, S. A.; Janik, M. J. Electrochemical specific adsorption of halides on Cu 111, 100, and 211: A Density Functional Theory study. _Electrochim. Acta_ 2015, _173_ , 302–309
  * Hörmann et al. 2015 Hörmann, N. G.; Jäckle, M.; Gossenberger, F.; Roman, T.; Forster-Tonigold, K.; Naderian, M.; Sakong, S.; Groß, A. Some challenges in the first-principles modeling of structures and processes in electrochemical energy storage and transfer. _J. Power Sources_ 2015, _275_ , 531–538
  * Lespes and Filhol 2015 Lespes, N.; Filhol, J.-S. Using Implicit Solvent in Ab Initio Electrochemical Modeling: Investigating Li+/Li Electrochemistry at a Li/Solvent Interface. _J. Chem. Theory Comput._ 2015, _11_ , 3375–3382
  * Rossmeisl et al. 2006 Rossmeisl, J.; Nørskov, J. K.; Taylor, C. D.; Janik, M. J.; Neurock, M. Calculated phase diagrams for the electrochemical oxidation and reduction of water over Pt(111). _J. Phys. Chem. B_ 2006, _110_ , 21833–21839
  * Hansen et al. 2008 Hansen, H. A.; Rossmeisl, J.; Nørskov, J. K. Surface Pourbaix diagrams and oxygen reduction activity of Pt, Ag and Ni(111) surfaces studied by DFT. _Phys. Chem. Chem. Phys._ 2008, _10_ , 3722–3730
  * Hörmann and Groß 2014 Hörmann, N.; Groß, A. Stability, composition and properties of Li2FeSiO4 surfaces studied by DFT. _J. Solid State Electrochem._ 2014, _18_ , 1401–1413
  * Gossenberger et al. 2015 Gossenberger, F.; Roman, T.; Groß, A. Equilibrium coverage of halides on metal electrodes. _Surf. Sci._ 2015, _631_ , 17 – 22
  * Opalka et al. 2019 Opalka, D.; Scheurer, C.; Reuter, K. Ab Initio Thermodynamics Insight into the Structural Evolution of Working IrO2 Catalysts in Proton-Exchange Membrane Electrolyzers. _ACS Catal._ 2019, _9_ , 4944–4950
  * Nørskov et al. 2009 Nørskov, J. K.; Bligaard, T.; Rossmeisl, J.; Christensen, C. H. Towards the computational design of solid catalysts. _Nat. Chem._ 2009, _1_ , 37–46
  * Rossmeisl et al. 2008 Rossmeisl, J.; Greeley, J.; Karlberg, G. _Fuel Cell Catalysis_ ; John Wiley & Sons, Ltd, 2008; Chapter 3, pp 57–92
  * Sakong and Groß 2016 Sakong, S.; Groß, A. The Importance of the Electrochemical Environment in the Electro-Oxidation of Methanol on Pt(111). _ACS Catal._ 2016, _6_ , 5575–5586
  * Li and Reuter 2020 Li, H.; Reuter, K. Active-Site Computational Screening: Role of Structural and Compositional Diversity for the Electrochemical CO2 Reduction at Mo Carbide Catalysts. _ACS Catal._ 2020, _10_ , 11814–11821
  * Zeng et al. 2015 Zeng, Z.; Chan, M. K. Y.; Zhao, Z.-J.; Kubal, J.; Fan, D.; Greeley, J. Towards First Principles-Based Prediction of Highly Accurate Electrochemical Pourbaix Diagrams. _J. Phys. Chem. C_ 2015, _119_ , 18177–18187
  * Bagger et al. 2020 Bagger, A.; Castelli, I. E.; Hansen, M. H.; Rossmeisl, J. In _Handbook of Materials Modeling: Applications: Current and Emerging Materials_ ; Andreoni, W., Yip, S., Eds.; Springer International Publishing: Cham, 2020; pp 1473–1503
  * Abidi et al. 2021 Abidi, N.; Lim, K. R. G.; Seh, Z. W.; Steinmann, S. N. Atomistic modeling of electrocatalysis: Are we there yet? _Wiley Interdiscip. Rev. Comput. Mol. Sci._ 2021, _11_ , e1499
  * Iyemperumal and Deskins 2017 Iyemperumal, S. K.; Deskins, N. A. Evaluating Solvent Effects at the Aqueous/Pt(111) Interface. _Chemphyschem_ 2017, _18_ , 2171–2190
  * Gray et al. 2017 Gray, C. M.; Saravanan, K.; Wang, G.; Keith, J. A. Quantifying solvation energies at solid/liquid interfaces using continuum solvation methods. _Mol. Simul._ 2017, _43_ , 420–427
  * Zhang and Asthagiri 2019 Zhang, Q.; Asthagiri, A. Solvation effects on DFT predictions of ORR activity on metal surfaces. _Catal. Today_ 2019, _323_ , 35–43
  * Patel et al. 2018 Patel, A. M.; Ringe, S.; Siahrostami, S.; Bajdich, M.; Nørskov, J. K.; Kulkarni, A. R. Theoretical Approaches to Describing the Oxygen Reduction Reaction Activity of Single-Atom Catalysts. _J. Phys. Chem. C_ 2018, _122_ , 29307–29318
  * Karlberg 2006 Karlberg, G. S. Adsorption trends for water, hydroxyl, oxygen, and hydrogen on transition-metal and platinum-skin surfaces. _Phys. Rev. B_ 2006, _74_ , 153414
  * Park and Roling 2020 Park, J.; Roling, L. T. Elucidating energy scaling between atomic and molecular adsorbates in the presence of solvent. _AIChE J._ 2020, _66_ , e17036
  * Meng et al. 2004 Meng, S.; Wang, E. G.; Gao, S. Water adsorption on metal surfaces: A general picture from density functional theory studies. _Phys. Rev. B_ 2004, _69_ , 195404
  * Steinmann et al. 2016 Steinmann, S. N.; Sautet, P.; Michel, C. Solvation free energies for periodic surfaces: comparison of implicit and explicit solvation models. _Phys. Chem. Chem. Phys._ 2016, _18_ , 31850–31861
  * Kasuya et al. 2016 Kasuya, M.; Sogawa, T.; Masuda, T.; Kamijo, T.; Uosaki, K.; Kurihara, K. Anion Adsorption on Gold Electrodes Studied by Electrochemical Surface Forces Measurement. _J. Phys. Chem. C_ 2016, _120_ , 15986–15992
  * Pajkossy et al. 1996 Pajkossy, T.; Wandlowski, T.; Kolb, D. M. Impedance aspects of anion adsorption on gold single crystal electrodes. _J. Electroanal. Chem._ 1996, _414_ , 209–220
  * Valette 1982 Valette, G. Double layer on silver single crystal electrodes in contact with electrolytes having anions which are slightly specifically adsorbed: Part II. The (100) face. _J. Electroanal. Chem. Interfacial Electrochem._ 1982, _138_ , 37–54
  * Valette 1981 Valette, G. Double layer on silver single-crystal electrodes in contact with electrolytes having anions which present a slight specific adsorption: Part I. The (110) face. _J. Electroanal. Chem. Interfacial Electrochem._ 1981, _122_ , 285–297
  * Hu et al. 2017 Hu, Q.; Weber, C.; Cheng, H.-W.; Renner, F. U.; Valtiner, M. Anion Layering and Steric Hydration Repulsion on Positively Charged Surfaces in Aqueous Electrolytes. _Chemphyschem_ 2017, _18_ , 3056–3065
  * Cuesta et al. 2000 Cuesta, A.; Kleinert, M.; Kolb, D. M. The adsorption of sulfate and phosphate on Au(111) and Au(100) electrodes: an in situ STM study. _Phys. Chem. Chem. Phys._ 2000, _2_ , 5684–5690
  * Koga et al. 2001 Koga, O.; Watanabe, Y.; Tanizaki, M.; Hori, Y. Specific adsorption of anions on a copper (100) single crystal electrode studied by charge displacement by CO adsorption and infrared spectroscopy. _Electrochim. Acta_ 2001, _46_ , 3083–3090
  * Berná et al. 2007 Berná, A.; Climent, V.; Feliu, J. M. New understanding of the nature of OH adsorption on Pt(111) electrodes. _Electrochem. commun._ 2007, _9_ , 2789–2794
  * Kristoffersen et al. 2018 Kristoffersen, H. H.; Vegge, T.; Hansen, H. A. OH formation and H2 adsorption at the liquid water-Pt(111) interface. _Chem. Sci._ 2018, _9_ , 6912–6921
  * Rizo et al. 2015 Rizo, R.; Sitta, E.; Herrero, E.; Climent, V.; Feliu, J. M. Towards the understanding of the interfacial pH scale at Pt(111) electrodes. _Electrochim. Acta_ 2015, _162_ , 138–145
  * Tian et al. 2009 Tian, F.; Jinnouchi, R.; Anderson, A. B. How Potentials of Zero Charge and Potentials for Water Oxidation to OH(ads) on Pt(111) Electrodes Vary With Coverage. _J. Phys. Chem. C_ 2009, _113_ , 17484–17492
  * Gossenberger et al. 2014 Gossenberger, F.; Roman, T.; Forster-Tonigold, K.; Groß, A. Change of the work function of platinum electrodes induced by halide adsorption. _Beilstein J. Nanotechnol._ 2014, _5_ , 152–161
  * Lozovoi et al. 2001 Lozovoi, A. Y.; Alavi, A.; Kohanoff, J.; Lynden-Bell, R. M. Ab initio simulation of charged slabs at constant chemical potential. _J. Chem. Phys._ 2001, _115_ , 1661–1669
  * Taylor et al. 2006 Taylor, C. D.; Wasileski, S. A.; Filhol, J.-S.; Neurock, M. First principles reaction modeling of the electrochemical interface: Consideration and calculation of a tunable surface potential from atomic and electronic structure. _Phys. Rev. B_ 2006, _73_ , 165402
  * Mamatkulov and Filhol 2011 Mamatkulov, M.; Filhol, J.-S. An ab initio study of electrochemical vs. electromechanical properties: the case of CO adsorbed on a Pt(111) surface. _Phys. Chem. Chem. Phys._ 2011, _13_ , 7675–7684
  * Sundararaman et al. 2017 Sundararaman, R.; Figueiredo, M. C.; Koper, M. T. M.; Schwarz, K. A. Electrochemical Capacitance of CO-Terminated Pt(111) Dominated by the CO-Solvent Gap. _J. Phys. Chem. Lett._ 2017, _8_ , 5344–5348
  * Goodpaster et al. 2016 Goodpaster, J. D.; Bell, A. T.; Head-Gordon, M. Identification of Possible Pathways for C-C Bond Formation during Electrochemical Reduction of CO2: New Theoretical Insights from an Improved Electrochemical Model. _J. Phys. Chem. Lett._ 2016, _7_ , 1471–1477
  * Melander 2020 Melander, M. M. Grand Canonical Rate Theory for Electrochemical and Electrocatalytic Systems I: General Formulation and Proton-coupled Electron Transfer Reactions. _J. Electrochem. Soc._ 2020, _167_ , 116518
  * Bonnet et al. 2012 Bonnet, N.; Morishita, T.; Sugino, O.; Otani, M. First-principles molecular dynamics at a constant electrode potential. _Phys. Rev. Lett._ 2012, _109_ , 266101
  * Chan and Nørskov 2015 Chan, K.; Nørskov, J. K. Electrochemical Barriers Made Simple. _J. Phys. Chem. Lett._ 2015, _6_ , 2663–2668
  * Chan and Nørskov 2016 Chan, K.; Nørskov, J. K. Potential Dependence of Electrochemical Barriers from ab Initio Calculations. _J. Phys. Chem. Lett._ 2016, _7_ , 1686–1690
  * Vijay et al. 2020 Vijay, S.; Gauthier, J. A.; Heenen, H. H.; Bukas, V. J.; Kristoffersen, H. H.; Chan, K. Dipole-Field Interactions Determine the CO2 Reduction Activity of 2D Fe–N–C Single-Atom Catalysts. _ACS Catal._ 2020, _10_ , 7826–7835
  * Kim et al. 2021 Kim, D. H.; Ringe, S.; Kim, H.; Kim, S.; Kim, B.; Bae, G.; Oh, H.-S.; Jaouen, F.; Kim, W.; Kim, H. et al. Selective electrochemical reduction of nitric oxide to hydroxylamine by atomically dispersed iron catalyst. _Nat. Commun._ 2021, _12_ , 1–11
  * Lee et al. 2020 Lee, M.-Y.; Ringe, S.; Kim, H.; Kang, S.; Kwon, Y. Electric Field Mediated Selectivity Switching of Electrochemical CO2 Reduction from Formate to CO on Carbon Supported Sn. _ACS Energy Lett._ 2020, _5_ , 2987–2994
  * Wu et al. 2019 Wu, Y.; Ringe, S.; Wu, C.-L.; Chen, W.; Yang, A.; Chen, H.; Tang, M.; Zhou, G.; Hwang, H. Y.; Chan, K. et al. A Two-Dimensional MoS2 Catalysis Transistor by Solid-State Ion Gating Manipulation and Adjustment (SIGMA). _Nano Lett._ 2019, _19_ , 7293–7300
  * Liu et al. 2003 Liu, P.; Logadottir, A.; Nørskov, J. Modeling the electro-oxidation of CO and H2/CO on Pt, Ru, PtRu and Pt3Sn. _Electrochimica Acta_ 2003, _48_ , 3731–3742, Electrocatalysis:From Theory to Industrial Applications
  * Hyman and Medlin 2005 Hyman, M. P.; Medlin, J. W. Theoretical study of the adsorption and dissociation of oxygen on Pt(111) in the presence of homogeneous electric fields. _J. Phys. Chem. B_ 2005, _109_ , 6304–6310
  * Lamoureux et al. 2019 Lamoureux, P. S.; Singh, A. R.; Chan, K. pH Effects on Hydrogen Evolution and Oxidation over Pt(111): Insights from First-Principles. _ACS Catal._ 2019, _9_ , 6194–6201
  * Kelly et al. 2020 Kelly, S. R.; Kirk, C.; Chan, K.; Nørskov, J. K. Electric Field Effects in Oxygen Reduction Kinetics: Rationalizing pH Dependence at the Pt(111), Au(111), and Au(100) Electrodes. _J. Phys. Chem. C_ 2020, _124_ , 14581–14591
  * Deißenbeck et al. 2021 Deißenbeck, F.; Freysoldt, C.; Todorova, M.; Neugebauer, J.; Wippermann, S. Dielectric Properties of Nanoconfined Water: A Canonical Thermopotentiostat Approach. _Phys. Rev. Lett._ 2021, _126_ , 136803
  * Karlberg et al. 2007 Karlberg, G. S.; Rossmeisl, J.; Nørskov, J. K. Estimations of electric field effects on the oxygen reduction reaction based on the density functional theory. _Phys. Chem. Chem. Phys._ 2007, _9_ , 5158–5161
  * Panchenko et al. 2004 Panchenko, A.; Koper, M. T. M.; Shubina, T. E.; Mitchell, S. J.; Roduner, E. Ab Initio Calculations of Intermediates of Oxygen Reduction on Low-Index Platinum Surfaces. _J. Electrochem. Soc._ 2004, _151_ , A2016
  * Clark et al. 2019 Clark, E. L.; Ringe, S.; Tang, M.; Walton, A.; Hahn, C.; Jaramillo, T. F.; Chan, K.; Bell, A. T. Influence of Atomic Surface Structure on the Activity of Ag for the Electrochemical Reduction of CO2 to CO. _ACS Catal._ 2019, 4006–4014
  * Che et al. 2018 Che, F.; Gray, J. T.; Ha, S.; Kruse, N.; Scott, S. L.; McEwen, J.-S. Elucidating the Roles of Electric Fields in Catalysis: A Perspective. _ACS Catal._ 2018, _8_ , 5153–5174
  * Jinnouchi et al. 2017 Jinnouchi, R.; Kodama, K.; Nagoya, A.; Morimoto, Y. Simulated Volcano Plot of Oxygen Reduction Reaction on Stepped Pt Surfaces. _Electrochim. Acta_ 2017, _230_ , 470–478
  * Huang et al. 2018 Huang, J.; Hörmann, N.; Oveisi, E.; Loiudice, A.; De Gregorio, G. L.; Andreussi, O.; Marzari, N.; Buonsanti, R. Potential-induced nanoclustering of metallic catalysts during electrochemical CO2 reduction. _Nat. Commun._ 2018, _9_ , 3117
  * Zhang et al. 2018 Zhang, H.; Goddard, W. A.; Lu, Q.; Cheng, M.-J. The importance of grand-canonical quantum mechanical methods to describe the effect of electrode potential on the stability of intermediates involved in both electrochemical CO2 reduction and hydrogen evolution. _Phys. Chem. Chem. Phys._ 2018, _20_ , 2549–2557
  * Steinmann and Sautet 2016 Steinmann, S. N.; Sautet, P. Assessing a First-Principles Model of an Electrochemical Interface by Comparison with Experiment. _J. Phys. Chem. C_ 2016, _120_ , 5619–5623
  * Filhol and Doublet 2013 Filhol, J.-S.; Doublet, M.-L. An ab initio study of surface electrochemical disproportionation: The case of a water monolayer adsorbed on a Pd(111) surface. _Catal. Today_ 2013, _202_ , 87–97
  * Waegele et al. 2019 Waegele, M. M.; Gunathunge, C. M.; Li, J.; Li, X. How cations affect the electric double layer and the rates and selectivity of electrocatalytic processes. _J. Chem. Phys._ 2019, _151_ , 160902
  * Garlyyev et al. 2018 Garlyyev, B.; Xue, S.; Watzele, S.; Scieszka, D.; Bandarenka, A. S. Influence of the Nature of the Alkali Metal Cations on the Electrical Double-Layer Capacitance of Model Pt(111) and Au(111) Electrodes. _J. Phys. Chem. Lett._ 2018, _9_ , 1927–1930
  * Dabo et al. 2010 Dabo, I.; Cancès, E.; Li, Y. L.; Marzari, N. Towards First-principles Electrochemistry. 2010
  * Bonnet et al. 2014 Bonnet, N.; Dabo, I.; Marzari, N. Chemisorbed Molecules under Potential Bias: Detailed Insights from First-Principles Vibrational Spectroscopies. _Electrochim. Acta_ 2014, _121_ , 210–214
  * Skúlason et al. 2007 Skúlason, E.; Karlberg, G. S.; Rossmeisl, J.; Bligaard, T.; Greeley, J.; Jónsson, H.; Nørskov, J. K. Density functional theory calculations for the hydrogen evolution reaction in an electrochemical double layer on the Pt(111) electrode. _Phys. Chem. Chem. Phys._ 2007, _9_ , 3241–3250
  * Rossmeisl et al. 2008 Rossmeisl, J.; Skúlason, E.; Björketun, M. E.; Tripkovic, V.; Nørskov, J. K. Modeling the electrified solid–liquid interface. _Chem. Phys. Lett._ 2008, _466_ , 68–71
  * Skúlason et al. 2010 Skúlason, E.; Tripkovic, V.; Björketun, M. E.; Gudmundsdóttir, S.; Karlberg, G.; Rossmeisl, J.; Bligaard, T.; Jónsson, H.; Nørskov, J. K. Modeling the Electrochemical Hydrogen Oxidation and Evolution Reactions on the Basis of Density Functional Theory Calculations. _The Journal of Physical Chemistry C_ 2010, _114_ , 18182–18197
  * Björketun et al. 2013 Björketun, M. E.; Zeng, Z.; Ahmed, R.; Tripkovic, V.; Thygesen, K. S.; Rossmeisl, J. Avoiding pitfalls in the modeling of electrochemical interfaces. _Chem. Phys. Lett._ 2013, _555_ , 145–148
  * Ping et al. 2017 Ping, Y.; Nielsen, R. J.; Goddard, W. A., 3rd The Reaction Mechanism with Free Energy Barriers at Constant Potentials for the Oxygen Evolution Reaction at the IrO(2) (110) Surface. _J. Am. Chem. Soc._ 2017, _139_ , 149–155
  * Kolb 1996 Kolb, D. M. Reconstruction phenomena at metal-electrolyte interfaces. _Prog. Surf. Sci._ 1996, _51_ , 109–173
  * Bonnet and Marzari 2013 Bonnet, N.; Marzari, N. First-principles prediction of the equilibrium shape of nanoparticles under realistic electrochemical conditions. _Phys. Rev. Lett._ 2013, _110_ , 086104
  * Weitzner and Dabo 2017 Weitzner, S. E.; Dabo, I. Voltage-dependent cluster expansion for electrified solid-liquid interfaces: Application to the electrochemical deposition of transition metals. _Phys. Rev. B_ 2017, _96_ , 205134
  * Weitzner and Dabo 2017 Weitzner, S. E.; Dabo, I. Quantum–continuum simulation of underpotential deposition at electrified metal–solution interfaces. _Npj Comput. Mater._ 2017, _3_ , 1–7
  * Karmodak and Andreussi 2020 Karmodak, N.; Andreussi, O. Catalytic Activity and Stability of Two-Dimensional Materials for the Hydrogen Evolution Reaction. _ACS Energy Lett._ 2020, _5_ , 885–891
  * Kopač Lautar et al. 2021 Kopač Lautar, A.; Bitenc, J.; Dominko, R.; Filhol, J.-S. Building Ab Initio Interface Pourbaix diagrams to Investigate Electrolyte Stability in the Electrochemical Double Layer: Application to Magnesium Batteries. _ACS Applied Materials & Interfaces_ 2021, _13_ , 8263–8273
  * McCrum and Janik 2016 McCrum, I. T.; Janik, M. J. First principles simulations of cyclic voltammograms on stepped pt(553) and pt(533) electrode surfaces. _ChemElectroChem_ 2016, _3_ , 1609–1617
  * Stern 1924 Stern, O. ZUR THEORIE DER ELEKTROLYTISCHEN DOPPELSCHICHT. _Z. Elektrochem. Angew. Physi. Chem._ 1924, _30_ , 508–516
  * Cheng and Sprik 2012 Cheng, J.; Sprik, M. Alignment of electronic energy levels at electrochemical interfaces. _Phys. Chem. Chem. Phys._ 2012, _14_ , 11245–11267
  * Le et al. 2018 Le, J.; Cuesta, A.; Cheng, J. The structure of metal-water interface at the potential of zero charge from density functional theory-based molecular dynamics. _J. Electroanal. Chem._ 2018, _819_ , 87–94
  * Le et al. 2021 Le, J.-B.; Chen, A.; Li, L.; Xiong, J.-F.; Lan, J.; Liu, Y.-P.; Iannuzzi, M.; Cheng, J. Modeling Electrified Pt(111)-Had/Water Interfaces from Ab Initio Molecular Dynamics. _JACS Au_ 2021, _1_ , 569–577
  * Bouzid and Pasquarello 2018 Bouzid, A.; Pasquarello, A. Atomic-Scale Simulation of Electrochemical Processes at Electrode/Water Interfaces under Referenced Bias Potential. _J. Phys. Chem. Lett._ 2018, _9_ , 1880–1884
  * Goldsmith et al. 2021 Goldsmith, Z. K.; Calegari Andrade, M. F.; Selloni, A. Effects of applied voltage on water at a gold electrode interface from ab initio molecular dynamics. _Chem. Sci._ 2021, _12_ , 5865–5873
  * Surendralal et al. 2018 Surendralal, S.; Todorova, M.; Finnis, M. W.; Neugebauer, J. First-Principles Approach to Model Electrochemical Reactions: Understanding the Fundamental Mechanisms behind Mg Corrosion. _Phys. Rev. Lett._ 2018, _120_ , 246801


m^{\lceil\log_{2}\left(\frac{14\left(1+C\right)}{C}\right)\rceil}\cdot\lceil\log_{2}\left(\frac{14\left(1+C\right)}{C}\right)\rceil}$

and that is the condition on $n$.

Next we need to show how to construct the embedding s.t $K_{L}$ fits the
$\frac{1}{2\cdot|K_{L}|}$ "socket". The idea here is, if $K_{L}$ doesn’t cover
the $\frac{1}{2\cdot|K_{L}|}$ "socket", to trim any excess dead space and
scale so that $K_{L}$ will cover the socket.

For the first step of the recursion assume $K^{1}_{L}$ doesn’t cover
$\frac{1}{2\cdot|K^{1}_{L}|}$ sized socket. As all sockets are interchangeable
and as $K^{1}_{L}$ was embedded as if $|K^{1}_{L}|>2$ one can place the
$K^{1}_{L}$ embedding in such a way that no other embeddings (of other steps
of the recursion) are on the same $[0,1]^{2}$ horizontal line or $[0,1]^{2}$
vertical line as $K^{1}_{L}$. Such an embedding can be done by placing
$K^{1}_{L}$ on the left bottom corner among the
$(2\max\\{|K^{1}_{L}|,3\\})^{2}$ sockets and placing the other $|K^{1}_{L}|$
recursive steps in the $(2\max\\{|K^{1}_{L}|,3\\})^{2}-2|K^{1}_{L}|$ socket
that aren’t on the same $[0,1]^{2}$ vertical or horizontal line as
$K^{1}_{L}$. And as $(2\max\\{|K^{1}_{L}|,3\\})^{2}-2|K^{1}_{L}|>|K^{1}_{L}|$
this can be done. Next mark all the lines in $K^{1}_{L}$ between cities of
$K^{1}_{L}$ and look at the projection of the marked lines on the $x$ axis,
it’s a set that doesn’t cover all $\frac{1}{2\max\\{|K^{1}_{L}|,3\\}}$ and
thus $a_{x}$ is the renaming length between the embedding and
$\frac{1}{2\max\\{|K^{1}_{L}|,3\\}}$. Do the same for the $y$ axis and choose
$b=\min\\{a_{x},a_{y}\\}$. Choose stripes in $[0,1]^{2}$ of width $b$ not on
$K^{1}_{L}$. As these stripes weren’t on $K^{1}_{L}$ and no other embedding is
to be found on the same horizontal or vertical lines no cities or $sq_{i}$s or
parts of paths are to be found within the stripes. Remove the stripes, now we
have $BAS(g)$ based on $[0,1-b]^{2}$ (rather than $[0,1]^{2}$). Normalize the
function back to based on $[0,1-b]^{2}$ by

$f_{\text{new}}(x,y)=\frac{1}{1-b}\cdot f((1-b)\cdot x,(1-b)\cdot y)$

as one can clearly see the first derivative doesn’t change (as

$\frac{\partial}{\partial x}f_{\text{new}}(x,y)=\frac{\partial}{\partial
x}f((1-b)\cdot x,(1-b)\cdot y)$

and the same goes for $y$) and the second order derivatives only decrease (as

$\frac{\partial^{2}}{\partial
x^{2}}f_{\text{new}}(x,y)=(1-b)\frac{\partial^{2}}{\partial x^{2}}f((1-b)\cdot
x,(1-b)\cdot y)$

and $(1-b)<1$ and the same goes for the other second order derivative. Thus
$M_{1},M_{2}$ bounds remain the same. Note that the maximum of the values of
$f$ may increase.

The embedding remained the same as both the embedding of $K^{1}_{L}$ and of
the recursive steps remains the same and were only enlarged by the same factor
and the value between sockets is higher than before (so no new paths between
$K^{1}_{L}$ or the recursive steps can emerge). Note that the normalization
factor $\alpha$ of 5.15 will change due to this enlargement.

For any of the subsequent recursive steps the construction remains the same,
if $K_{L}$ doesn’t cover the sized socket we can place it (as all sockets are
interchangeable) in such a way that there are no other embeddings (of other
steps of the recursion) are on the same $[0,1]^{2}$ horizontal line or
vertical line as $K_{L}$. Note that in the recursive case that may call for
changes to the placement of previous embedding as well. Afterwards we look at
the projection of $K_{L}$, slice the dead strips and normalize to fit a
$BAS(g)$ based on $[0,1]^{2}$.

Finally, assuming worst case scenario, if every step in the recursion needs
such a trim, we have no more than $n$ trims (for each of $K_{L}$ unique city)
and every trim is of fixed time to compute (provided $C,m$ are fixed) as $f$
is already known $K_{L}$ has a maximum number of cities bounded by a function
of $C,m$ and multiplying by a constant (for the enlargement) is $O(1)$. So the
bound

$n\cdot
S(C,m)\left(\frac{2\max_{x,y\in\left\\{1,\ldots,n\right\\}}d\left(x,y\right)}{\min_{x,y\in\left\\{1,\ldots,n\right\\}}d\left(x,y\right)}\right)^{T_{1}\left(C,m\right)}$

on the running time stays the same (The functions
$S(C,m),T_{1}\left(C,m\right)$ may change). ∎

In the practical case, as we only need equation (1) above to hold w.r.t a
fixed number (i.e $1$), one can save the hassle of trimming all recursive
steps and estimate the LHS of equation (1) by using Christofides algorithm
[11] to estimate the LHS. Once that LHS Christofides’s estimation is $\geq 1$
the final LHS can’t be less than $\frac{2}{3}$ and as 4.3 needs only
$\frac{1}{2}$ that suffice.

##  6 Solving TSP on metrics

In this section we will finally combine the embeddings of 5 of a given metric
to a surface along with 4 and the algorithm given in 4.3 to solve TSP on a
surface to receive an algorithm to solve TSP problem for given arbitrary
metrics.

Let’s start with the obvious:

######  Theorem 6.1.

Given a series of metric spaces
$d_{k}:\\{1,\ldots,n_{k}\\}\rightarrow\mathbb{R}$ for $k\in\mathbb{N}$ one can
estimate the $\frac{1}{C}$ approximation of the TSP problem on $d_{k}$ (with
probability $\geq\frac{1}{2}$). The running time (which may be non-polynomial
in $n_{k}$) depends on the growth of $n_{k}$ and the metric spaces.

###### Proof.

Given a $k\in\mathbb{N}$ use 5.5 to embed $d_{k}$ into a surface and then use
4.3 to estimate the $\frac{1}{C}$ approximation of the TSP problem on $d_{k}$
(see the corollary after 5.9). ∎

Now for the polynomially bounded cases:

######  Theorem 6.2.

Given a series of metric spaces
$d_{k}:\\{1,\ldots,n_{k}\\}\rightarrow\mathbb{R}$ for $k\in\mathbb{N}$ s.t all
are uniform one can estimate the $\frac{1}{C}$ approximation of the TSP
problem on $d_{k}$ (with probability $\geq\frac{1}{2}$). The running time is
polynomially bounded by $n_{k}$.

###### Proof.

Given a $k\in\mathbb{N}$ use 5.11 to embed $d_{k}$ into a surface and then use
4.3 to estimate the $\frac{1}{C}$ approximation of the TSP problem on $d_{k}$.
As $M_{1}=M_{2}=0$ in this case and $g=n^{2}$ the expression in the time bound
4.12 is

$O(n_{k}^{2}5+n_{k}^{1+T(0,0,C)}\cdot\log(n_{k})$

where $T$ is the function that appears in 4.12. This expression is
polynomially bounded by $n_{k}$. ∎

######  Theorem 6.3.

Given a series of metric spaces
$d_{k}:\\{1,\ldots,n_{k}\\}\rightarrow\mathbb{R}$ for $k\in\mathbb{N}$ s.t all
are $m>0$ doubling (with the same doubling constant) one can estimate the
$1+\frac{1}{C}$ approximation of the TSP problem on $d_{k}$ (with probability
$\geq\frac{1}{2}$). The running time is polynomially bounded by $n_{k}$.

The key idea in this proof is to bound the size of
$\frac{\max_{x,y\in\left\\{1,\ldots,n\right\\}d_{k}\left(x,y\right)}}{\min_{x,y\in\left\\{1,\ldots,n\right\\}d_{k}\left(x,y\right)}}$
by changing the metric space in such a way that the $\frac{1}{C}$
approximation won’t change (on the one hand) but
$\frac{\max_{x,y\in\left\\{1,\ldots,n\right\\}d_{k}\left(x,y\right)}}{\min_{x,y\in\left\\{1,\ldots,n\right\\}d_{k}\left(x,y\right)}}$
won’t be too large on the other.

###### Proof.

we will denote $n=n_{k}$ for simplicity. Assume $C>1$ (otherwise enlarge $C$
\- it will only improve the approximation). Denote $C_{0}=10\cdot C$ and
$\bar{C}=\frac{1}{C_{0}}$, and denote

$d_{k}^{\text{new}}\left(x,y\right)=\begin{cases}d_{k}\left(x,y\right)&\text{if
$d_{k}\left(x,y\right)$>}\frac{\bar{C}}{n}\left(\max_{x_{0}\neq
y_{0}}d_{k}\left(x_{0},y_{0}\right)\right)\\\
\frac{\bar{C}}{n+1}\left(\max_{x_{0}\neq
y_{0}}d_{k}\left(x_{0},y_{0}\right)\right)&\text{else}\end{cases}$

Please note that for a fixed $C$, $\bar{C}$ and $C_{0}$ are also constants (as
a function of $C$).

Use 5.15 (along with 5.16) to embed a $(1+\bar{C})$ approximation of
$d_{k}^{\text{new}}$, receive a surface $(f,g)$ along with
$p_{1},\ldots,p_{n}$. Denote the optimal TSP path on $d_{S(f,g)}$ by $s_{2}\in
S(n)$. Use 4.3 to calculate the $(1+\frac{1}{C_{0}})$ approximation TSP tour
denote the path given by the algorithm by $s_{2}\in S(n)$.

Now for the estimation proof: For any $s\in S(n_{k})$ it holds that the path
of $s$ on $d_{k}^{\text{new}}$ is at most $\left(1+\bar{C}\right)$
approximation of the same path in $d_{k}$, as

$\displaystyle
d_{k}^{\text{new}}\left(p_{s\left(n\right)},p_{s\left(1\right)}\right)+\overset{n-1}{\underset{j=1}{\sum}}d_{k}^{\text{new}}\left(p_{s\left(j\right)},p_{s\left(j+1\right)}\right)$
$\displaystyle\leq^{\left(1\right)}$ $\displaystyle
d_{k}\left(p_{s\left(n\right)},p_{s\left(1\right)}\right)+\overset{n-1}{\underset{j=1}{\sum}}d_{k}\left(p_{s\left(j\right)},p_{s\left(j+1\right)}\right)+\left(n+1\right)\cdot\frac{\bar{C}}{n+1}\left(\max_{x_{0}\neq
y_{0}}d_{k}\left(x_{0},y_{0}\right)\right)$ $\displaystyle=$ $\displaystyle
d_{k}\left(p_{s\left(n\right)},p_{s\left(1\right)}\right)+\overset{n-1}{\underset{j=1}{\sum}}d_{k}\left(p_{s\left(j\right)},p_{s\left(j+1\right)}\right)+\bar{C}\left(\max_{x_{0}\neq
y_{0}}d_{k}\left(x_{0},y_{0}\right)\right)$
$\displaystyle\leq^{\left(2\right)}$ $\displaystyle
d_{k}\left(p_{s\left(n\right)},p_{s\left(1\right)}\right)+\overset{n-1}{\underset{j=1}{\sum}}d_{k}\left(p_{s\left(j\right)},p_{s\left(j+1\right)}\right)+\left(d_{k}\left(p_{s\left(n\right)},p_{s\left(1\right)}\right)+\overset{n-1}{\underset{j=1}{\sum}}d_{k}\left(p_{s\left(j\right)},p_{s\left(j+1\right)}\right)\right)\cdot\bar{C}$
$\displaystyle=$
$\displaystyle\left(1+\bar{C}\right)\left(d_{k}\left(p_{s\left(n\right)},p_{s\left(1\right)}\right)+\overset{n-1}{\underset{j=1}{\sum}}d_{k}\left(p_{s\left(j\right)},p_{s\left(j+1\right)}\right)\right)$

where

  * •

inequity 1 is due to the fact that the most increase between $d_{k}$ and
$d_{k}^{\text{new}}$ is $\frac{\bar{C}}{n+1}\left(\max_{x_{0}\neq
y_{0}}d_{k}\left(x_{0},y_{0}\right)\right)$ at most on each intercity travel
and there are $n+1$ of them.

  * •

inequity 2 is due to the fact that any closed tour must be of larger length
than the maximum intercity distance (generalized triangle inequality)

So, the path $s$ is also an $(1+\bar{C})^{2}$ upper approximation as

$\displaystyle
d_{S\left(f,g\right)}\left(p_{s\left(n\right)},p_{s\left(1\right)}\right)+\overset{n-1}{\underset{j=1}{\sum}}d_{S\left(f,g\right)}\left(p_{s\left(j\right)},p_{s\left(j+1\right)}\right)\leq$
$\displaystyle\left(1+\bar{C}\right)\left(d_{k}^{\text{new}}\left(p_{s\left(n\right)},p_{s\left(1\right)}\right)+\overset{n-1}{\underset{j=1}{\sum}}d_{k}^{\text{new}}\left(p_{s\left(j\right)},p_{s\left(j+1\right)}\right)\right)\leq$
$\displaystyle\left(1+\bar{C}\right)^{2}\left(d_{k}\left(p_{s\left(n\right)},p_{s\left(1\right)}\right)+\overset{n-1}{\underset{j=1}{\sum}}d_{k}\left(p_{s\left(j\right)},p_{s\left(j+1\right)}\right)\right)$

and a $(1-\bar{C})$ lower approximation on the other hand, as

$\displaystyle
d_{S\left(f,g\right)}\left(p_{s\left(n\right)},p_{s\left(1\right)}\right)+\overset{n-1}{\underset{j=1}{\sum}}d_{S\left(f,g\right)}\left(p_{s\left(j\right)},p_{s\left(j+1\right)}\right)$
$\displaystyle\geq\left(1-\bar{C}\right)\left(d_{k}^{\text{new}}\left(p_{s\left(n\right)},p_{s\left(1\right)}\right)+\overset{n-1}{\underset{j=1}{\sum}}d_{k}^{\text{new}}\left(p_{s\left(j\right)},p_{s\left(j+1\right)}\right)\right)$
$\displaystyle\geq\left(1-\bar{C}\right)\left(d_{k}\left(p_{s\left(n\right)},p_{s\left(1\right)}\right)+\overset{n-1}{\underset{j=1}{\sum}}d_{k}\left(p_{s\left(j\right)},p_{s\left(j+1\right)}\right)\right)$

(As $S(f,g)$ is a $\bar{C}$ approximation of $d_{k}^{\text{new}}$ and
$d_{k}^{\text{new}}$ was a length increase over $d_{k}$.)

Denote $s_{3}\in S(n)$ to be the optimal TSP path on $d_{k}$, we receive

$\displaystyle\left(1-\bar{C}\right)\left(d_{k}^{\text{}}\left(p_{s_{2}\left(n\right)},p_{s_{2}\left(1\right)}\right)+\overset{n-1}{\underset{j=1}{\sum}}d_{k}^{\text{}}\left(p_{s_{2}\left(j\right)},p_{s_{2}\left(j+1\right)}\right)\right)\leq^{\left(1\right)}$
$\displaystyle
d_{S\left(f,g\right)}\left(p_{s_{2}\left(n\right)},p_{s_{2}\left(1\right)}\right)+\overset{n-1}{\underset{j=1}{\sum}}d_{S\left(f,g\right)}\left(p_{s_{2}\left(j\right)},p_{s_{2}\left(j+1\right)}\right)\leq^{\left(2\right)}$
$\displaystyle\left(1+\frac{1}{C_{0}}\right)\left(d_{S\left(f,g\right)}\left(p_{s_{1}\left(n\right)},p_{s_{1}\left(1\right)}\right)+\overset{n-1}{\underset{j=1}{\sum}}d_{S\left(f,g\right)}\left(p_{s_{1}\left(j\right)},p_{s_{1}\left(j+1\right)}\right)\right)\leq^{\left(2\right)}$
$\displaystyle\left(1+\frac{1}{C_{0}}\right)\left(d_{S\left(f,g\right)}\left(p_{s_{3}\left(n\right)},p_{s_{3}\left(1\right)}\right)+\overset{n-1}{\underset{j=1}{\sum}}d_{S\left(f,g\right)}\left(p_{s_{3}\left(j\right)},p_{s_{3}\left(j+1\right)}\right)\right)\leq^{\left(3\right)}$
$\displaystyle\left(1+\frac{1}{C_{0}}\right)\left(1+\bar{C}\right)^{2}\left(d_{k}^{\text{}}\left(p_{s_{3}\left(n\right)},p_{s_{3}\left(1\right)}\right)+\overset{n-1}{\underset{j=1}{\sum}}d_{k}^{\text{}}\left(p_{s_{3}\left(j\right)},p_{s_{3}\left(j+1\right)}\right)\right)$
$\displaystyle=\left(1+\frac{1}{C_{0}}\right)\left(1+\bar{C}\right)^{2}OPT\left(d_{k}\right)$

where:

  * •

inequalities 1 and 3 are the inequalities proven above applied to $s_{2}$ and
$s_{3}$ respectively.

  * •

inequality 2 is due to the fact that $s_{1}$ is the optimal TSP tour on
$d_{S(f,g)}$ and therefore any other tour (such as $s_{3}$) must be of larger
or equal length.

So we receive that

$d_{k}^{\text{}}\left(p_{s_{2}\left(n\right)},p_{s_{2}\left(1\right)}\right)+\overset{n-1}{\underset{j=1}{\sum}}d_{k}^{\text{}}\left(p_{s_{2}\left(j\right)},p_{s_{2}\left(j+1\right)}\right)\leq\frac{\left(1+\frac{1}{C_{0}}\right)\left(1+\bar{C}\right)^{2}}{1-\bar{C}}OPT\left(d_{k}\right)$

that mean that the path we calculated is a
$\frac{\left(1+\frac{1}{C_{0}}\right)\left(1+\bar{C}\right)^{2}}{1-\bar{C}}$
approximation of the optimal TSP tour. And as

$\frac{\left(1+\frac{1}{C_{0}}\right)\left(1+\bar{C}\right)^{2}}{1-\bar{C}}=\frac{\left(1+\bar{C}\right)\left(1+\bar{C}\right)^{2}}{1-\bar{C}}=\frac{1+\bar{3C}+3\bar{C}^{2}+\bar{C}^{3}}{1-\bar{C}}\leq^{\left(1\right)}\frac{1+7\bar{C}}{1-\bar{C}}<^{\left(2\right)}1+\frac{1}{C}$

where

  * •

inequality 1 is due to the fact that $C>1$ and thus $\bar{C}<1$

  * •

inequality 2 is due to:

$\displaystyle\bar{C}$
$\displaystyle=\frac{1}{10C}<\frac{1}{\left(8+\frac{1}{C}\right)C}$
$\displaystyle\Downarrow$
$\displaystyle\bar{C}\left(8+\frac{1}{C}\right)<\frac{1}{C}$
$\displaystyle\Downarrow$ $\displaystyle
8\bar{C}+\frac{\bar{C}}{C}<\frac{1}{C}$ $\displaystyle\Downarrow$
$\displaystyle
1+7\bar{C}<1-\bar{C}+\frac{1}{C}-\frac{\bar{C}}{C}=\left(1-\bar{C}\right)\left(1+\frac{1}{C}\right)$
$\Downarrow$ $\displaystyle\frac{1+7\bar{C}}{1-\bar{C}}<1+\frac{1}{C}$

Therefore, the algorithm gives a $1+\frac{1}{C}$ approximation of the optimal
TSP travel.

Now for the time bound: As

$\frac{\max_{x,y\in\left\\{1,\ldots,n\right\\}d_{k}\left(x,y\right)}}{\min_{x,y\in\left\\{1,\ldots,n\right\\}d_{k}\left(x,y\right)}}\leq\frac{\max_{x,y\in\left\\{1,\ldots,n\right\\}d_{k}\left(x,y\right)}}{\frac{\bar{C}}{n+1}\left(\max_{x_{0}\neq
y_{0}}d_{k}\left(x_{0},y_{0}\right)\right)}=\frac{n+1}{\bar{C}}=10C\left(n+1\right)$

we know that the time bound

$n_{k}\cdot
S(\bar{C},m)\left(\frac{2\max_{x,y\in\left\\{1,\ldots,n\right\\}}d\left(x,y\right)}{\min_{x,y\in\left\\{1,\ldots,n\right\\}}d\left(x,y\right)}\right)^{T_{1}\left(\bar{C},m\right)}$

on 5.15 is simply

$n\cdot
S(\bar{C},m)\left(20C\left(n+1\right)\right)^{T_{1}\left(\bar{C},m\right)}$

which is polynomially bounded by $n=n_{k}$ and 4.3 is bounded by 4.12 which is

$O(n^{25}+n\cdot\log(n)\cdot g^{T(M_{1},M_{2},C_{0})})$

as $M_{1},M_{2}$ are bounded by a function of $C_{0},m$ and as

$g<nm^{\lceil\log_{2}\left(\frac{14\left(1+C_{0}\right)}{C_{0}}\right)\rceil}\log_{\left(\frac{4+4C_{0}}{4+3C_{0}}\right)}\frac{2\max_{x,y\in\left\\{1,\ldots,n\right\\}}d_{1}\left(x,y\right)}{\min_{x,y\in\left\\{1,\ldots,n\right\\}}d_{1}\left(x,y\right)}$

the time bound here is polynomially bounded by $n=n_{k}$ as well. ∎

######  Corollary 6.4.

The above solutions to the TSP problem on different metric spaces can be done
with certainty, rather than with probability $\geq\frac{1}{2}$ by de-
randomizing the algorithm, as seen in 4.14. The running time will remain
polynomially bounded, as mentioned in 4.14.

-

## References

  * [1] Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur" (The traveling salesman — how he must be and what he should do in order to get commissions and be sure of the happy success in his business — by an old commis-voyageur)
  * [2] "Reducibility Among Combinatorial Problems". In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103
  * [3] Orponen, P.; Mannila, H. (1987), "On approximation preserving reductions: Complete problems and robust measures’", Technical Report C-1987–28, Department of Computer Science, University of Helsinki.
  * [4] S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy. “Proof verification and the hardness of approximation problems” J. ACM, 45(3): 501-555, 1998.
  * [5] ”New inapproximability bounds for TSP” by M.Karpinski, M.Lampis, R.Schmied. Journal of Computer and System Sciences Volume 81 Issue 8, December 2015 Pages 1665-1677.
  * [6] ”When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree” by Luca Trevisan. SIAM J. Comput., 30(2), 475–485. (11 pages) 2000.
  * [7] Sanjeev Arora. 1998. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45, 5 (September 1998), 753-782. DOI=http://dx.doi.org/10.1145/290179.290180
  * [8] Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomialtime approximation scheme for geometric TSP, k- MST, and related problems. SIAM J. Comput., 28(4):1298–1309, 1999.
  * [9] The travelling salesman problem: low-dimensionality implies a polynomial time approximation scheme. Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer. STOC 2012: 663-672 (extended abstract)
  * [10] Thomas H. Cormen et al. Introduction to Algorithms, Second Edition. ISBN 0-262-03293-7 subsection 25.2 The Floyd-Warshall algorithm, page 535.
  * [11] Christofides, Christofides (1976), Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU.