{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:57Z","timestamp":1753893837870,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>Recall that Janson showed that if the edges of the complete graph $K_n$ are assigned exponentially distributed independent random weights, then the expected length of a shortest path between a fixed pair of vertices is asymptotically equal to $(\\log n)\/n$.\u00a0 We consider analogous problems where edges have not only a random length but also a random cost, and we are interested in the length of the minimum-length structure whose total cost is less than some cost budget.\u00a0 For several classes of structures, we determine the correct minimum length structure as a function of the cost-budget, up to constant factors.\u00a0 Moreover, we achieve this even in the more general setting where the distribution of weights and costs are arbitrary, so long as the density $f(x)$ as $x\\to 0$ behaves like $cx^\\gamma$ for some $\\gamma\\geq 0$; previously, this case was not understood even in the absence of cost constraints.\u00a0 We also handle the case where each edge has several independent costs associated to it, and we must simultaneously satisfy budgets on each cost.\u00a0 In this case, we show that the minimum-length structure obtainable is essentially controlled by the product of the cost thresholds.<\/jats:p>","DOI":"10.37236\/9152","type":"journal-article","created":{"date-parts":[[2021,2,11]],"date-time":"2021-02-11T10:12:11Z","timestamp":1613038331000},"source":"Crossref","is-referenced-by-count":0,"title":["Minimum-Weight Combinatorial Structures Under Random Cost-Constraints"],"prefix":"10.37236","volume":"28","author":[{"given":"Alan","family":"Frieze","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wesley","family":"Pegden","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gregory B.","family":"Sorkin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomasz","family":"Tkocz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2021,1,29]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v28i1p20\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v28i1p20\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,11]],"date-time":"2021-02-11T10:12:11Z","timestamp":1613038331000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v28i1p20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,29]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1,14]]}},"URL":"https:\/\/doi.org\/10.37236\/9152","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2021,1,29]]},"article-number":"P1.20"}}