2024
Banihashem, K., Hajiaghayi, M., Kowalski, D. R., Krysta, P., & Olkowski, J. (2024). Power of Posted-price Mechanisms for Prophet Inequalities. In Unknown Conference (pp. 4580-4604). Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611977912.163DOI: 10.1137/1.9781611977912.163
2023
Adamson, D., Gusev, V. V., Deligkas, A., Antypov, D., Collins, C. M., Krysta, P., . . . Rosseinsky, M. J. (2023). Optimality Guarantees for Crystal Structure Prediction. Nature. doi:10.1038/s41586-023-06071-yDOI: 10.1038/s41586-023-06071-y
Chionas, G., Chlebus, B. S., Kowalski, D. R., & Krysta, P. (2023). Adversarial Contention Resolution Games. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization. doi:10.24963/ijcai.2023/289DOI: 10.24963/ijcai.2023/289
2021
Fotakis, D., Krysta, P., & Ventre, C. (n.d.). Efficient Truthful Scheduling and Resource Allocation through Monitoring. In Proceedings of the AAAI Conference on Artificial Intelligence Vol. 35 (pp. 5423-5431). Association for the Advancement of Artificial Intelligence (AAAI). doi:10.1609/aaai.v35i6.16683DOI: 10.1609/aaai.v35i6.16683
2020
Krysta, P. J., Mari, M., & Zhi, N. (2020). Ultimate greedy approximation of independent sets in subcubic graphs. In SODA '20: Proceeding of the 31st annual ACM-SIAM symposium on discrete algorithms (pp. 1436-1455). Salt Lake City, UT, USA. Retrieved from https://dl.acm.org/doi/abs/10.5555/3381089.3381176
2019
Zhi, N., Payne, T. R., Krysta, P., & li, M. (2019). Truthful Mechanisms for Multi Agent Self-Interested Correspondence Selection. In The 18th International Semantic Web Conference. Auckland, New Zealand. doi:10.1007/978-3-030-30793-6_42DOI: 10.1007/978-3-030-30793-6_42
Krysta, P., Manlove, D., Rastegari, B., & Zhang, J. (2019). Size versus truthfulness in the House Allocation problem. Algorithmica: an international journal in computer science, 81, 3422-3463. doi:10.1007/s00453-019-00584-7DOI: 10.1007/s00453-019-00584-7
Anastasiadis, E., Deng, X., Krysta, P. J., Li, M., Qiao, H., & Zhang, J. (2019). Network Pollution Games. Algorithmica: an international journal in computer science, 81(1), 124-166. doi:10.1007/s00453-018-0435-4DOI: 10.1007/s00453-018-0435-4
2018
Fotakis, D., Krysta, P., & Ventre, C. (2018). The Power of Verification for Greedy Mechanism Design. Journal of Artificial Intelligence Research, 62, 459-488. doi:10.1613/jair.1.11215DOI: 10.1613/jair.1.11215
2017
Krysta, P., Li, M., Payne, T. R., & Zhi, N. (2017). Mechanism Design for Ontology Alignment. In AAMAS '17 Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems (pp. 1587). São Paulo, Brazil.
Fotakis, D., Krysta, P., & Ventre, C. (2017). Combinatorial Auctions Without Money. Algorithmica, 77(3), 756-785. doi:10.1007/s00453-015-0105-8DOI: 10.1007/s00453-015-0105-8
2016
Krysta, P. J., & Zhang, J. (2016). House Markets with Matroid and Knapsack Constraints. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Vol. 55 (pp. 141:1-141:14). doi:10.4230/LIPIcs.ICALP.2016.141DOI: 10.4230/LIPIcs.ICALP.2016.141
Anastasiadis, E., Deng, X., Krysta, P. J., Li, M., Qiao, H., & Zhang, J. (2016). New Results for Network Pollution Games. In 22nd International Computing and Combinatorics Conference (COCOON'16).
Anastasiadis, E., Deng, X., Krysta, P., Li, M., Qiao, H., & Zhang, J. (2016). Network pollution games. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS (pp. 23-31).
2015
Krysta, P., Telelis, O., & Ventre, C. (2015). Mechanisms for Multi-unit Combinatorial Auctions with a Few Distinct Goods. JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 53, 721-744. doi:10.1613/jair.4587DOI: 10.1613/jair.4587
Krysta, P., & Ventre, C. (2015). Combinatorial auctions with verification are tractable. THEORETICAL COMPUTER SCIENCE, 571, 21-35. doi:10.1016/j.tcs.2015.01.001DOI: 10.1016/j.tcs.2015.01.001
Near-optimal approximation mechanisms for multi-unit combinatorial auctions (Conference Paper)
Krysta, P., Telelis, O., & Ventre, C. (2015). Near-optimal approximation mechanisms for multi-unit combinatorial auctions. In IJCAI International Joint Conference on Artificial Intelligence Vol. 2015-January (pp. 4275-4281).
Fotakis, D., Krysta, P., & Ventre, C. (2015). The Power of Verification for Greedy Mechanism Design. In 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015).
The power of verification for greedy mechanism design (Conference Paper)
Fotakis, D., Krysta, P., & Ventre, C. (2015). The power of verification for greedy mechanism design. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS Vol. 1 (pp. 307-315).
2014
Fotakis, D., Krysta, P., & Ventre, C. (2014). Combinatorial Auctions without money. In 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014 Vol. 2 (pp. 1029-1036).
Krysta, P., Manlove, D., Rastegari, B., & Zhang, J. (2014). Size versus truthfulness in the house allocation problem. In EC '14: Proceedings of the fifteenth ACM conference on Economics and computatio (pp. 453-470). Stanford , CA, USA. doi:10.1145/2600057.2602868DOI: 10.1145/2600057.2602868
Grandoni, F., Krysta, P., Leonardi, S., & Ventre, C. (2014). UTILITARIAN MECHANISM DESIGN FOR MULTIOBJECTIVE OPTIMIZATION. SIAM JOURNAL ON COMPUTING, 43(4), 1263-1290. doi:10.1137/130913602DOI: 10.1137/130913602
2013
Ranking games that have competitiveness-based strategies (Journal article)
Goldberg, L. A., Goldberg, P. W., Krysta, P., & Ventre, C. (2013). Ranking games that have competitiveness-based strategies. Theoretical Computer Science, 476, 24-37. doi:10.1016/j.tcs.2013.01.013DOI: 10.1016/j.tcs.2013.01.013
Mechanisms for Multi-Unit Combinatorial Auctions with a Few Distinct Goods (Conference Paper)
Krysta, P., Telelis, O., & Ventre, C. (2013). Mechanisms for Multi-Unit Combinatorial Auctions with a Few Distinct Goods. In 12th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2013) (pp. 691-698). Saint Paul, MN, USA.
2012
Stackelberg Network Pricing Games (Journal article)
Briest, P., Hoefer, M., & Krysta, P. (2012). Stackelberg Network Pricing Games. Algorithmica, 62(3-4), 733-753. doi:10.1007/s00453-010-9480-3DOI: 10.1007/s00453-010-9480-3
Limited Supply Online Auctions for Revenue Maximization (Conference Paper)
Krysta, P., & Telelis, O. (2012). Limited Supply Online Auctions for Revenue Maximization. In 8th International Workshop on Internet and Network Economics (WINE 2012) (pp. ???). Berlin: Springer-Verlag.
Online Mechanism Design (Randomized Rounding on the Fly) (Conference Paper)
Krysta, P., & Vöcking, B. (2012). Online Mechanism Design (Randomized Rounding on the Fly). In Unknown Conference (pp. 636-647). Springer Berlin Heidelberg. doi:10.1007/978-3-642-31585-5_56DOI: 10.1007/978-3-642-31585-5_56
2011
Algorithmic Game Theory (Conference Paper)
Persiano, G. (Ed.) (2011). Algorithmic Game Theory. In . Springer Berlin Heidelberg. doi:10.1007/978-3-642-24829-0DOI: 10.1007/978-3-642-24829-0
Approximation Techniques for Utilitarian Mechanism Design (Journal article)
Briest, P., Krysta, P., & Vöcking, B. (2011). Approximation Techniques for Utilitarian Mechanism Design. SIAM Journal on Computing, 40(6), 1587-1622. doi:10.1137/090772988DOI: 10.1137/090772988
Buying Cheap Is Expensive: Approximability of Combinatorial Pricing Problems (Journal article)
Briest, P., & Krysta, P. (2011). Buying Cheap Is Expensive: Approximability of Combinatorial Pricing Problems. SIAM Journal on Computing, 40(6), 1554-1586. doi:10.1137/090752353DOI: 10.1137/090752353
2010
Ranking games that have competitiveness-based strategies (Conference Paper)
Goldberg, L. A., Goldberg, P. W., Krysta, P., & Ventre, C. (2010). Ranking games that have competitiveness-based strategies. In Proceedings of the 11th ACM conference on Electronic commerce. ACM. doi:10.1145/1807342.1807396DOI: 10.1145/1807342.1807396
Utilitarian Mechanism Design for Multi-Objective Optimization (Conference Paper)
Grandoni, F., Krysta, P., Leonardi, S., & Ventre, C. (2010). Utilitarian Mechanism Design for Multi-Objective Optimization. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611973075.48DOI: 10.1137/1.9781611973075.48
Combinatorial Auctions with Verification Are Tractable (Conference Paper)
Krysta, P., & Ventre, C. (2010). Combinatorial Auctions with Verification Are Tractable. In Unknown Conference (pp. 39-50). Springer Berlin Heidelberg. doi:10.1007/978-3-642-15781-3_4DOI: 10.1007/978-3-642-15781-3_4
Combinatorial auctions with externalities (Conference Paper)
Krysta, P., Michalak, T. P., Sandholm, T., & Wooldridge, M. (2010). Combinatorial auctions with externalities. In International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS '10) (pp. 1471-1472). Atlanta: IFAAMAS. doi:10.1145/1838206.1838437DOI: 10.1145/1838206.1838437
Ranking games that have competitiveness-based strategies (Conference Paper)
Goldberg, L. A., Goldberg, P. W., Krysta, P., & Ventre, C. (2010). Ranking games that have competitiveness-based strategies. In ACM conference on Electronic commerce (pp. 335-344). Boston, USA: ACM. Retrieved from http://portal.acm.org/
Selfish Traffic Allocation for Server Farms (Journal article)
Czumaj, A., Krysta, P., & Vöcking, B. (2010). Selfish Traffic Allocation for Server Farms. SIAM Journal on Computing, 39(5), 1957-1987. doi:10.1137/070693862DOI: 10.1137/070693862
2008
Briest, P., Hoefer, M., & Krysta, P. (2008). Stackelberg Network Pricing Games. In Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (2008). Retrieved from http://arxiv.org/abs/0802.2841v1
On the Approximability of Combinatorial Exchange Problems (Conference Paper)
Babaioff, M., Briest, P., & Krysta, P. (2008). On the Approximability of Combinatorial Exchange Problems. In Unknown Conference (pp. 83-94). Springer Berlin Heidelberg. doi:10.1007/978-3-540-79309-0_9DOI: 10.1007/978-3-540-79309-0_9
Social Context Games (Conference Paper)
Ashlagi, I., Krysta, P., & Tennenholtz, M. (2008). Social Context Games. In Unknown Conference (pp. 675-683). Springer Berlin Heidelberg. doi:10.1007/978-3-540-92185-1_73DOI: 10.1007/978-3-540-92185-1_73
Utilitarian Mechanism Design for Single-Minded Agents (Chapter)
Krysta, P., & Vöcking, B. (2008). Utilitarian Mechanism Design for Single-Minded Agents. In Encyclopedia of Algorithms (pp. 997-1001). Springer US. doi:10.1007/978-0-387-30162-4_454DOI: 10.1007/978-0-387-30162-4_454
2007
An Experimental Study of the Misdirection Algorithm for Combinatorial Auctions (Conference Paper)
Knoche, J., & Krysta, P. (2007). An Experimental Study of the Misdirection Algorithm for Combinatorial Auctions. In Unknown Conference (pp. 265-278). Springer Berlin Heidelberg. doi:10.1007/11970125_21DOI: 10.1007/11970125_21
Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing (Conference Paper)
Briest, P., & Krysta, P. (2007). Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing. In ACM-SIAM Symposium on Discrete Algorithms (pp. 716-725). Philadelphia, PA: SIAM.
2006
Computing equilibria for a service provider game with (Im)perfect information (Journal article)
Beier, R., Czumaj, A., Krysta, P., & Vöcking, B. (2006). Computing equilibria for a service provider game with (Im)perfect information. ACM Transactions on Algorithms, 2(4), 679-706. doi:10.1145/1198513.1198524DOI: 10.1145/1198513.1198524
Efficient approximation algorithms for the achromatic number (Journal article)
Krysta, P., & Loryś, K. (2006). Efficient approximation algorithms for the achromatic number. Theoretical Computer Science, 361(2-3), 150-171. doi:10.1016/j.tcs.2006.05.007DOI: 10.1016/j.tcs.2006.05.007
Single-minded unlimited supply pricing on sparse instances (Conference Paper)
Briest, P., & Krysta, P. (2006). Single-minded unlimited supply pricing on sparse instances. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06. ACM Press. doi:10.1145/1109557.1109678DOI: 10.1145/1109557.1109678
2005
Approximation techniques for utilitarian mechanism design (Conference Paper)
Briest, P., Krysta, P., & Vöcking, B. (2005). Approximation techniques for utilitarian mechanism design. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. ACM. doi:10.1145/1060590.1060597DOI: 10.1145/1060590.1060597
Bicriteria Network Design via Iterative Rounding (Conference Paper)
Krysta, P. (2005). Bicriteria Network Design via Iterative Rounding. In Unknown Conference (pp. 179-187). Springer Berlin Heidelberg. doi:10.1007/11533719_20DOI: 10.1007/11533719_20
Geometric Network Design with Selfish Agents (Conference Paper)
Hoefer, M., & Krysta, P. (2005). Geometric Network Design with Selfish Agents. In Unknown Conference (pp. 167-178). Springer Berlin Heidelberg. doi:10.1007/11533719_19DOI: 10.1007/11533719_19
Greedy Approximation via Duality for Packing, Combinatorial Auctions and Routing (Conference Paper)
Krysta, P. (2005). Greedy Approximation via Duality for Packing, Combinatorial Auctions and Routing. In Unknown Conference (pp. 615-627). Springer Berlin Heidelberg. doi:10.1007/11549345_53DOI: 10.1007/11549345_53
2004
Computing equilibria for congestion games with (im)perfect information (Conference Paper)
Beier, R., Czumaj, A., Krysta, P., & Voecking, B. (2004). Computing equilibria for congestion games with (im)perfect information. In ACM-SIAM Symposium on Discrete Algorithms (pp. 746-755). Philadelphia, PA: SIAM.
2003
Approximating minimum size {1,2}-connected networks (Journal article)
Krysta, P. (2003). Approximating minimum size {1,2}-connected networks. Discrete Applied Mathematics, 125(2-3), 267-288. doi:10.1016/s0166-218x(02)00199-3DOI: 10.1016/s0166-218x(02)00199-3
An Experimental Study of k-Splittable Scheduling for DNS-Based Traffic Allocation (Conference Paper)
Agarwal, A., Agarwal, T., Chopra, S., Feldmann, A., Kammenhuber, N., Krysta, P., & Vöcking, B. (2003). An Experimental Study of k-Splittable Scheduling for DNS-Based Traffic Allocation. In Unknown Conference (pp. 230-235). Springer Berlin Heidelberg. doi:10.1007/978-3-540-45209-6_35DOI: 10.1007/978-3-540-45209-6_35
Optimizing misdirection (Conference Paper)
Berman, P., & Krysta, P. (2003). Optimizing misdirection. In ACM-SIAM Symposium on Discrete Algorithms (pp. 192-201). Philadelphia, PA: SIAM. doi:10.1145/644108.644142DOI: 10.1145/644108.644142
Scheduling and Traffic Allocation for Tasks with Bounded Splittability (Conference Paper)
Krysta, P., Sanders, P., & Vöcking, B. (2003). Scheduling and Traffic Allocation for Tasks with Bounded Splittability. In Unknown Conference (pp. 500-510). Springer Berlin Heidelberg. doi:10.1007/978-3-540-45138-9_44DOI: 10.1007/978-3-540-45138-9_44
2002
Selfish traffic allocation for server farms (Conference Paper)
Czumaj, A., Krysta, P., & Vöcking, B. (2002). Selfish traffic allocation for server farms. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. ACM. doi:10.1145/509907.509952DOI: 10.1145/509907.509952
Approximability of Dense and Sparse Instances of Minimum 2-Connectivity, TSP and Path Problems (Conference Paper)
Csaba, B., Karpinski, M., & Krysta, P. (2002). Approximability of Dense and Sparse Instances of Minimum 2-Connectivity, TSP and Path Problems. In ACM-SIAM Symposium on Discrete Algorithms (pp. 74-83). Philadelphia, PA: SIAM. doi:10.1145/545381.545390DOI: 10.1145/545381.545390
2001
(Journal article)
Krysta, P., & Solis-Oba, R. (2001). Unknown Title. Journal of Combinatorial Optimization, 5(2), 233-247. doi:10.1023/a:1011465419252DOI: 10.1023/a:1011465419252
Approximation Algorithms for Minimum Size 2-Connectivity Problems (Conference Paper)
Krysta, P., & Kumar, V. S. A. (2001). Approximation Algorithms for Minimum Size 2-Connectivity Problems. In Unknown Conference (pp. 431-442). Springer Berlin Heidelberg. doi:10.1007/3-540-44693-1_38DOI: 10.1007/3-540-44693-1_38
1999
The STO problem is NP-complete (Journal article)
Krysta, P., & Pacholski, L. (1999). The STO problem is NP-complete. Journal of Symbolic Computation, 27(2), 207-219. doi:10.1006/jsco.1998.0249DOI: 10.1006/jsco.1998.0249
Approximation Algorithms for Bounded Facility Location (Conference Paper)
Krysta, P., & Solis-Oba, R. (1999). Approximation Algorithms for Bounded Facility Location. In Unknown Conference (pp. 241-250). Springer Berlin Heidelberg. doi:10.1007/3-540-48686-0_24DOI: 10.1007/3-540-48686-0_24
Efficient Approximation Algorithms for the Achromatic Number (Conference Paper)
Krysta, P., & Loryś, K. (1999). Efficient Approximation Algorithms for the Achromatic Number. In Unknown Conference (pp. 402-413). Springer Berlin Heidelberg. doi:10.1007/3-540-48481-7_35DOI: 10.1007/3-540-48481-7_35
1997
External inverse pattern matching (Conference Paper)
Gasieniec, L., Indyk, P., & Krysta, P. (1997). External inverse pattern matching. In Unknown Conference (pp. 90-101). Springer Berlin Heidelberg. doi:10.1007/3-540-63220-4_53DOI: 10.1007/3-540-63220-4_53