Using a sitemap is the appropriate way to do this. One issue however is that search engine robots do not crawl at specific schedules. As sitemaps.org states about the changefreq attribute:
Please note that the value of this tag is considered a hint and not a
command. Even though search engine crawlers may consider this
information when making decisions, they may crawl pages marked
"hourly" less frequently than that, and they may crawl pages marked
"yearly" more frequently than that.
Therefore, specifying the
<changefreq> to be weekly may not be sufficient to index your weekly changes, particularly at the start of each week... It might be helpful to change this to "daily" instead. Also make sure the
<lastmod> attribute is incremented daily as well. Note that this will however increase the load on your web server too.
It's also important to note that
<changefreq> indicates the change frequency for pages to change, not URL's. Since the actual URL's for weekly "deals" will change, this and the
<priority> attribute aren't of benefit. In this case, you need robots to crawl the newly created URL's for weekly deals.
For that reason, you may also want to create a "Deals" page with these new links listed on it, and specify the
<priority> for this Deals page in your sitemap. And just by updating the content on your site more often, your site will likely get crawled more frequently too.