Grants

• Online algorithms for configuration games

  Leader: dr hab. Marcin Bieńkowski

  Funded by Polish National Science Centre

  2023-2026

   

• Efektywne wykorzystanie randomizacji: od szeregowania do AdWords

  Kierownik: dr Łukasz Jeż

  Okres realizacji: 2021-2025

  Projekt badawczy finansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego

• Algorytmy dla projektowania połączeń w warunkach niepewności

  Kierownik: dr hab. Jarosław Byrka

  Okres realizacji: 2021-2025

  Projekt badawczy finansowany przez Narodowe Centrum Nauki

• Optymalizacja kombinatoryczna w warunkach niepewności: matroidy, skojarzenia i funkcje submodularne

  Kierownik: dr Marek Adamczyk

  Okres realizacji: 2020-2023

• Combinatorial optimization through the lens of the traveling salesman route and matchings

  Leader: dr hab. Katarzyna Paluch
  Funded by Polish National Science Centre.
  2019-2022

• Algorithmic techniques for solving social and economic issues

  Leader: mgr Krzysztof Sornat
  Funded by Polish National Science Centre.
  2018-2019

• Algorytmiczna optymalizacja online dla problemów grafowych

  Kierownik: dr hab. Marcin Bieńkowski

  Okres realizacji: 2017-2023

  Projekt badawczy finansowany przez Narodowe Centrum Nauki

• Online algorithms for packing and covering problems

  Leader: mgr Maciej Pacut
  Funded by Polish National Science Centre.
  2017-2018

• Algorithmic online optimization for graph problems

  Leader: dr hab. Marcin Bieńkowski
  Funded by Polish National Science Centre.
  2017-2022

  The goal of this project is to deliver new algorithmic methods for various problems related to online optimization. The considered problems span vast areas of computer networks, telecommunications, distribution networks and supply-chain management. Rather than focusing on a specific application, we address a broad scope of fundamental building blocks, crucial in many optimization procedures.

  The particular research directions we pursue are split into three categories: (i) developing online algorithms for efficient dynamic placement of resources in a graph, (ii) developing online algorithms for leasing of resources, (iii) investigating gains of reordering and aggregating demands.

• Throughput Maximization Problems

  Leader: dr Łukasz Jeż
  Funded by Polish National Science Centre.
  2017-2020

• Application of modern algorithmic methods for solving NP-hard clustering problems

  Leader: mgr Krzysztof Sornat
  Funded by Polish National Science Centre.
  2016-2019
  
  

• Algorithmic fundamentals of supply chain networks

  Leader: dr hab. Jarosław Byrka
  Funded by Polish National Science Centre.
  2016-2021
  

  The drive to minimize costs in logistics, and supply-chain networks in particular, results in the need to aggregate traffic both in space and over time. This motivates the study of the underlying combinatorial optimization problems. The two biggest challenges are the intractability resulting from the presence of combinatorial constraints such as unsplittability of shipments, and the uncertainty of the future demand.
  
  State-of-the-art solution methods for a number of the fundamental network design and management problems are still far from being best possible and are often complex compositions of routines developed for more restricted settings. Also the issue of scheduling of shipments on the existing network leaves many unresolved questions, especially in the online case where shipment requests arrive over time.
  
  The particular directions we consider are: 1) to develop direct algorithms for a number of hierarchical network design settings based on rounding solutions to strong convex relaxations of the studied problems, 2) resolve the possibility to aggregate traffic on multilevel networks in the online request arrival model, 3) take temporal aspects of the anticipated demand into account at the stage of designing a network, possibly allowing designs with non-standard topologies.

• Online algorithms for fundamental network problems

  Leader: dr hab. Marcin Bieńkowski
  Funded by Polish National Science Centre.
  2014-2017
  

  Currently in the Internet, packets are delivered using best-effort strategies: while network devices like routers and switches do their best, there are hardly any guarantees on timely packet delivery. The best-effort paradigm is also commonly used in other aspects of fundamental network echanisms, such as routing table organization, maintaining access to shared data, etc. The goal of the project is to design and analyze algorithms that introduce or improve quality of service (QoS) for network applications.
  

  We identified several fundamental network mechanisms that are algorithmically challenging and whose improvements — in a long term perspective — would bring qualitative change for already existing applications. The first part of the project focuses on optimizing the mechanisms used within a single router. We consider research challenges related to managing the queues of packets to be transmitted (e.g., answering the question which packet should be sent first and which should be dropped) and the problems of maximizing the number of correctly transmitted movie frames. We also plan to address the problem of compressing the routing tables (also in the presence of its frequent updates). The second part of the project focuses on two important issues arising while serving multiple users. The first task concerns the implementation of a reliable multicast transmission: to this end, we plan to efficiently aggregate the transmitted acknowledgements. The second task focuses on constructing smart mechanisms of migrating shared services, simultaneously minimizing the user-experienced latency and monetary costs of migration.

• Efficient approximation algorithms for finding the optimal traveling salesman tours and related problems

  Leader: dr Katarzyna Paluch
  Funded by Polish National Science Centre.
  2014-2017

  The traveling salesman problem (TSP) belongs to one of the most heavily researched problems in computer science due both to its theoretical appeal and wide applications. The key objective of the project is to design approximation algorithms for important variants of the traveling salesman problem achieving better approximation factors than those known so far. We are going to study the maximization variants of the traveling salesman problem, the minimization variants and the problems connected with finding cycle cover and matchings with special properties.

• LP rounding approximation algorithms

  Leader: mgr Bartosz Rybicki
  Funded by Polish National Science Centre.
  2013-2016
  

• GreenNets (Power consumption and CO2 footprint reduction in mobile networks by advanced automated network management approaches)

  University of Wrocław coordinator: prof. Leszek Pacholski
  University of Wroclaw investigator: dr hab. Marcin Bieńkowski
  Funded within FP7-SME-2011-BSG
  2011-2013
  http://www.greennets.eu/

• LP-based approximation algorithms

  Leader: dr Jarosław Byrka
  Funded by Foundation for Polish Science within Homing Plus programme.
  2010-2013
  

• Online scheduling

  Leader: mgr Łukasz Jeż
  Funded by Ministry of Science and Higher Education.
  2010-2011
  

• Approximation algorithms under uncertainty

  Leader: dr Marcin Bieńkowski
  Funded by Ministry of Science and Higher Education.
  2010-2013

• Dynamic networks: exploration and data management

  Leader: dr Marcin Bieńkowski
  Funded by Ministry of Science and Higher Education.
  2006-2008