|
|
Heuristics for Length Bounded Cuts
Madaj, Pavel ; Kolman, Petr (advisor) ; Koutecký, Martin (referee)
This thesis deals with the problem of finding a minimum length-bounded cut in a graph. We first provide a brief overview of the problem and its applications. We then discuss the known theoretical results and approximation algorithms. We look at the existing linear programming formulations and propose a new one. A concise discussion on potential hard instances, utilized for testing our formulations, is also incorporated. The focus of our analysis is on the performance and behavior of our proposed linear programming family, contrasting it with the established natural formulation. We also compare the performance of various heuristics and approximation algorithms in practice by examining their behaviour on a large set of small instances. 1
|
|
|
A Framework For Experimental Evaluation of Opinion Diffusion Models
Jelínek, Dominik ; Koutecký, Martin (advisor) ; Vetta, Adrian (referee)
Title: A Framework for Experimental Study of Opinion Diffusion Models Author: Dominik Jelínek institute: IUUK Supervisor: Martin Koutecký, IUUK Abstract: Our theoretical contribution centers on defining possible diffusion steps decreasing either Kendall-tau or Spearman's footrule distance between two bucket orders, which are orders with ties. These diffusion steps give us a new ability to work with, among others, election data where voters can specify any number of top preferences. From the practical contribution, we have developed an experimental framework specialized for working with bucket orders. The framework's easily extendable architecture provided by the usage of strategy design pattern allows for the generation and comparison of various models at a large scale. A part of a framework is an extensive list of important metrics and visualization techniques to observe and compare the behavior of different models. Keywords: bucket order, diffusion model, social network, framework, election iii
|
|
|
Experimental Analysis of Scaling Methods for LP
Komárek, Jakub ; Koutecký, Martin (advisor) ; Vegh, Laszlo (referee)
In his recent work, Dadush et al. introduced the condition number κ for constraint matrices of linear programming and devised an algorithm to approximately optimize κ by scaling columns of the constraint matrix. We follow up on his work by implementing this scaling algorithm. We have used our implementation to obtain an approximate rescaling of some linear programming instances available from public datasets. Finally, this work shows results of experiments evaluating the effects of the obtained rescalings on the runtime of some available linear programming solvers. 1
|
|
|
Performance Comparison of ILP versus Logical Solvers on Bribery-type Problems
Kumar, Aryan ; Koutecký, Martin (advisor) ; Faliszewski, Piotr (referee)
Integer Linear Programming (ILP) has proven to be a powerful tool for solving hard problems, particularly in computational social choice, where it has been used to address variants of the bribery problem. This problem involves finding the smallest change that results in a desired outcome after opinions diffuse through a society. The ILP solution for this problem has been shown to be experimentally limited to small instances of the problem. Research has shown that such problems can be encoded using logical formulas in Presburger Arithmetic (PrA) matching the complexity of the ILP algo- rithm. Therefore, a practical analysis of the PrA-based approach is called for. In this project, we randomly generate instances with prescribed election parameters and model them as ILP instances and PrA formulas. We use solvers such as GUROBI, GLPK, and Z3 to solve these instances and con- duct a comparative study to evaluate the performance of both approaches under different parameters, such as the number of voter types and diffusion steps. Our results show that the ILP approach is more robust than the PrA approach in practice. 1
|
|
|
Experimental analysis of the simplex method for the multicommodity flow problem
Kubek, Dávid ; Koutecký, Martin (advisor) ; Borgwardt, Steffen (referee)
This thesis investigates the multicommodity min-cost flow (MMCF) prob- lem. We aim to contribute to the search for a combinatorial algorithm for MMCF. The simplex method is employed to examine the vertices of the poly- hedron of feasible solutions using experimental analysis on a set of publicly available MMCF instances. To achieve this, we develop a solver capable of tracing solutions in each iteration of the algorithm in exact arithmetic, which was not available in existing solvers. Our investigation focuses on the frac- tionality of MMCF problems and the impact of different pivoting rules, par- ticularly whether the fractionality is exponential or polynomial with respect to increasing dimension. Our findings suggest that fractionality exhibits ex- ponential behavior.
|
|
|
A Symmetric Homophily-preserving Opinion Diffusion Model
Prokop, Aleš ; Koutecký, Martin (advisor) ; Talmon, Nimrod (referee)
We define and study a symmetric homophily-preserving opinion diffusion model on clusters of voters. This model is symmetric, which means that clusters of voters influence each other. The model is also homophily-preserving, meaning when a voter changes their opinion, their neighborhood also changes, which is a frequently observed property of social sites. We present properties of the diffusion model, such as convergence, ϵ-convergence for some types of graphs, and polyhedral description of the set of fixed points, as well as generalizations on graphs with weighted edges and directed graphs and their properties. We provide the definition of the threshold diffusion process. We study fixed points of the diffusion and threshold diffusion process. We also provide a program for experimentation on our model. 1
|
|
| |
|
|
Optimization in graphs with bounded treewidth
Koutecký, Martin ; Kolman, Petr (advisor) ; Kráľ, Daniel (referee)
Courcelle's theorem speaks about computational complexity of decision problems defined by formulae in monadic second order logic over relational structures with bounded treewodth. For a fixed treewidth and a fixed formula, Courcelle's theorem gives an algorithm, which decides the formula over a structure of said treewidth in linear time. is thesis provides a self-contained proof of Courcelle's theorem using methods of finite model theory. Furthermore it contains the proofs of all propositions and theorems upon which the main proof depends, notably the Ehrenfeucht-Fraïssé theorem widely used in finite model theory. e thesis also contains an implementa- tion of an algorithm which follows from the main proof. Finally a sketch of the current state of the art of the area of research is given, as well as the possibilities following from it. 1
|
|
|
On the Hardness of General Caching
Folwarczný, Lukáš ; Sgall, Jiří (advisor) ; Koutecký, Martin (referee)
Caching (also known as paging) is a classical problem concerning page re- placement policies in two-level memory systems. General caching is its vari- ant with pages of different sizes and fault costs. We aim at a better charac- terization of the computational complexity of general caching in the offline version. General caching in the offline version was recently shown to be strongly NP- hard, but the proof needed instances of caching with pages larger than half of the cache size. The primary result of this work addresses this problem as we prove: General caching is strongly NP-hard even when page sizes are limited to {1, 2, 3}. In the structural part of this work, a new simpler proof for the full characterization of work functions by layers for classical caching is given and then extended to caching with variable cache size. We invent two algorithms for restricted instances of general caching building on results around caching with variable cache size.
|
|
|
Combinatorial Algorithms for Flow Problems
Hladík, Richard ; Koutecký, Martin (advisor) ; Vegh, Laszlo (referee)
The multicommodity flow problem (MCF) and the length-bounded flow problem (LBF) are two generalisations of the maximum flow problem. Both can be solved us- ing linear programming and approximated using fully polynomial-time approximation schemes (FPTASs). However, there are no known algorithms for them that are at the same time 1) exact, 2) polynomial, and 3) combinatorial and/or not relying on general methods like linear programming. Multicommodity flow is sometimes called "the easiest problem with no combinatorial algorithm". In this thesis, we summarise problem-specific as well as general methods used to solve these problems. We propose two new combi- natorial algorithms, one based on the Frank-Wolfe method for convex optimisation (for MCF and LBF), and the other one based on most helpful cycle cancelling (for MCF), and prove that in networks with polynomial demands they both run in poly(input size, 1/ε) time. We also present some results from polyhedral theory, examining the circuits of MCF and LBF polyhedra. On the one hand, we prove that the existence of a circuit-like set consisting of vectors of small norm would make both algorithms nearly-exact (i.e., with ‰(log 1/ε) convergence). On the other hand, we prove that exponential circuits exist for both MCF and LBF. The existence of a circuit-like set...
|
guest ::
