Martin Pál - papers

Hubie Chen, Martin Pál.
Optimization, Games, and Quantified Constraint Satisfaction.
Summary:
Bib info:To appear in MFCS'04.
• Anupam Gupta, R. Ravi, Martin Pál, Amitabh Sinha.
  Boosted Sampling: Approximation Algorithms for Stochastic Optimization.
  Summary: We consider the following stochastic problem: today, we can buy some elements (edges, facilities, vertices..) at a low price. Tomorrow, demands will materialize, and we will need to buy some more elements, at a much higher price, to serve those demands. If we assume that the demands are drawn from a known probability distribution, what set of elements should we buy today? We give a simple but powerful framework that gives us constant approximation algorithms for a number of problems, such as Facility Location, Steiner tree or Vertex Cover.
  Bib info: STOC 2004.

• Anupam Gupta, Amit Kumar, Martin Pál and Tim Roughgarden.
  Approximation Via Cost Sharing: Simple Approximations for the Multicommodity Rent-or-Buy Problem.
  Summary: We consider the multicommodity rent-or-buy problem, in which a set of terminal pairs is given, and the goal is to rent and buy edges so that the terminal pairs get connected. We show a novel connection between cost sharing and approximation algorithms, and give a general framework in which "strict" cost shares can be used to lift an approximation for a "buy only" problem to a corresopnding two-level problem. Using this framework, we give a simple 12-approximation for the multicommodity rent or buy problem.
  Note: The conference paper gives a 12-approximation, but a slight refinement of the analysis (to appear in a journal version) shows approximation guarantee of 8.
  Bib info: Proceedings of the 44th Annual IEEE Symposium on the Foundations of Computer Science, 2003.
  slides (long version)

• Martin Pál, Éva Tardos.
  Strategy Proof Mechanisms via Primal-dual Algorithms.
  Summary: We consider the problem of sharing the cost of a facility shared by selfish users. We assume that each user has some kind of requirement (such as being connected to a facility) and is willing to pay a contribution towards the shared solution if this requirement is met. Our work is motivated by a result of Moulin and Shenker that a group strategyproof sharing mechanism is possible if we have a cross-monotonic cost sharing function for the problem. We give cross-monotonic cost sharing functions for two problems: facility location and single-sink rent-or-buy. Both functions are competitive and recover a constant fraction of the cost.
  Bib info: Proceedings of the 44th Annual IEEE Symposium on the Foundations of Computer Science, 2003.
  slides (long version)

• Mohammad Mahdian, Martin Pál.
  Universal Facility Location.
  Summary: We consider a facility location problem in which the cost of the facility can be an arbitrary non-decreasing function of the amount of demand served. We give a 8+\epsilon approximation based on local search. This extends and improves the result on hard capacitated facility location from FOCS'01 (below).
  Bib info: European Symposium on Algorithms, 2003. Surprisingly, this little paper won the best student paper award.
  slides

• Martin Pál, Éva Tardos and Tom Wexler.
  Facility Location with Nonuniform Hard Capacities.
  Summary: We give the first approximation algorithm for facility location with hard capacities. That is, each facility has a certain capacity (may be different for different facilities) and cannot serve more demand than its capacity (opening multiple copies of a facility is not allowed). The algorithm is based on local search and achieves approximation guarantee of an 9+\epsilon.
  Bib info: Proceedings of the 42nd Annual IEEE Symposium on the Foundations of Computer Science, 2001.