Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow
83
0
0.0
(
0
)
Added by
Petr Kolman
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given a graph $G=(V,E)$ with two distinguished vertices $s,tin V$ and an integer $L$, an {em $L$-bounded flow} is a flow between $s$ and $t$ that can be decomposed into paths of length at most $L$. In the {em maximum $L$-bounded flow problem} the task is to find a maximum $L$-bounded flow between a given pair of vertices in the input graph. The problem can be solved in polynomial time using linear programming. However, as far as we know, no polynomial-time combinatorial algorithm for the $L$-bounded flow is known. The only attempt, that we are aware of, to describe a combinatorial algorithm for the maximum $L$-bounded flow problem was done by Koubek and v{R}i ha in 1981. Unfortunately, their paper contains substantional flaws and the algorithm does not work; in the first part of this paper, we describe these problems. In the second part of this paper we describe a combinatorial algorithm based on the exponential length method that finds a $(1+epsilon)$-approximation of the maximum $L$-bounded flow in time $O(epsilon^{-2}m^2 Llog L)$ where $m$ is the number of edges in the graph. Moreover, we show that this approach works even for the NP-hard generalization of the maximum $L$-bounded flow problem in which each edge has a length.
rate research
Read More
Given a graph $G=(V,E)$ with two distinguished vertices $s,tin V$ and an integer parameter $L>0$, an {em $L$-bounded cut} is a subset $F$ of edges (vertices) such that the every path between $s$ and $t$ in $Gsetminus F$ has length more than $L$. The task is to find an $L$-bounded cut of minimum cardinality. Though the problem is very simple to state and has been studied since the beginning of the 70s, it is not much understood yet. The problem is known to be $cal{NP}$-hard to approximate within a small constant factor even for $Lgeq 4$ (for $Lgeq 5$ for the vertex cuts). On the other hand, the best known approximation algorithm for general graphs has approximation ratio only $mathcal{O}({n^{2/3}})$ in the edge case, and $mathcal{O}({sqrt{n}})$ in the vertex case, where $n$ denotes the number of vertices. We show that for planar graphs, it is possible to solve both the edge- and the vertex-version of the problem optimally in time $mathcal{O}(L^{3L}n)$. That is, the problem is fixed parameter tractable (FPT) with respect to $L$ on planar graphs. Furthermore, we show that the problem remains FPT even for bounded genus graphs, a super class of planar graphs. Our second contribution deals with approximations of the vertex version of the problem. We describe an algorithm that for a given a graph $G$, its tree decomposition of treewidth $tau$ and vertices $s$ and $t$ computes a $tau$-approximation of the minimum $L$-bounded $s-t$ vertex cut; if the decomposition is not given, then the approximation ratio is $mathcal{O}(tau sqrt{log tau})$. For graphs with treewidth bounded by $mathcal{O}(n^{1/2-epsilon})$ for any $epsilon>0$, but not by a constant, this is the best approximation in terms of~$n$ that we are aware of.
For graphs $G$ and $H$, we say that $G$ is $H$-free if it does not contain $H$ as an induced subgraph. Already in the early 1980s Alekseev observed that if $H$ is connected, then the textsc{Max Weight Independent Set} problem (MWIS) remains textsc{NP}-hard in $H$-free graphs, unless $H$ is a path or a subdivided claw, i.e., a graph obtained from the three-leaf star by subdividing each edge some number of times (possibly zero). Since then determining the complexity of MWIS in these remaining cases is one of the most important problems in algorithmic graph theory. A general belief is that the problem is polynomial-time solvable, which is witnessed by algorithmic results for graphs excluding some small paths or subdivided claws. A more conclusive evidence was given by the recent breakthrough result by Gartland and Lokshtanov [FOCS 2020]: They proved that MWIS can be solved in quasipolynomial time in $H$-free graphs, where $H$ is any fixed path. If $H$ is an arbitrary subdivided claw, we know much less: The problem admits a QPTAS and a subexponential-time algorithm [Chudnovsky et al., SODA 2019]. In this paper we make an important step towards solving the problem by showing that for any subdivided claw $H$, MWIS is polynomial-time solvable in $H$-free graphs of bounded degree.
The question of whether all problems in NP class are also in P class is generally considered one of the most important open questions in mathematics and theoretical computer science as it has far-reaching consequences to other problems in mathematics, computer science, biology, philosophy and cryptography. There are intensive research on proving `NP not equal to P and `NP equals to P. However, none of the `proved results is commonly accepted by the research community up to date. In this paper, motived by approximability of traveling salesman problem (TSP) in polynomial time, we aim to provide a new perspective: showing that NP=P from polynomial time approximation-bounded solutions of TSP in Euclidean space.
We study the problem of computing the maximum likelihood estimator (MLE) of multivariate log-concave densities. Our main result is the first computationally efficient algorithm for this problem. In more detail, we give an algorithm that, on input a set of $n$ points in $mathbb{R}^d$ and an accuracy parameter $epsilon>0$, it runs in time $text{poly}(n, d, 1/epsilon)$, and outputs a log-concave density that with high probability maximizes the log-likelihood up to an additive $epsilon$. Our approach relies on a natural convex optimization formulation of the underlying problem that can be efficiently solved by a projected stochastic subgradient method. The main challenge lies in showing that a stochastic subgradient of our objective function can be efficiently approximated. To achieve this, we rely on structural results on approximation of log-concave densities and leverage classical algorithmic tools on volume approximation of convex bodies and uniform sampling from convex sets.
We consider the problem of computing the maximum likelihood multivariate log-concave distribution for a set of points. Specifically, we present an algorithm which, given $n$ points in $mathbb{R}^d$ and an accuracy parameter $epsilon>0$, runs in time $poly(n,d,1/epsilon),$ and returns a log-concave distribution which, with high probability, has the property that the likelihood of the $n$ points under the returned distribution is at most an additive $epsilon$ less than the maximum likelihood that could be achieved via any log-concave distribution. This is the first computationally efficient (polynomial time) algorithm for this fundamental and practically important task. Our algorithm rests on a novel connection with exponential families: the maximum likelihood log-concave distribution belongs to a class of structured distributions which, while not an exponential family, locally possesses key properties of exponential families. This connection then allows the problem of computing the log-concave maximum likelihood distribution to be formulated as a convex optimization problem, and solved via an approximate first-order method. Efficiently approximating the (sub) gradients of the objective function of this optimization problem is quite delicate, and is the main technical challenge in this work.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
