1 Search Results for "Tripathi, Pushkar"


Document
Combinatorial Problems with Discounted Price Functions in Multi-agent Systems

Authors: Gagan Goel, Pushkar Tripathi, and Lei Wang

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)


Abstract
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.

Cite as

Gagan Goel, Pushkar Tripathi, and Lei Wang. Combinatorial Problems with Discounted Price Functions in Multi-agent Systems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 436-446, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{goel_et_al:LIPIcs.FSTTCS.2010.436,
  author =	{Goel, Gagan and Tripathi, Pushkar and Wang, Lei},
  title =	{{Combinatorial Problems with Discounted Price Functions in Multi-agent Systems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{436--446},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.436},
  URN =		{urn:nbn:de:0030-drops-28847},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.436},
  annote =	{Keywords: Approximation algorithm, decreasing marginal cost, submodular function, discounted price function}
}
  • Refine by Author
  • 1 Goel, Gagan
  • 1 Tripathi, Pushkar
  • 1 Wang, Lei

  • Refine by Classification

  • Refine by Keyword
  • 1 Approximation algorithm
  • 1 decreasing marginal cost
  • 1 discounted price function
  • 1 submodular function

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2010

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail