-
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
|