Piotr Krysta - List of publications




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. To appear.


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. To appear.


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.