On the Descriptive Complexity of Color Coding [PDF]
, 2021 Color coding is an algorithmic technique used in parameterized complexity theory to detect “small” structures inside graphs. The idea is to derandomize algorithms that first randomly color a graph and then search for an easily-detectable, small color ...
Max Bannach, Till Tantau
core +1 more source
Improved complexity bounds in Wasserstein barycenter problem [PDF]
, 2021 In this paper, we focus on computational aspects of the Wasserstein barycenter problem. We propose two algorithms to compute Wasserstein barycenters of m discrete measures of size n with accuracy $\e$.
Dvinskikh, Darina, Tiapkin, Daniil
core +1 more source
On a Nonsmooth Gauss–Newton Algorithms for Solving Nonlinear Complementarity Problems [PDF]
, 2020 In this paper, we propose a new version of the generalized damped Gauss–Newton method for solving nonlinear complementarity problems based on the transformation to the nonsmooth equation, which is equivalent to some unconstrained optimization problem ...
Marek J. Śmietański +1 more
core +1 more source
Randomized Parameterized Algorithms for the Kidney Exchange Problem [PDF]
, 2019 In order to increase the potential kidney transplants between patients and their incompatible donors, kidney exchange programs have been created in many countries.
Bin Fu +7 more
core +2 more sources
A Structural Complexity Analysis of Synchronous Dynamical Systems [PDF]
, 2023 Synchronous dynamic systems are well-established models that have been used to capture a range of phenomena in networks, including opinion diffusion, spread of disease and product adoption.
Ganian, Robert +3 more
core +1 more source
A Multi-Dimensional Matrix Product—A Natural Tool for Parameterized Graph Algorithms [PDF]
, 2022 We introduce the concept of a k-dimensional matrix product D of k matrices A1,…,Ak of sizes n1×n,…,nk×n, respectively, where D[i1,…,ik] is equal to ∑ℓ=1nA1[i1,ℓ]×…×Ak[ik,ℓ].
Lingas, Andrzej +3 more
core +1 more source
On the probabilistic min spanning tree Problem [PDF]
, 2010 International audienceWe study a probabilistic optimization model for min spanning tree, where any vertex v i of the input-graph G(V, E) has some presence probability p i in the final instance G′ ⊂ G that will effectively be optimized.
Paschos, V.T. +10 more
core +1 more source
Data Complexity in Machine Learning and Novel Classification Algorithms [PDF]
, 2006 This thesis summarizes four of my research projects in machine learning. One of them is on a theoretical challenge of defining and exploring complexity measures for data sets; the others are about new and improved classification algorithms.
Li, Ling
core +1 more source
Energy-aware lot sizing problem: Complexity analysis and exact algorithms [PDF]
International Journal of Production Economics, 2018 Abstract The single-item lot sizing problem under a periodic energy limitation is considered in this paper. Identical and parallel capacitated machines constitute the production system, each one consuming a certain amount of energy when being switched on, when reserved, and when producing.
Christophe Rapine +2 more
openaire +1 more source
The sparse awakens : streaming algorithms for matching size estimation in sparse graphs [PDF]
, 2017 Estimating the size of the maximum matching is a canonical problem in graph analysis, and one that has attracted extensive study over a range of different computational models.
Muthukrishnan, S. +3 more
core +1 more source