2026-08-17T10:43:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2884 2024-03-06T10:33:40Z ddc:004 open_access

Combinatorial Problems with Discounted Price Functions in Multi-agent Systems Goel, Gagan Tripathi, Pushkar Wang, Lei Approximation algorithm decreasing marginal cost submodular function discounted price function Motivated by economic thought, a recent research agenda has suggested the algorithmic study of combinatorial optimization problems under functions which satisfy the property of decreasing marginal cost. A natural first step to model such functions is to consider submodular functions. However, many fundamental problems have turned out to be extremely hard to approximate under general submodular functions, thus indicating the need for a systematic study of subclasses of submodular functions that are practically motivated and yield good approximation ratios. In this paper, we introduce and study an important subclass of submodular functions, which we call discounted price functions. These functions are succinctly representable and generalize linear(additive) price functions. We study the following fundamental combinatorial optimization problems: edge cover, spanning tree, perfect matching and $s-t$ path. We give both upper and lower bound for the approximability of these problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gagan Goel and Pushkar Tripathi and Lei Wang 2010 Is Part Of LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2010.436 urn:nbn:de:0030-drops-28847 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.436 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode