Martin Pál

SODA Conference 2009 Conference Paper

An online mechanism for ad slot reservations with cancellations

• Florin Constantin
• Jon Feldman
• S. Muthukrishnan 0001
• Martin Pál

SODA Conference 2008 Conference Paper

Improved algorithms for orienteering and related problems

• Chandra Chekuri
• Nitish Korula
• Martin Pál

FOCS Conference 2005 Conference Paper

A Recursive Greedy Algorithm for Walks in Directed Graphs

• Chandra Chekuri
• Martin Pál

Given an arc-weighted directed graph G = (V, A, /spl lscr/) and a pair of nodes s, t, we seek to find an s-t walk of length at most B that maximizes some given function f of the set of nodes visited by the walk. The simplest case is when we seek to maximize the number of nodes visited: this is called the orienteering problem. Our main result is a quasi-polynomial time algorithm that yields an O(log OPT) approximation for this problem when f is a given submodular set function. We then extend it to the case when a node v is counted as visited only if the walk reaches v in its time window [R(v), D(v)]. We apply the algorithm to obtain several new results. First, we obtain an O(log OPT) approximation for a generalization of the orienteering problem in which the profit for visiting each node may vary arbitrarily with time. This captures the time window problem considered earlier for which, even in undirected graphs, the best approximation ratio known [Bansal, N et al. (2004)] is O(log/sup 2/ OPT). The second application is an O(log/sup 2/ k) approximation for the k-TSP problem in directed graphs (satisfying asymmetric triangle inequality). This is the first non-trivial approximation algorithm for this problem. The third application is an O(log/sup 2/ k) approximation (in quasi-poly time) for the group Steiner problem in undirected graphs where k is the number of groups. This improves earlier ratios (Garg, N et al.) by a logarithmic factor and almost matches the inapproximability threshold on trees (Halperin and Krauthgamer, 2003). This connection to group Steiner trees also enables us to prove that the problem we consider is hard to approximate to a ratio better than /spl Omega/(log/sup 1-/spl epsi// OPT), even in undirected graphs. Even though our algorithm runs in quasi-poly time, we believe that the implications for the approximability of several basic optimization problems are interesting.

SODA Conference 2005 Conference Paper

Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy

• Luca Becchetti
• Jochen Könemann
• Stefano Leonardi 0001
• Martin Pál

STOC Conference 2004 Conference Paper

Boosted sampling: approximation algorithms for stochastic optimization

• Anupam Gupta 0001
• Martin Pál
• R. Ravi 0001
• Amitabh Sinha

Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies requirements of clients. In the Steiner Tree problem, for example, edges must be chosen to connect terminals (clients); in Vertex Cover, vertices must be chosen to cover edges (clients); in Facility Location, facilities must be chosen and demand vertices (clients) connected to these chosen facilities. We consider a stochastic version of such a problem where the solution is constructed in two stages: Before the actual requirements materialize, we can choose elements in a first stage. The actual requirements are then revealed, drawn from a pre-specified probability distribution π thereupon, some more elements may be chosen to obtain a feasible solution for the actual requirements. However, in this second (recourse) stage, choosing an element is costlier by a factor of σ> 1. The goal is to minimize the first stage cost plus the expected second stage cost.We give a general yet simple technique to adapt approximation algorithms for several deterministic problems to their stochastic versions via the following method. First stage: Draw σ independent sets of clients from the distribution π and apply the approximation algorithm to construct a feasible solution for the union of these sets. Second stage: Since the actual requirements have now been revealed, augment the first-stage solution to be feasible for these requirements. We use this framework to derive constant factor approximations for stochastic versions of Vertex Cover, Steiner Tree and Uncapacitated Facility Location for arbitrary distributions π in one fell swoop. For special (product) distributions, we obtain additional and improved results. Our techniques adapt and use the notion of strict cost-shares introduced in [5].

MFCS Conference 2004 Conference Paper

Optimization, Games, and Quantified Constraint Satisfaction

• Hubie Chen
• Martin Pál

Abstract Optimization problems considered in the literature generally assume a passive environment that does not react to the actions of an agent. In this paper, we introduce and study a class of optimization problems in which the environment plays an active, adversarial role and responds dynamically to the actions of an agent; this class of problems is based on the framework of quantified constraint satisfaction. We formalize a new notion of approximation algorithm for these optimization problems, and consider certain restricted versions of the general problem obtained by restricting the types of constraints that may appear. Our main result is a dichotomy theorem classifying exactly those restricted versions having a constant factor approximation algorithm.

FOCS Conference 2003 Conference Paper

Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem

• Anupam Gupta 0001
• Amit Kumar 0001
• Martin Pál
• Tim Roughgarden

We study the multicommodity rent-or-buy problem, a type of network design problem with economies of scale. In this problem, capacity on an edge can be rented, with cost incurred on a per-unit of capacity basis, or bought, which allows unlimited use after payment of a large fixed cost. Given a graph and a set of source-sink pairs, we seek a minimum-cost way of installing sufficient capacity on edges so that a prescribed amount of flow can be sent simultaneously from each source to the corresponding sink. The first constant-factor approximation algorithm for this problem was recently given by Kumar et al. ; however, this algorithm and its analysis are both quite complicated, and its performance guarantee is extremely large. In this paper, we give a conceptually simple 12-approximation algorithm for this problem. Our analysis of this algorithm makes crucial use of cost sharing, the task of allocating the cost of an object to many users of the object in a "fair" manner. While techniques from approximation algorithms have recently yielded new progress on cost sharing problems, our work is the first to show the converse - those ideas from cost sharing can be fruitfully applied in the design and analysis of approximation algorithms.

FOCS Conference 2003 Conference Paper

Group Strategyproof Mechanisms via Primal-Dual Algorithms

• Martin Pál
• Éva Tardos

We develop a general method for turning a primal-dual algorithm into a group strategy proof cost-sharing mechanism. We use our method to design approximately budget balanced cost sharing mechanisms for two NP-complete problems: metric facility location, and single source rent-or-buy network design. Both mechanisms are competitive, group strategyproof and recover a constant fraction of the cost. For the facility location game our cost-sharing method recovers a 1/3rd of the total cost, while in the network design game the cost shares pay for a 1/15 fraction of the cost of the solution.

FOCS Conference 2001 Conference Paper

Facility Location with Nonuniform Hard Capacities

• Martin Pál
• Éva Tardos
• Tom Wexler

The authors give the first constant factor approximation algorithm for the facility location problem with nonuniform, hard capacities. Facility location problems have received a great deal of attention in recent years. Approximation algorithms have been developed for many variants. Most of these algorithms are based on linear programming, but the LP techniques developed thus far have been unsuccessful in dealing with hard capacities. A local-search based approximation algorithm (M. Korupolu et al. , 1998; F. A. Chudak and D. P. Williamson, 1999) is known for the special case of hard but uniform capacities. We present a local-search heuristic that yields an approximation guarantee of 9 + /spl epsi/ for the case of nonuniform hard capacities. To obtain this result, we introduce new operations that are natural in this context. Our proof is based on network flow techniques.