Which algorithm does the location-allocation Maximize Coverage problem type use? I already found on the ArcGIS help that location-allocation uses a vertex substitution heuristic to solve the p-median problem (Teitz and Bart), but I didn't find, which algorithm the Maximize Coverage uses. Is it also solved as a p-median problem (Teitz and Bart)?
esri normally doesn't specify which algorithms they use, but you could try going to help file link for a topic and on the bottom right, there is a "Provide Feedback link". You could send a message there stating that you would like to see a reference to the describe the method used for the tool. They may respond... otherwise, you are left with doing a trial and error should there be alternatives. I would check your reference link to see if the methodology is applicable in different scenarios.
The algorithms used by Network Analyst are described here:
Algorithms used by the ArcGIS Network Analyst extension—Help | ArcGIS for Desktop
As discussed there, for Location-Allocation, we use a vertex substitution heuristic to solve the p-median problem. And we use a process called Hillsman editing to first transform a particular problem type such as Maximize Coverage to a P-median and then use the same heuristic.
Here is a reference to the original paper by Ed Hillsman:
Hillsman, E.L. (1984). The p-median structure as a unified linear model for location-allocation analysis. Environment and Planning A, 16 (3), 305-318
And here is another researcher using a similar approach: