LP rounding approximation algorithms
2012/07/N/ST6/03068
Keywords
Descriptors
- ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
- ST6_4: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna
- ST6_12: Obliczenia naukowe, narzędzia modelowania i symulacji
Panel
ST6 – Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems
Host institution
Uniwersytet Wrocławski, Wydział Matematyki i Informatyki
Voivodeship: dolnośląskie
Principal investigator (from the host institution)
Number of co-investigators in the project: 2
Call
PRELUDIUM 4 – announced on 2012-09-15
- Amount awarded
- 149 898 PLN
- Project start date
- 2013-07-29
- Project end date
- 2016-07-28
- Project duration
- 36 months (the same as in the proposal)
- Project status
- Project settled
Equipment purchased [PL]
- Notebook. Cost: 5 000 PLN
Information in the final report
Publication in academic press/journals (1)
-
Improved Approximation Algorithm for k-level Uncapacitated Facility Location Problem (with Penalties)
- Authors:
- Jaroslaw Byrka, Shanfei Li, Bartosz Rybicki
- Academic press:
- Theory of Computing Systems (year: 2016, volume: 58, pages: 19-44), Publisher: Springer
- Status:
- Published
Articles in post-conference publications (5)
-
An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
- Authors:
- Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, Khoa Trinh
- Conference:
- SODA 2015 (year: 2015, pages: 737-756), Publisher: ACM Digital Library
- Date:
- conference 1,2015
- Status:
- Published
- DOI:
- link to the publication
-
Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems
- Authors:
- Jaroslaw Byrka, Krzysztof Fleszar, Bartosz Rybicki, Joachim Spoerhase
- Conference:
- SODA 2015 (year: 2015, pages: 722-736), Publisher: ACD Digital Library
- Date:
- conference 1,2015
- Status:
- Published
- DOI:
- link to the publication
-
Improved Approximation Algorithm for k-Level UFL with Penalties, a Simplistic View on Randomizing the Scaling Parameter
- Authors:
- Jarosław Byrka, Shanfei Li, Bartosz Rybicki
- Conference:
- WAOA 2013 (year: 2013, pages: 85-96), Publisher: Springer
- Date:
- conference 5-6.09
- Status:
- Published
- DOI:
- link to the publication
-
Improved Approximation Algorithm for Fault-Tolerant Facility Placement
- Authors:
- Jarosław Byrka, Bartosz Rybicki
- Conference:
- WAOA 2014 (year: 2015, pages: 59-70), Publisher: Springer
- Date:
- conference 9,2014
- Status:
- Published
- DOI:
- link to the publication
-
An Improved Approximation Algorithm for Knapsack Median Using Sparsification
- Authors:
- Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Joachim Spoerhase, Aravind Srinivasan, Khoa Trinh
- Conference:
- ESA 2015 (year: 2015, pages: 275-287), Publisher: Springer
- Date:
- conference 9,2015
- Status:
- Published