Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userApproximating Min-Cost Chain-Constrained Spanning Trees: A Reduction from Weighted to Unweighted Problems
51
0
0.0
(
0
)
Added by
Chaitanya Swamy
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the {em min-cost chain-constrained spanning-tree} (abbreviated mcst) problem: find a min-cost spanning tree in a graph subject to degree constraints on a nested family of node sets. We devise the {em first} polytime algorithm that finds a spanning tree that (i) violates the degree constraints by at most a constant factor {em and} (ii) whose cost is within a constant factor of the optimum. Previously, only an algorithm for {em unweighted} cst was known cite{olver}, which satisfied (i) but did not yield any cost bounds. This also yields the first result that obtains an $O(1)$-factor for {em both} the cost approximation and violation of degree constraints for any spanning-tree problem with general degree bounds on node sets, where an edge participates in a super-constant number of degree constraints. A notable feature of our algorithm is that we {em reduce} mcst to unweighted cst (and then utilize cite{olver}) via a novel application of {em Lagrangian duality} to simplify the {em cost structure} of the underlying problem and obtain a decomposition into certain uniform-cost subproblems. We show that this Lagrangian-relaxation based idea is in fact applicable more generally and, for any cost-minimization problem with packing side-constraints, yields a reduction from the weighted to the unweighted problem. We believe that this reduction is of independent interest. As another application of our technique, we consider the {em $k$-budgeted matroid basis} problem, where we build upon a recent rounding algorithm of cite{BansalN16} to obtain an improved $n^{O(k^{1.5}/epsilon)}$-time algorithm that returns a solution that satisfies (any) one of the budget constraints exactly and incurs a $(1+epsilon)$-violation of the other budget constraints.
rate research
Read More
Many load balancing problems that arise in scientific computing applications ask to partition a graph with weights on the vertices and costs on the edges into a given number of almost equally-weighted parts such that the maximum boundary cost over all parts is small. Here, this partitioning problem is considered for bounded-degree graphs G=(V,E) with edge costs c: E->R+ that have a p-separator theorem for some p>1, i.e., any (arbitrarily weighted) subgraph of G can be separated into two parts of roughly the same weight by removing a vertex set S such that the edges incident to S in the subgraph have total cost at most proportional to (SUM_e c^p_e)^(1/p), where the sum is over all edges e in the subgraph. We show for all positive integers k and weights w that the vertices of G can be partitioned into k parts such that the weight of each part differs from the average weight by less than MAX{w_v; v in V}, and the boundary edges of each part have cost at most proportional to (SUM_e c_e^p/k)^(1/p) + MAX_e c_e. The partition can be computed in time nearly proportional to the time for computing a separator S of G. Our upper bound on the boundary costs is shown to be tight up to a constant factor for infinitely many instances with a broad range of parameters. Previous results achieved this bound only if one has c=1, w=1, and one allows parts with weight exceeding the average by a constant fraction.
We consider cost constrain
This article identifies a key algorithmic ingredient in the edge-weighted online matching algorithm by Zadimoghaddam (2017) and presents a simplified algorithm and its analysis to demonstrate how it works in the unweighted case.
Dealing with NP-hard problems, kernelization is a fundamental notion for polynomial-time data reduction with performance guarantees: in polynomial time, a problem instance is reduced to an equivalent instance with size upper-bounded by a function of a parameter chosen in advance. Kernelization for weighted problems particularly requires to also shrink weights. Marx and Vegh [ACM Trans. Algorithms 2015] and Etscheid et al. [J. Comput. Syst. Sci. 2017] used a technique of Frank and Tardos [Combinatorica 1987] to obtain polynomial-size kernels for weighted problems, mostly with additive goal functions. We characterize the function types that the technique is applicable to, which turns out to contain many non-additive functions. Using this insight, we systematically obtain kernelization results for natural problems in graph partitioning, network design, facility location, scheduling, vehicle routing, and computational social choice, thereby improving and generalizing results from the literature.
The {sc Directed Maximum Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we obtain two combinatorial results on the number of leaves in out-branchings. We show that - every strongly connected $n$-vertex digraph $D$ with minimum in-degree at least 3 has an out-branching with at least $(n/4)^{1/3}-1$ leaves; - if a strongly connected digraph $D$ does not contain an out-branching with $k$ leaves, then the pathwidth of its underlying graph UG($D$) is $O(klog k)$. Moreover, if the digraph is acyclic, the pathwidth is at most $4k$. The last result implies that it can be decided in time $2^{O(klog^2 k)}cdot n^{O(1)}$ whether a strongly connected digraph on $n$ vertices has an out-branching with at least $k$ leaves. On acyclic digraphs the running time of our algorithm is $2^{O(klog k)}cdot n^{O(1)}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
