Martin Pál graduated from Comenius University in Slovakia ("mgr." '00) and Cornell University (PhD '04). He held a postdoc at Rutgers and Bell Labs in '04/'05, and has been working as an engineer at Google since then.
Martin's interests include approximation algorithms, combinatorial optimization, auctions and game theory.
“Showing Relevant Ads via Lipschitz Context Multi-Armed Bandits”, Tyler Lu, Dávid Pál, Martin Pál, Thirteenth International Conference on Artificial Intelligence and Statistics, 2010.
[abstract] [jmlr.csail.mit.edu] [pdf] [search]
“Algorithms for Secretary Problems on Graphs and Hypergraphs”, Nitish Korula, Martin Pál, ICALP 2009.
[abstract] [front.math.ucdavis.edu] [search]
“An Online Mechanism for Ad Slot Reservations with Cancellations”, Florin Constantin, Jon Feldman, S. Muthukrishnan, Martin Pal, Fourth Workshop on Ad Auctions; Symposium on Discrete Algorithms (SODA), 2009.
[arxiv.org] [search]
“General Auction Mechanism for Search Advertising”, Gagan Aggarwal, S. Muthukrishnan, Dávid Pál, Martin Pál, WWW 2009.
[front.math.ucdavis.edu] [search]
“Online Ad Assignment with Free Disposal”, Jon Feldman, Nitish Korula, Vahab S. Mirrokni, S. Muthukrishnan, Martin Pál, Workshop of Internet Economics (WINE), 2009, pp. 374-385.
[doi] [search]
“A Truthful Mechanism for Offline Ad Slot Scheduling”, Jon Feldman, S. Muthukrishnan, Evdokia Nikolova, Martin Pal, Symposium on Algorithmic Game Theory, 2008.
[front.math.ucdavis.edu] [pdf] [search]
“Improved Algorithms for Orienteering and Related Problems”, Chandra Chekuri, Nitish Korula, Martin Pál, Proc. 19th Annual Symposium on Discrete Algorithms (SODA), 2008.
[cs.uiuc.edu] [pdf] [search]
“Sponsored Search Auctions for Markovian Users”, Gagan Aggarwal, Jon Feldman, Martin Pal, S. Muthukrishnan, Fourth Workshop on Ad Auctions; Workshop on Internet and Network Economics (WINE)., 2008.
[arxiv.org] [search]
“Theory research at Google”, Gagan Aggarwal, Nir Ailon, Florin Constantin, Eyal Even-Dar, Jon Feldman, Gereon Frahling, Monika R. Henzinger, S. Muthukrishnan, Noam Nisan, Martin Pál, Mark Sandler, Anastasios Sidiropoulos, SIGACT News, vol. 39 (2008), pp. 10-28.
[doi.acm.org] [search]
“Approximation via Cost Sharing: Simpler and Better Approximation Algorithms for Network Design”, Anupam Gupta, Amit Kumar, Martin Pál, Tim Roughgarden, Journal of the ACM, vol. 54, no 3 (2007), pp. 11.
[doi.acm.org] [search]
“Budget Optimization in Search-Based Advertising Auctions”, Jon Feldman, S. Muthukrishnan, Martin Pál, Cliff Stein, Proc. ACM Conference on Electronic Commerce, 2007.
[search]
“Maximizing a Submodular Set Function subject to a Matroid Constraint”, Chandra Chekuri, Gruia Calinescu, Martin Pál, Jan Vondrák, Proceedings of the Twelfth Conference on Integer Programming and Combinatorial Optimization (IPCO) 2007.
[cs.uiuc.edu] [search]
“Sharing the cost more efficiently: Improved approximation for multicommodity rent-or-buy”, L. Becchetti, J. Könemann, S. Leonardi, Martin Pál, ACM Transactions on Algorithms, vol. 3, no 2 (2007), pp. 23.
[doi.acm.org] [search]
“Stochastic Models for Budget Optimization in Search-Based Advertising”, S. Muthukrishnan, Martin Pál, Zoya Svitkina, Internet and Network Economics (WINE), 2007, pp. 131-142.
[search]
“An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem”, Chandra Chekuri, Martin Pál, Proceedings of APPROX 2006.
[search]