Piotr
Krysta - List of publications
Preprints and
working papers
Dimitris Fotakis,
Vasilis Kontonis, Piotr Krysta and Paul G. Spirakis. Learning Powers of Poisson Binomial
Distributions. ArXiv, CoRR abs/1707.05662, 2017.
Dimitris Fotakis,
Vasilis Kontonis, Piotr Krysta and Paul G. Spirakis. Learning the distribution of edges in graphs
whose vertices may fail. Manuscript, 2018.
2021
Dimitris Fotakis,
Piotr Krysta and Carmine Ventre. Efficient truthful scheduling and resource allocation through monitoring. In the Proceedings
of The 35th AAAI Conference on Artificial Intelligence
(AAAI '21), 2021. Accepted for publication.
2020
Piotr Krysta, Mathieu Mari and
Nan Zhi. Ultimate greedy approximation of independent
sets in subcubic graphs. In the Proceedings
of The 31st ACM-SIAM Symposium on Discrete Algorithms
(SODA '20), 2020.
2019
Piotr Krysta, David Manlove, Baharak Rastegari and Jinshan Zhang. Size
versus truthfulness in the House Allocation problem. Algorithmica,
81(9): 3422-3463, 2019.
Eleftherios
Anastasiadis, Xiaotie Deng,
Piotr Krysta, Minming Li, Han Qiao
and Jinshan Zhang. Network Pollution Games. Algorithmica, 81(1): 124-166, 2019.
2018
Dimitris Fotakis, Piotr Krysta
and Carmine Ventre. The Power of Verification for
Greedy Mechanism Design. Journal of Artificial Intelligence Research,
62: 459-488, 2018.
2017
Dimitris Fotakis,
Piotr Krysta and Carmine Ventre. Combinatorial
Auctions without Money. Algorithmica,
77(3): 756-785, 2017.
Piotr Krysta, Minming
Li, Terry R. Payne and Nan Zhi. Mechanism Design
for Ontology Alignment. In the Proceedings of the 16th Conference on
Autonomous Agents and Multi-Agent Systems (AAMAS '17), 2017.
2016
Piotr Krysta and Jinshan Zhang. House Markets with Matroid
and Knapsack Constraints. In the Proceedings of the 43rd International
Colloquium on Automata, Languages and Programming (ICALP '16), 2016.
Eleftherios
Anastasiadis, Xiaotie Deng,
Piotr Krysta, Minming Li, Han Qiao,
Jinshan Zhang. New Results for Network Pollution
Games. In the Proceedings of the 22nd Annual International Conference on
Computing and Combinatorics (COCOON '16),
2016.
Eleftherios
Anastasiadis, Xiaotie Deng,
Piotr Krysta, Minming Li, Han Qiao,
Jinshan Zhang. Network Pollution Games. In the
Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS '16), pp. 23-31, 2016.
2015
Piotr Krysta, Orestis
Telelis, Carmine Ventre. Near-Optimal
Approximation Mechanisms for Multi-Unit Combinatorial Auctions. In the Proceedings
of the 24th International Joint Conference on Artificial Intelligence (IJCAI
'15), pp. 4275-4281, AAAI Press, 2015.
Dimitris Fotakis,
Piotr Krysta and Carmine Ventre. The Power of
Verification for Greedy Mechanism Design. In the Proceedings of the 14th
International Conference on Autonomous Agents and Multiagent
Systems (AAMAS '15), pp. 307-315, 2015.
Piotr Krysta and Carmine Ventre. Combinatorial auctions with verification are
tractable. Theoretical Computer Science, 571: 21-35, 2015.
Piotr Krysta, Orestis
Telelis, Carmine Ventre. Mechanisms
for Multi-unit Combinatorial Auctions with a Few Distinct Goods. Journal
of Artificial Intelligence Research (JAIR), 53: 721-744, 2015.
2014
Piotr Krysta, David Manlove, Baharak Rastegari and Jinshan Zhang. Size
versus truthfulness in the House Allocation problem. In the Proceedings
of the 15th ACM Conference on Economics and Computation (EC '14),
2014.
Dimitris Fotakis,
Piotr Krysta and Carmine Ventre. Combinatorial
Auctions without Money. In the Proceedings of the 13th International
Conference on Autonomous Agents and Multiagent Systems
(AAMAS '14), 2014. Also available in ArXiv.
Fabrizio Grandoni, Piotr Krysta,
Stefano Leonardi, Carmine Ventre.
Utilitarian Mechanism Design for Multiobjective
Optimization. SIAM Journal on Computing, 43(4): 1263-1290, 2014.
2013
Piotr Krysta, Orestis Telelis and Carmine Ventre. Mechanisms for Multi-Unit Combinatorial Auctions
with a Few Distinct Goods. In the Proceedings of the 12th International
Conference on Autonomous Agents and Multiagent
Systems (AAMAS '13), 2013. Best paper
award of AAMAS 2013.
Leslie
Goldberg, Paul Goldberg, Piotr Krysta and Carmine Ventre.
Ranking Games that have Competitiveness-based Strategies. Theoretical
Computer Science, 476: 24-37, March, 2013.
2012
Piotr Krysta
and Orestis Telelis. Limited
Supply Online Auctions for Revenue Maximization. In the Proceedings of
the 8th International Workshop on Internet and Network Economics (WINE
'12), 2012.
Piotr Krysta,
and Berthold Vöcking. Online Mechanism Design
(Randomized Rounding on the Fly). In the Proceedings of the 39th
International Colloquium on Automata, Languages and Programming (ICALP
'12), 2012. Best paper award for "Track C:
Foundations of Networked Computation" of ICALP 2012.
Patrick Briest, Martin Hoefer and Piotr
Krysta. Stackelberg Network Pricing Games. Algorithmica, 62(3-4): 733-753, 2012.
2011
Patrick Briest, and Piotr Krysta. Buying Cheap is Expensive: Approximability of Combinatorial Pricing Problems. SIAM
Journal on Computing, 40(6): 1554-1586, December, 2011.
Patrick Briest, Piotr Krysta, and Berthold Vöcking.
Approximation Techniques for Utilitarian Mechanism Design. SIAM
Journal on Computing, 40(6): 1587-1622, December, 2011.
Dimitris Fotakis, Piotr Krysta and Orestis
Telelis. Externalities among Advertisers in
Sponsored Search. In the Proceedings of the 4th International Symposium
on Algorithmic Game Theory (SAGT '11), 2011.
2010
Artur Czumaj, Piotr Krysta, and
Berthold Vöcking. Selfish Traffic Allocation
for Server Farms. SIAM Journal on Computing, 39(5): 1957-1987,
February, 2010.
Piotr Krysta
and Carmine Ventre. Combinatorial Auctions with
Verification are Tractable. In the Proceedings of The
18th Annual European Symposium on Algorithms (ESA '10), 2010.
Piotr Krysta,
Tomasz Michalak, Tuomas Sandholm and Michael Wooldridge. Combinatorial Auctions
with Externalities. In the Proceedings of The
9th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS
'10), 2010. (short paper)
Leslie
Goldberg, Paul Goldberg, Piotr Krysta and Carmine Ventre.
Ranking Games that have Competitiveness-based Strategies. In the Proceedings
of The 11th ACM Conference on Electronic Commerce (EC
'10), 2010.
Fabrizio Grandoni, Piotr Krysta,
Stefano Leonardi and Carmine Ventre.
Utilitarian Mechanism Design for Multi-Objective Optimization. In the Proceedings
of The 21st ACM-SIAM Symposium on Discrete Algorithms
(SODA '10), 2010.
2008
Piotr Krysta
and Berthold Vöcking. Utilitarian Mechanism Design
for Single-Minded Agents. In Encyclopedia of Algorithms
2008 (Ming-Yang Kao, Editor), Springer, 2008.
Itai Ashlagi, Piotr Krysta and
Moshe Tennenholtz. Social Context Games. In
the Proceedings of the 4th International Workshop on Internet and Network
Economics (WINE '08), 2008.
Moshe Babaioff, Patrick Briest and
Piotr Krysta. On the Approximability of
Combinatorial Exchange Problems. In the Proceedings of the 1st
International Symposium on Algorithmic Game Theory (SAGT '08), 2008.
Patrick Briest, Martin Hoefer and Piotr
Krysta. Stackelberg Network Pricing Games. In
the Proceedings of The 25th International Symposium
on Theoretical Aspects of Computer Science (STACS '08), 2008.
2007
Patrick Briest and Piotr Krysta. Buying Cheap is Expensive:
Hardness of Non-Parametric Multi-Product Pricing. In the Proceedings of
The 18th ACM-SIAM Symposium on Discrete Algorithms
(SODA '07), 2007. Also appeared as ECCC Technical
Report No. TR06-068, 2006.
2006
Rene
Beier, Artur Czumaj, Piotr Krysta, and Berthold Vöcking.
Computing Equilibria for Congestion Games with (Im)perfect Information. ACM Transactions on Algorithms,
2(4): 679-706, October, 2006. Special issue of the journal devoted to selected
papers from SODA'04.
Piotr
Krysta and Krzysztof Lorys. Efficient
Approximation Algorithms for the Achromatic Number. Theoretical
Computer Science, 361: 150-171, September, 2006. Special issue on
approximation and on-line algorithms.
Jörg Knoche and Piotr
Krysta. An Experimental Study of the Misdirection Algorithm for
Combinatorial Auctions. In the Proceedings of The
4th Workshop on Approximation and Online Algorithms (WAOA '06),
2006. PS file
PDF file ©
Patrick Briest and Piotr Krysta. Single-Minded Unlimited Supply
Pricing on Sparse Instances. In the Proceedings of The
17th ACM-SIAM Symposium on Discrete Algorithms (SODA '06), 2006. PS file PDF file
©
2005
Piotr Krysta.
Greedy Approximation via Duality for Packing, Combinatorial Auctions and
Routing. In the Proceedings of The 30th
International Symposium on Mathematical Foundations of Computer Science (MFCS
'05), 2005. PS file
PDF
file ©
Piotr
Krysta. Bicriteria Network Design via Iterative
Rounding. In the Proceedings of The 11th
International Computing and Combinatorics Conference
(COCOON '05), 2005. PS file
PDF
file ©
Martin Hoefer and Piotr Krysta.
Geometric Network Design with Selfish Agents. In the Proceedings of The 11th International Computing and Combinatorics
Conference (COCOON '05), 2005. PS file
PDF
file ©
Patrick Briest, Piotr Krysta and
Berthold Vöcking. Approximation Techniques for
Utilitarian Mechanism Design. In the Proceedings of The 37th ACM Symposium
on Theory of Computing (STOC '05), 2005. PS file
PDF
file ©
2004
Rene Beier, Artur
Czumaj, Piotr Krysta and Berthold Vöcking.
Computing Equilibria for Congestion Games with (Im)perfect Information. In the Proceedings of The 15th ACM-SIAM Symposium on Discrete Algorithms (SODA
'04), 2004. PS
file PDF
file ©
2003
Piotr Krysta. Approximating Minimum Size {1,2}-Connected Networks. Discrete Applied Mathematics,
125: 267-288, January, 2003.
Piotr Krysta, Peter Sanders and Berthold Vöcking.
Scheduling and Traffic Allocation for Tasks with Bounded Splittability.
In the Proceedings of The 28th International
Symposium on Mathematical Foundations of Computer Science (MFCS
'03), 2003. PS file
PDF
file ©
Amit Agarwal, Tarun Agarwal, Sumit Chopra, Anja Feldmann, Nils Kammenhuber, Piotr
Krysta and Berthold Vöcking. An Experimental
Study of Different Strategies for DNS-Based Load Balancing. In the Proceedings
of The 9th International Conference on Parallel and
Distributed Computing (EUROPAR '03), 2003.
Piotr Berman and Piotr Krysta. Optimizing misdirection. In
the Proceedings of The 14th ACM-SIAM Symposium on
Discrete Algorithms (SODA '03), 2003. PS file
PDF
file ©
2002
Artur Czumaj,
Piotr Krysta and Berthold Vöcking. Selfish
Traffic Allocation for Server Farms. In the Proceedings of The 34th ACM
Symposium on Theory of Computing (STOC '02), 2002. PS
file PDF
file ©
Bela Csaba, Marek Karpinski and Piotr Krysta. Approximability
of Dense and Sparse Instances of Minimum 2-Connectivity, TSP and Path Problems.
In the Proceedings of The 13th ACM-SIAM Symposium
on Discrete Algorithms (SODA '02), 2002. PS file
PDF
file ©
2001
Piotr Krysta and Roberto Solis-Oba. Approximation
Algorithms for Bounded Facility Location. Journal of Combinatorial
Optimization, 5(2): 233-247, June, 2001.
Piotr Krysta and V.S. Anil Kumar. Approximation Algorithms
for Minimum Size 2-Connectivity Problems. In the Proceedings of The 18th International Symposium on Theoretical Aspects of
Computer Science (STACS '01), 2001.
1999
Piotr Krysta and Leszek Pacholski. The STO-problem is NP-complete. Journal
of Symbolic Computation, 27(2): 207-219, February, 1999.
Piotr Krysta and Krzysztof Lorys.
Efficient Approximation Algorithms for the Achromatic Number. In the Proceedings
of The 7th Annual European Symposium on Algorithms (ESA
'99), 1999.
Piotr Krysta and Roberto Solis-Oba. Approximation Algorithms
for Bounded Facility Location. In the Proceedings of The
5th Annual International Computing and Combinatorics
Conference (COCOON '99), 1999.
--1999
Leszek Gasieniec,
Piotr Indyk and Piotr Krysta. External Inverse
Pattern Matching. In the Proceedings of The 8th Annual Symposium on
Combinatorial Pattern Matching (CPM '97), 1997.
Piotr
Krysta. Solving Functional Equations. Pi Mu Epsilon Journal,
9(10), Fall, 1994.
©
Copyright Notice:
The documents distributed by this server have been provided by the contributing
authors as a means to ensure timely dissemination of scholarly and technical
work on a noncommercial basis. Copyright and all
rights therein are maintained by the authors or by other copyright holders,
notwithstanding that they have offered their works here electronically. It is
understood that all persons copying this information will adhere to the terms
and constraints invoked by each author's copyright. These works may not be
reposted without the explicit permission of the copyright holder.