
Contention resolution schemes have proven to be an incredibly powerful
concept which allows to tackle a broad class of problems. The framework has
been initially designed to handle submodular optimization under various types
of constraints, that is, intersections of exchange systems (including
matroids), knapsacks, and unsplittable flows on trees. Later on, it turned out
that this framework perfectly extends to optimization under uncertainty, like
stochastic probing and online selection problems, which further can be applied
to mechanism design.
We add to this line of work by showing how to create contention resolution
schemes for intersection of matroids and knapsacks when we work in the random
order setting. More precisely, we do know the whole universe of elements in
advance, but they appear in an order given by a random permutation. Upon
arrival we need to irrevocably decide whether to take an element or not. We
bring a novel technique for analyzing procedures in the random order setting
that is based on the martingale theory. This unified approach makes it easier
to combine constraints, and we do not need to rely on the monotonicity of
contention resolution schemes.
Our paper fills the gaps, extends, and creates connections between many
previous results and techniques. The main application of our framework is a
$k+4+\varepsilon$ approximation ratio for the Bayesian multiparameter
unitdemand mechanism design under the constraint of $k$ matroids intersection,
which improves upon the previous bounds of $4k2$ and $e(k+1)$. Other results
include improved approximation ratios for stochastic $k$set packing and
submodular stochastic probing over arbitrary nonnegative submodular objective
function, whereas previous results required the objective to be monotone.

The subject of this paper is the time complexity of approximating Knapsack,
Subset Sum, Partition, and some other related problems. The main result is an
$\widetilde{O}(n+1/\varepsilon^{5/3})$ time randomized FPTAS for Partition,
which is derived from a certain relaxed form of a randomized FPTAS for Subset
Sum. To the best of our knowledge, this is the first NPhard problem that has
been shown to admit a subquadratic time approximation scheme, i.e., one with
time complexity of $O((n+1/\varepsilon)^{2\delta})$ for some $\delta>0$. To
put these developments in context, note that a quadratic FPTAS for Partition
has been known for 40 years.
Our main contribution lies in designing a mechanism that reduces an instance
of Subset Sum to several simpler instances, each with some special structure,
and keeps track of interactions between them. This allows us to combine
techniques from approximation algorithms, pseudopolynomial algorithms, and
additive combinatorics.
We also prove several related results. Notably, we improve approximation
schemes for 3SUM, (min,+)convolution, and Tree Sparsity. Finally, we argue
why breaking the quadratic barrier for approximate Knapsack is unlikely by
giving an $\Omega((n+1/\varepsilon)^{2o(1)})$ conditional lower bound.

We study the problem of deleting the smallest set $S$ of vertices (resp.\
edges) from a given graph $G$ such that the induced subgraph (resp.\ subgraph)
$G \setminus S$ belongs to some class $\mathcal{H}$.
We consider the case where graphs in $\mathcal{H}$ have treewidth bounded by
$t$, and give a general framework to obtain approximation algorithms for both
vertex and edgedeletion settings from approximation algorithms for certain
natural graph partitioning problems called $k$Subset Vertex Separator and
$k$Subset Edge Separator, respectively.
For the vertex deletion setting, our framework combined with the current best
result for $k$Subset Vertex Separator, yields a significant improvement in the
approximation ratios for basic problems such as $k$Treewidth Vertex Deletion
and Planar$F$ Vertex Deletion. Our algorithms are simpler than previous works
and give the first uniform approximation algorithms under the natural
parameterization.
For the edge deletion setting, we give improved approximation algorithms for
$k$Subset Edge Separator combining ideas from LP relaxations and important
separators. We present their applications in boundeddegree graphs, and also
give an APXhardness result for the edge deletion problems.

In recent years, significant progress has been made in explaining the
apparent hardness of improving upon the naive solutions for many fundamental
polynomially solvable problems. This progress has come in the form of
conditional lower bounds  reductions from a problem assumed to be hard. The
hard problems include 3SUM, AllPairs Shortest Path, SAT, Orthogonal Vectors,
and others.
In the $(\min,+)$convolution problem, the goal is to compute a sequence
$(c[i])^{n1}_{i=0}$, where $c[k] = $ $\min_{i=0,\ldots,k} $ $\{a[i] $ $+$
$b[ki]\}$, given sequences $(a[i])^{n1}_{i=0}$ and $(b[i])_{i=0}^{n1}$. This
can easily be done in $O(n^2)$ time, but no $O(n^{2\varepsilon})$ algorithm is
known for $\varepsilon > 0$. In this paper, we undertake a systematic study of
the $(\min,+)$convolution problem as a hardness assumption.
First, we establish the equivalence of this problem to a group of other
problems, including variants of the classic knapsack problem and problems
related to subadditive sequences. The $(\min,+)$convolution problem has been
used as a building block in algorithms for many problems, notably problems in
stringology. It has also appeared as an ad hoc hardness assumption. Second, we
investigate some of these connections and provide new reductions and other
results. We also explain why replacing this assumption with the SETH might not
be possible for some problems.

We introduce the Noncommutative Subset Convolution  a convolution of
functions useful when working with determinantbased algorithms. In order to
compute it efficiently, we take advantage of Clifford algebras, a
generalization of quaternions used mainly in the quantum field theory.
We apply this tool to speed up algorithms counting subgraphs parameterized by
the treewidth of a graph. We present an $O^*((2^\omega + 1)^{tw})$time
algorithm for counting Steiner trees and an $O^*((2^\omega + 2)^{tw})$time
algorithm for counting Hamiltonian cycles, both of which improve the previously
known upper bounds. The result for Steiner Tree also translates into a
deterministic algorithm for Feedback Vertex Set. All of these constitute the
best known running times of deterministic algorithms for decision versions of
these problems and they match the best obtained running times for pathwidth
parameterization under assumption $\omega = 2$.

In the classical Maximum Acyclic Subgraph problem (MAS), given a
directededge weighted graph, we are required to find an ordering of the nodes
that maximizes the total weight of forwarddirected edges. MAS admits a 2
approximation, and this approximation is optimal under the Unique Game
Conjecture.
In this paper we consider a generalization of MAS, the Restricted Maximum
Acyclic Subgraph problem (RMAS), where each node is associated with a list of
integer labels, and we have to find a labeling of the nodes so as to maximize
the weight of edges whose head label is larger than the tail label. The best
known (almost trivial) approximation for RMAS is 4.
The interest of RMAS is mostly due to its connections with the Vertex Pricing
problem (VP). In VP we are given an undirected graph with positive edge
budgets. A feasible solution consists of an assignment of nonnegative prices
to the nodes. The profit for each edge $e$ is the sum of its endpoints prices
if that sum is at most the budget of $e$, and zero otherwise. Our goal is to
maximize the total profit. The best known approximation for VP, which works
analogously to the mentioned approximation algorithm for RMAS, is 4. Improving
on that is a challenging open problem. On the other hand, the best known 2
inapproximability result is due to a reduction from a special case of RMAS.
In this paper we present an improved LProunding $2\sqrt{2}$ approximation
for RMAS. Our result shows that, in order to prove a 4 hardness of
approximation result for VP (if possible), one should consider reductions from
harder problems. Alternatively, our approach might suggest a different way to
design approximation algorithms for VP.

The ability to represent intracellular biochemical dynamics via deterministic
and stochastic modelling is one of the crucial components to move biological
sciences in the observepredictcontroldesign knowledge ladder. Compared to
the engineering or physics problems, dynamical models in quantitative biology
typically dependent on a relatively large number of parameters. Therefore, the
relationship between model parameters and dynamics is often prohibitively
difficult to determine. We developed a method to depict the inputoutput
relationship for multiparametric stochastic and deterministic models via
informationtheoretic quantification of similarity between model parameters and
modules. Identification of most informationtheoretically orthogonal biological
components, provided mathematical language to precisely communicate and
visualise compensation like phenomena such as biological robustness, sloppiness
and statistical nonidentifiability. A comprehensive analysis of the
multiparameter NF$\kappa$B signalling pathway demonstrates that the
informationtheoretic similarity reflects a topological structure of the
network. Examination of the currently available experimental data on this
system reveals the number of identifiable parameters and suggests informative
experimental protocols.