Combinatorial optimization problems in Internet applications
[ 1 ] Instytut Informatyki, Wydział Informatyki, Politechnika Poznańska | [ P ] employee
[ 1 ] Instytut Informatyki, Wydział Informatyki, Politechnika Poznańska | [ P ] employee
PL Problemy optymalizacji kombinatorycznej w aplikacjach internetowych
english
- combinatorial optimization
- 2d packing
- web enineering
- tag clouds
- css-sprite
- optymalizacja kombinatoryczna
- pakowanie 2-wymiarowe
- inżynieria internetowa
- chmury tagów
- duszki css
EN Three innovative research problems are proposed and solved: 1) web page layout partitioning to improve future placing of advertisements, 2) tag clouds construction for better readability and usability on web pages, 3) CSS-sprite packing to speed up web pages loading and offload servers. The main common factor of the problems is originating from real web applications and the use of combinatorial optimization, in particular 2D packaging algorithms, to improve the performance of web pages. All of the problems are computationally difficult, NP-hard, what is demonstrated. For each of the problems, a mathematical model is provided and heuristic algorithms are developed and tested.
PL W pracy zaproponowano i rozwiązano trzy nowatorskie zagadnienia badawcze: 1) optymalizacji układu szerokości kolumn strony internetowej w celu poprawy możliwości umieszczania reklam, 2) budowania chmur tagów dla lepszej czytelności i użyteczności stron internetowych, 3) pakowania CSS-sprite tak, by przyspieszyć ładowanie stron internetowych i odciążyć serwery. Głównymi wspólnymi cechami problemów jest pochodzenie z rzeczywistych zastosowań aplikacji internetowych oraz użycie optymalizacji kombinatorycznej, a w szczególności algorytmów pakowania dwuwymiarowego, dla poprawy jakości działania tych stron. Wszystkie rozpatrywane problemy są obliczeniowo trudne, należą do klasy problemów NP-trudnych, co jest wykazywane. Dla każdego z problemów zaproponowano model matematyczny, a do ich rozwiązywania zaproponowano i przetestowano algorytmy heurystyczne.
135
computer sciences and computer science
computer science
DrOIN 1877
public
Pascal Bouvry
Luksemburg, Luksemburg
16.09.2017
english
public
Eric Sanlaville
Hawr, Francja
16.09.2017
english
public
dissertation
Poznań, Polska
17.11.2017
Rada Wydziału Informatyki Politechniki Poznańskiej
doktor nauk technicznych w dyscyplinie: informatyka, w specjalności: optymalizacja kombinatoryczna