Publications

Filter publications

What type of publication do you want to show?

All

Journals

Conference papers

Chapters

Books

Other

2024

Ultimate Greedy Approximation of Independent Sets in Subcubic Graphs

Krysta, P., Mari, M., & Zhi, N. (2024). Ultimate Greedy Approximation of Independent Sets in Subcubic Graphs. Algorithmica, 86(11), 3518-3578. doi:10.1007/s00453-024-01268-7

DOI: 10.1007/s00453-024-01268-7
: Journal article

First Order Methods for Geometric Optimization of Crystals: Experimental Analysis

Tsili, A., Dyer, M. S., Gusev, V. V., Krysta, P., & Savani, R. (n.d.). First Order Methods for Geometric Optimization of Crystals: Experimental Analysis. Advanced Theory and Simulations. doi:10.1002/adts.202400124

DOI: 10.1002/adts.202400124
: Journal article

First Order Methods for Geometric Optimization of Crystals: Theoretical Derivations

Tsili, A., Dyer, M. S., Gusev, V. V., Krysta, P., & Savani, R. (n.d.). First Order Methods for Geometric Optimization of Crystals: Theoretical Derivations. Advanced Theory and Simulations. doi:10.1002/adts.202400125

DOI: 10.1002/adts.202400125
: Journal article

Who gets the Maximal Extractable Value? A Dynamic Sharing Blockchain Mechanism

Braga, P., Chionas, G., Krysta, P., Leonardos, S., Piliouras, G., & Ventre, C. (2024). Who gets the Maximal Extractable Value? A Dynamic Sharing Blockchain Mechanism. In AAMAS '24: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems.

: Conference Paper

MEV Sharing with Dynamic Extraction Rates

: Preprint

Power of Posted-price Mechanisms for Prophet Inequalities

Banihashem, K., Hajiaghayi, M., Kowalski, D., Krysta, P., & Olkowski, J. (2024). Power of Posted-price Mechanisms for Prophet Inequalities. In Proceedings 35th ACM-SIAM Symposium on Discrete Algorithms (SODA 2024).

: Conference Paper

Online Sampling and Decision Making with Low Entropy

Hajiaghayi, M. T., Kowalski, D. R., Krysta, P., & Olkowski, J. (2024). Online Sampling and Decision Making with Low Entropy. In Proceedings of the Thirty-ThirdInternational Joint Conference on Artificial Intelligence (pp. 4080-4088). International Joint Conferences on Artificial Intelligence Organization. doi:10.24963/ijcai.2024/451

DOI: 10.24963/ijcai.2024/451
: Conference Paper

Power of Posted-price Mechanisms for Prophet Inequalities

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

: Conference Paper

2023

Optimality Guarantees for Crystal Structure Prediction

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

DOI: 10.1038/s41586-023-06071-y
: Journal article

First Order Methods for Geometric Optimization of Crystal Structures

: Preprint

Adversarial Contention Resolution Games

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 (pp. 2598-2606). International Joint Conferences on Artificial Intelligence Organization. doi:10.24963/ijcai.2023/289

DOI: 10.24963/ijcai.2023/289
: Conference Paper

Combinatorial Group Testing with Selfish Agents

Chionas, G., Kowalski, D. R., & Krysta, P. (2023). Combinatorial Group Testing with Selfish Agents. In Advances in Neural Information Processing Systems Vol. 36.

: Conference Paper

2022

Optimal Algorithms for Free Order Multiple-Choice Secretary

DOI: 10.48550/arxiv.2207.10703
: Preprint

2021

Online Sampling and Decision Making with Low Entropy

: Preprint

Efficient Truthful Scheduling and Resource Allocation through Monitoring

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

DOI: 10.1609/aaai.v35i6.16683
: Conference Paper

2020

Ultimate greedy approximation of independent sets in subcubic graphs

DOI: 10.48550/arxiv.2001.11997
: Preprint

Ultimate greedy approximation of independent sets in subcubic graphs

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

: Conference Paper

2019

Truthful Mechanisms for Multi Agent Self-Interested Correspondence Selection

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_42

DOI: 10.1007/978-3-030-30793-6_42
: Conference Paper

Size versus truthfulness in the House Allocation problem

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

DOI: 10.1007/s00453-019-00584-7
: Journal article

Network Pollution Games

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

DOI: 10.1007/s00453-018-0435-4
: Journal article

2018

The Power of Verification for Greedy Mechanism Design

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

DOI: 10.1613/jair.1.11215
: Journal article

2017

Learning Powers of Poisson Binomial Distributions

DOI: 10.48550/arxiv.1707.05662
: Preprint

Mechanism Design for Ontology Alignment

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.

: Conference Paper

Combinatorial Auctions Without Money

Fotakis, D., Krysta, P., & Ventre, C. (2017). Combinatorial Auctions Without Money. Algorithmica, 77(3), 756-785. doi:10.1007/s00453-015-0105-8

DOI: 10.1007/s00453-015-0105-8
: Journal article

2016

House Markets with Matroid and Knapsack Constraints

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

DOI: 10.4230/LIPIcs.ICALP.2016.141
: Conference Paper

New Results for Network Pollution Games

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

: Conference Paper

Network Pollution Games

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

: Conference Paper

Utilitarian Mechanism Design for Single-Minded Agents

Krysta, P., & Vöcking, B. (2016). Utilitarian Mechanism Design for Single-Minded Agents. In Encyclopedia of Algorithms (pp. 2312-2318). Springer New York. doi:10.1007/978-1-4939-2864-4_454

DOI: 10.1007/978-1-4939-2864-4_454
: Chapter

2015

Mechanisms for Multi-unit Combinatorial Auctions with a Few Distinct Goods

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

DOI: 10.1613/jair.4587
: Journal article

Combinatorial auctions with verification are tractable

Krysta, P., & Ventre, C. (2015). Combinatorial auctions with verification are tractable. THEORETICAL COMPUTER SCIENCE, 571, 21-35. doi:10.1016/j.tcs.2015.01.001

DOI: 10.1016/j.tcs.2015.01.001
: Journal article

Near-optimal approximation mechanisms for multi-unit combinatorial auctions

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

: Conference Paper

The Power of Verification for Greedy Mechanism Design

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

: Conference Paper

The power of verification for greedy mechanism design

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

: Conference Paper

2014

Size versus truthfulness in the House Allocation problem

DOI: 10.48550/arxiv.1404.5245
: Preprint

Combinatorial Auctions without money

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

: Conference Paper

Size versus truthfulness in the house allocation problem

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

DOI: 10.1145/2600057.2602868
: Conference Paper

UTILITARIAN MECHANISM DESIGN FOR MULTIOBJECTIVE OPTIMIZATION

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

DOI: 10.1137/130913602
: Journal article

2013

Combinatorial Auctions without Money

DOI: 10.48550/arxiv.1310.0177
: Preprint

Ranking games that have competitiveness-based strategies

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

DOI: 10.1016/j.tcs.2013.01.013
: Journal article

Ranking Games that have Competitiveness-based Strategies

DOI: 10.48550/arxiv.1301.5844
: Preprint

Mechanisms for Multi-Unit Combinatorial Auctions with a Few Distinct Goods

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.

: Conference Paper

2012

Stackelberg Network Pricing Games

Briest, P., Hoefer, M., & Krysta, P. (2012). Stackelberg Network Pricing Games. Algorithmica, 62(3-4), 733-753. doi:10.1007/s00453-010-9480-3

DOI: 10.1007/s00453-010-9480-3
: Journal article

Limited Supply Online Auctions for Revenue Maximization

Krysta, P., & Telelis, O. (2012). Limited Supply Online Auctions for Revenue Maximization. In Lecture Notes in Computer Science (pp. 519-525). Springer Berlin Heidelberg. doi:10.1007/978-3-642-35311-6_41

DOI: 10.1007/978-3-642-35311-6_41
: Chapter

Limited Supply Online Auctions for Revenue Maximization

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.

: Conference Paper

Online Mechanism Design (Randomized Rounding on the Fly)

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_56

DOI: 10.1007/978-3-642-31585-5_56
: Conference Paper

2011

Algorithmic Game Theory

Persiano, G. (Ed.) (2011). Algorithmic Game Theory. In . Springer Berlin Heidelberg. doi:10.1007/978-3-642-24829-0

DOI: 10.1007/978-3-642-24829-0
: Conference Paper

Approximation Techniques for Utilitarian Mechanism Design

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

DOI: 10.1137/090772988
: Journal article

Buying Cheap Is Expensive: Approximability of Combinatorial Pricing Problems

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

DOI: 10.1137/090752353
: Journal article

Externalities among Advertisers in Sponsored Search

Fotakis, D., Krysta, P., & Telelis, O. (2011). Externalities among Advertisers in Sponsored Search. In Lecture Notes in Computer Science (pp. 105-116). Springer Berlin Heidelberg. doi:10.1007/978-3-642-24829-0_11

DOI: 10.1007/978-3-642-24829-0_11
: Chapter

2010

Ranking games that have competitiveness-based strategies

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 (pp. 335-344). ACM. doi:10.1145/1807342.1807396

DOI: 10.1145/1807342.1807396
: Conference Paper

Utilitarian Mechanism Design for Multi-Objective Optimization

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 (pp. 573-584). Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611973075.48

DOI: 10.1137/1.9781611973075.48
: Conference Paper

Combinatorial Auctions with Verification Are Tractable

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_4

DOI: 10.1007/978-3-642-15781-3_4
: Conference Paper

Combinatorial auctions with externalities

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

DOI: 10.1145/1838206.1838437
: Conference Paper

Ranking games that have competitiveness-based strategies

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/

: Conference Paper

Selfish Traffic Allocation for Server Farms

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

DOI: 10.1137/070693862
: Journal article

2008

Stackelberg Network Pricing Games

DOI: 10.48550/arxiv.0802.2841
: Preprint

Stackelberg Network Pricing Games

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

: Conference Paper

On the Approximability of Combinatorial Exchange Problems

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_9

DOI: 10.1007/978-3-540-79309-0_9
: Conference Paper

Social Context Games

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_73

DOI: 10.1007/978-3-540-92185-1_73
: Conference Paper

Utilitarian Mechanism Design for Single-Minded Agents

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_454

DOI: 10.1007/978-0-387-30162-4_454
: Chapter

Utilitarian Mechanism Design for Single-Minded Agents

Krysta, P., & Vöcking, B. (2008). Utilitarian Mechanism Design for Single-Minded Agents. In Encyclopedia of Algorithms (pp. 1-99). Springer Nature. doi:10.1007/978-0-387-30162-4_454

DOI: 10.1007/978-0-387-30162-4_454
: Chapter

2007

An Experimental Study of the Misdirection Algorithm for Combinatorial Auctions

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_21

DOI: 10.1007/11970125_21
: Conference Paper

Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing

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.

: Conference Paper

2006

Computing equilibria for a service provider game with (Im)perfect information

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

DOI: 10.1145/1198513.1198524
: Journal article

Efficient approximation algorithms for the achromatic number

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

DOI: 10.1016/j.tcs.2006.05.007
: Journal article

Single-minded unlimited supply pricing on sparse instances

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 (pp. 1093-1102). ACM Press. doi:10.1145/1109557.1109678

DOI: 10.1145/1109557.1109678
: Conference Paper

2005

Approximation techniques for utilitarian mechanism design

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 (pp. 39-48). ACM. doi:10.1145/1060590.1060597

DOI: 10.1145/1060590.1060597
: Conference Paper

Bicriteria Network Design via Iterative Rounding

Krysta, P. (2005). Bicriteria Network Design via Iterative Rounding. In Unknown Conference (pp. 179-187). Springer Berlin Heidelberg. doi:10.1007/11533719_20

DOI: 10.1007/11533719_20
: Conference Paper

Geometric Network Design with Selfish Agents

Hoefer, M., & Krysta, P. (2005). Geometric Network Design with Selfish Agents. In Unknown Conference (pp. 167-178). Springer Berlin Heidelberg. doi:10.1007/11533719_19

DOI: 10.1007/11533719_19
: Conference Paper

Greedy Approximation via Duality for Packing, Combinatorial Auctions and Routing

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_53

DOI: 10.1007/11549345_53
: Conference Paper

2004

Computing equilibria for congestion games with (im)perfect information

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.

: Conference Paper

2003

Approximating minimum size {1,2}-connected networks

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

DOI: 10.1016/s0166-218x(02)00199-3
: Journal article

An Experimental Study of k-Splittable Scheduling for DNS-Based Traffic Allocation

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_35

DOI: 10.1007/978-3-540-45209-6_35
: Conference Paper

Optimizing misdirection

Berman, P., & Krysta, P. (2003). Optimizing misdirection. In ACM-SIAM Symposium on Discrete Algorithms (pp. 192-201). Philadelphia, PA: SIAM. doi:10.1145/644108.644142

DOI: 10.1145/644108.644142
: Conference Paper

Scheduling and Traffic Allocation for Tasks with Bounded Splittability

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_44

DOI: 10.1007/978-3-540-45138-9_44
: Conference Paper

2002

Selfish traffic allocation for server farms

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 (pp. 287-296). ACM. doi:10.1145/509907.509952

DOI: 10.1145/509907.509952
: Conference Paper

Approximability of Dense and Sparse Instances of Minimum 2-Connectivity, TSP and Path Problems

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

DOI: 10.1145/545381.545390
: Conference Paper

2001

Krysta, P., & Solis-Oba, R. (2001). Unknown Title. Journal of Combinatorial Optimization, 5(2), 233-247. doi:10.1023/a:1011465419252

DOI: 10.1023/a:1011465419252
: Journal article

Approximation Algorithms for Minimum Size 2-Connectivity Problems

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_38

DOI: 10.1007/3-540-44693-1_38
: Conference Paper

1999

The STO problem is NP-complete

Krysta, P., & Pacholski, L. (1999). The STO problem is NP-complete. Journal of Symbolic Computation, 27(2), 207-219. doi:10.1006/jsco.1998.0249

DOI: 10.1006/jsco.1998.0249
: Journal article

Approximation Algorithms for Bounded Facility Location

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_24

DOI: 10.1007/3-540-48686-0_24
: Conference Paper

Efficient Approximation Algorithms for the Achromatic Number

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_35

DOI: 10.1007/3-540-48481-7_35
: Conference Paper

1997

External inverse pattern matching

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_53

DOI: 10.1007/3-540-63220-4_53
: Conference Paper