Optimal Approximation Algorithms for Multi-agent Combinatorial Problems with Discounted Price Functions

Details Optimal Approximation Algorithms for Multi-agent Combinatorial Problems with Discounted Price Functions Optimal Approximation Algorithms for Multi-agent Combinatorial Problems with Discounted Price Functions

2009-11-06

arxiv.org/abs/0911.1346v1

Computer Science

Multiagent Systems

Scientific paper

Submodular functions are an important class of functions in combinatorial optimization which satisfy the natural properties of decreasing marginal costs. The study of these functions has led to strong structural properties with applications in many areas. Recently, there has been significant interest in extending the theory of algorithms for optimizing combinatorial problems (such as network design problem of spanning tree) over submodular functions. Unfortunately, the lower bounds under the general class of submodular functions are known to be very high for many of the classical problems. 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 cost functions. In this paper we study the following fundamental combinatorial optimization problems: Edge Cover, Spanning Tree, Perfect Matching and Shortest Path, and obtain tight upper and lower bounds for these problems. The main technical contribution of this paper is designing novel adaptive greedy algorithms for the above problems. These algorithms greedily build the solution whist rectifying mistakes made in the previous steps.

Affiliated with

Also associated with

No associations

Rating

Optimal Approximation Algorithms for Multi-agent Combinatorial Problems with Discounted Price Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Approximation Algorithms for Multi-agent Combinatorial Problems with Discounted Price Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Approximation Algorithms for Multi-agent Combinatorial Problems with Discounted Price Functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-699096