2012/05/08 by Kevin Costello, Costello, Kevin, Prasad Tetali +3
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Game Theory and Voting Systems #Optimization and Search Problems #cs.DM #cs.DS #cs.GT
paper · pdf · doi:10.48550/arxiv.1205.1721
arxiv created 2012/05/08 · openalex publication_date 2012/05/08 · arxiv updated 2015/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the following stochastic optimization problem first introduced by Chen et al. in \citechen. We are given a vertex set of a random graph where each possible edge is present with probability pe. We do not know which edges are actually present unless we scan/probe an edge. However whenever we probe an edge and find it to be present, we are constrained to picking the edge and both its end points are deleted from the graph. We wish to find the maximum matching in this model. We compare our results against the optimal omniscient algorithm that knows the edges of the graph and present a 0.573 factor algorithm using a novel sampling technique. We also prove that no algorithm can attain a factor better than 0.898 in this model.