what would be generally the most cost-efficient city/university combos?

Hi Ioannis.
First of all, it's worth noticing that Germany is a country with a high average income, but therefore also with a high cost of living in the urban centers. That'd be the case in the regions you mentioned, but also in and around Stuttgart, Frankfurt and Cologne, to add few more examples.
So, with a small budget, conurbations should be avoided - with some possible exceptions in the more rural regions, more particularly in eastern, northern and central Germany. Dresden, Leipzig or Erfurt would be larger cities where the cost of living is not as high and also falling more sharply in the outlying districts.
However, more urban areas and larger cities often also mean a larger selection of private universities.
Another aspect: the prices for individual degree courses can vary. It is therefore possible that a private university is not generally cheaper than others.
So, generally, you should get an overview of available study locations for your program (incl. price) and check the cost of living. This site with user-generated insights on the cost of living in different cities might be helpful:
https://www.numbeo.com/cost-of-living/rankings.jsp
Let's stick with Dresden, Erfurt and Leipzig and their private universities for now, but keep in mind there might be cheaper cities or cheaper unis.
Let's have a look at different Bachelor's degree on-campus studies in Dresden:
Dresden University of Applied Sciences, for example, offers some of the basic fields of study at a moderate price.

IU International University of Applied Sciences adds to the mix, is a bit more affordable but also hardly an on-campus study, as its programs are either „dual“ or „blended learning“, both with a good portion of distance learning.
[courses items="16637,15910,17082,17049,17047" layout="tabelle" type="studiengaenge" head="anbieter,dauer,inhalte,kosten_gesamt,kosten_monat,favorites" order="title_asc"]
Add the programs of SRH Berlin University of Applied Sciences and Dresden International University you get some more in the fields of tourism or health and social sciences, at both the upper and lower end of the price range.
Leipzig is somewhat more expensive and will be even more so in the near future as it's growing fast. Nevertheless, it is currently still one of the more affordable larger conurbations.
DIPLOMA University of Applied Sciences might be of specific interest here, for education sciences and on the lower end of the price spectrum, as might be the University of Applied Management in the fields of Business Administration, Management or Marketing.
Erfurt should be of special interest for anyone who wants to study Human Medicine or Psychology. Erfurt is comparatively cheap and the Health and Medical University is offering these programs.

The IU International University of Applied Sciences has its headquarters here, offering dual study programs for the region.
As you can see, there's a lot to consider and finding the ideal combination can be time-consuming, but it's worth it in the long run.
Hope this helps.
Kind regards