Martin Pál - papers

  • Jon Feldman, S. Muthukrishnan, Evdokia Nikolova, Martin Pál. A Truthful Mechanism for Offline Ad Slot Scheduling. SAGT 2008.
  • Chandra Chekuri, Nitish Korula and Martin Pál. Improved Algorithms for Orienteering and Related Problems. SODA 2008.
  • Chandra Chekuri, Gruia Calinescu, Martin Pál, Jan Vondrák. Maximizing a Submodular Set Function subject to a Matroid Constraint. IPCO 2007.
  • S. Muthukrishnan, Martin Pál, Zoya Svitkina. Stochastic Models for Budget Optimization in Search-Based Advertising. WINE 2007.
  • Jon Feldman, S. Muthukrishnan, Martin Pál, Cliff Stein. Budget Optimization in Search-Based Advertising Auctions. ACM EC 2007.

  • Chandra Chekuri and Martin Pál. An O(log n) Approximation Ratio for the Asymmetric Treveling Salesman Path problem.
    Summary: We give an O(log n) approximation algorithm for finding the shortest path from a start to an end vertex in a directed graph that visits every other vertex along the way.
    Bib info: Preliminary version in APPROX 2006. Journal version in Theory of Computing.

  • Chandra Chekuri and Martin Pál. Recursive Greedy Algorithm for Walks in Directed Graphs.
    Summary: In orienteering, we are to find a path from a given start vertex to a given destination vertex, of length at most a given budget B, that maximizes the number of vertices visited along the way. Here we consider a generalized version where each vertex may have a time window (and must be visited in that time window in order for the visit to count), and instead of maximizing just the number of vertices visited, we allow maximizing an arbitrary non-decreasing submodular function of the set of visited vertices.
    Bib info:FOCS 2005.

  • Anupam Gupta, R. Ravi, Martin Pál, Amitabh Sinha. What about Wednesday? Approximation Algorithms for Multistage Stochastic Optimization.
    Summary: The boosted sampling framework of GPRS04 works with stochastic inflation factors and multiple stages, too.
    Bib info:APPROX 2005.

  • Anupam Gupta and Martin Pál. Stochastic Steiner Trees without a Root.
    Summary: We give the first approximation algorithm for the stochastic Steiner tree (in the two-stage stochastic framework with recourse, as in GPRS04 below) without assuming that the tree must contain a given fixed root vertex. As unrooted stochastic Steiner tree happens to generalize (deterministic) Steiner Forest and Multicommodity Rent-or-Buy, a way to the solution lies in strenghtening the strict cost sharing from our earlier MRoB paper.
    Bib info:ICALP 2005.   slides (short)

  • Moses Charikar, Chandra Chekuri and Martin Pál. Sampling for two-stage stochastic optimization with recourse.
    Summary: We look at sampling-based scenario reduction techniques for two-stage stochastic optimization with recourse. Our goal is to approximate an arbitrary probability distribution over scenarios by a discrete distribution over a small (polynomial in natural parameters of the input) number of sampled scenarios, so that good solutions to the approximate problem would turn into good solutions for the true problem. We give a couple of theorems saying that an approximation algorithm for solving a stochastic problem on a discrete distribution over an explicit list of scenarios can be used to solve this problem on an arbitrary distribution given by a sampling oracle.
    Bib info:RANDOM 2005.

  • Ara Hayrapetyan, David Kempe, Martin Pál and Zoya Svitkina. Unbalanced Graph Cuts.
    Summary: Given a graph with capacities on edges and weights on nodes, and a potentially harmful source node s, we seek to find a cut of total capacity at most B that minimizes the number (or total weight) of vertices that remain on the s side of the cut. This is a NP-hard problem, and not much is known about it (although it has many cool applications, including finding web communities). We give a (2,2) bicriteria approximation algorithm for it (find a cut of capacity 2B, that leaves twice as many vertices exposed as the optimum), and a PTAS for bounded-treewidth graphs.
    Bib info: ESA 2005. (Final project for CS 685, December 2002).

  • Retsef Levi, Martin Pál, Robin Roundy and David Shmoys. Approximation Algorithms for Stochastic Inventory Control Models.
    Bib info: IPCO 2005. First prize in the MSOM 2004 Student Paper competition.

  • Luca Becchetti, Jochen Konemann, Stefano Leonardi and Martin Pál. Sharing the cost more efficiently: Improved Approximation for Multicommodity Rent-or-Buy. (Get a copy from Jochen's homepage)
    Summary: Luca, Jochen and Stefano came up with a completely new way of analyzing (a variant of) the MRoB algorithm from the GKPR03 paper below, improving the approximation ratio to 6.83. I just selfishly note that the same improvement can be obtained by polishing the GKPR03 analysis a little bit. (More in my thesis.)
    Bib info: 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005.

  • Hubie Chen and Martin Pál. Optimization, Games, and Quantified Constraint Satisfaction.
    Summary: Since many optimization problems are NP-hard, people have often looked at algorithms that can give them approximately optimal solutions efficiently (in polynomial time). Optimizing one's return in a two-player multi-round game is a step higher in the complexity hierarchy: PSPACE-hard. We explore the possibility of designing game strategies that can be implemented by poly-time algorithms and guarantee a payoff that is at least a constant fraction of the payoff achieved by the optimal strategy.
    Bib info: 29th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2004. EATCS Best Student Paper Award.

  • Anupam Gupta, R. Ravi, Martin Pál and 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, rooted Steiner tree or Vertex Cover.
    Bib info: STOC 2004. slides

  • 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. (The conference paper gives a 12-approximation, but a slight refinement of the analysis shows approximation guarantee of 8.)
    Bib info: Proceedings of the 44th Annual IEEE Symposium on the Foundations of Computer Science, 2003. Journal version Approximation via Cost Sharing: Simpler and Better Approximation Algorithms for Network Design, in Journal of the ACM, vol. 54, no 3 (2007), pp. 11.
    slides (long version)

  • Martin Pál and É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 and Martin Pál. Universal Facility Location.
    Summary: We consider a facility location problem in which the cost of each 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 PTW01.
    Bib info: European Symposium on Algorithms, 2003. 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 9+\epsilon.
    Bib info: Proceedings of the 42nd Annual IEEE Symposium on the Foundations of Computer Science, 2001.   slides

  • Martin Pál. Cost Sharing and Approximation. (single-spaced)
    Summary: Results from PT03, GKPR03, GPRS04, GP05 and couple of smaller observations.
    Bib info: PhD dissertation, Cornell University, January 2005.

  • Alex Slivkins, Martin Pál. On Fixed-Parameter Tractability of Some Routing Problems.
    Bib info: Cornell University Technical Report TR2002-1874, 2002.

  • Martin Pál. Online and Offline Paging Algorithms.
    Summary: The optimal offline paging algorithm by Belady always evicts the page that will be requested furthest in the future. It is obviously offline in that it needs to know the sequence of future requests - but, surprisingly, there is an online algorithm that exactly predicts when the optimal algorithm faults (of course it cannot guess which page the optimal algorithm evicts). We also study online paging algorithms in models where the page request sequence is generated by programs with nested procedure calls.
    Bib info: My "magister" thesis at Comenius University, 2000.

  • Ivona Bezáková, Martin Pál. Planar Finite Automata.
    Summary: A finite automaton can be represented by a labeled directed graph. What happens if we require the graph to be planar? It turns out that every regular language has a planar non-deterministic finite automaton, although the construction requires exponential blowup in the number of states. There are languages over a two-letter alphabet that cannot be accepted by a deterministic planar finite automaton.
    Bib info: Student Science Conference, Comenius University, 1999.
Luca Becchetti
Moses Charikar
Chandra Chekuri
Hubie Chen
Jon Feldman
Anupam Gupta
Ara Hayrapetyan
David Kempe
Jochen Konemann
Nitish Korula
Amit Kumar
Stefano Leonardi
Retsef Levi
Mohammad Mahdian
Muthu Muthukrishnan
Eddie Nikolova
R. Ravi
Tim Roughgarden
Robin Roundy
David Shmoys
Amitabh Sinha
Éva Tardos
Tom Wexler
Cliff Stein
Zoya Svitkina

Last updated 18 Feb 2008