Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDistributed Approximation Algorithms for the Combinatorial Motion Planning Problem
97
0
0.0
(
0
)
Added by
Shrisha Rao
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present a new $4$-approximation algorithm for the Combinatorial Motion Planning problem which runs in $mathcal{O}(n^2alpha(n^2,n))$ time, where $alpha$ is the functional inverse of the Ackermann function, and a fully distributed version for the same in asynchronous message passing systems, which runs in $mathcal{O}(nlog_2n)$ time with a message complexity of $mathcal{O}(n^2)$. This also includes the first fully distributed algorithm in asynchronous message passing systems to perform shortcut operations on paths, a procedure which is important in approximation algorithms for the vehicle routing problem and its variants. We also show that our algorithm gives feasible solutions to the $k$-TSP problem with an approximation factor of $2$ in both centralized and distributed environments. The broad idea of the algorithm is to distribute the set of vertices into two subsets and construct paths for each salesman over each of the two subsets. Finally we combine these pairwise disjoint paths for each salesman to obtain a set of paths that span the entire graph. This is similar to the algorithm by Yadlapalli et. al. cite{3.66} but differs in respect to the fact that it does not require us to use minimum cost matching as a subroutine, and hence can be easily distributed.
rate research
Read More
We consider the distributed version of the Multiple Knapsack Problem (MKP), where $m$ items are to be distributed amongst $n$ processors, each with a knapsack. We propose different distributed approximation algorithms with a tradeoff between time and message complexities. The algorithms are based on the greedy approach of assigning the best item to the knapsack with the largest capacity. These algorithms obtain a solution with a bound of $frac{1}{n+1}$ times the optimum solution, with either $mathcal{O}left(mlog nright)$ time and $mathcal{O}left(m nright)$ messages, or $mathcal{O}left(mright)$ time and $mathcal{O}left(mn^{2}right)$ messages.
The anti-Ramsey number, $ar(G, H)$ is the minimum integer $k$ such that in any edge colouring of $G$ with $k$ colours there is a rainbow subgraph isomorphic to $H$, i.e., a copy of $H$ with each of its edges assigned a different colour. The notion was introduced by Erd{{o}}s and Simonovits in 1973. Since then the parameter has been studied extensively in combinatorics, also the particular case when $H$ is a star graph. Recently this case received the attention of researchers from the algorithm community because of its applications in interface modelling of wireless networks. To the algorithm community, the problem is known as maximum edge $q$-colouring problem. In this paper, we study the maximum edge $2$-colouring problem from the approximation algorithm point of view. The case $q=2$ is particularly interesting due to its application in real-life problems. Algorithmically, this problem is known to be NP-hard for $qge 2$. For the case of $q=2$, it is also known that no polynomial-time algorithm can approximate to a factor less than $3/2$ assuming the unique games conjecture. Feng et al. showed a $2$-approximation algorithm for this problem. Later Adamaszek and Popa presented a $5/3$-approximation algorithm with the additional assumption that the input graph has a perfect matching. Note that the obvious but the only known algorithm issues different colours to the edges of a maximum matching (say $M$) and different colours to the connected components of $G setminus M$. In this article, we give a new analysis of the aforementioned algorithm leading to an improved approximation bound for triangle-free graphs with perfect matching. We also show a new lower bound when the input graph is triangle-free. The contribution of the paper is a completely new, deeper and closer analysis of how the optimum achieves a higher number of colours than the matching based algorithm, mentioned above.
A long-standing conjecture by Heath, Pemmaraju, and Trenk states that the upward book thickness of outerplanar DAGs is bounded above by a constant. In this paper, we show that the conjecture holds for subfamilies of upward outerplanar graphs, namely those whose underlying graph is an internally-triangulated outerpath or a cactus, and those whose biconnected components are $at$-outerplanar graphs. On the complexity side, it is known that deciding whether a graph has upward book thickness $k$ is NP-hard for any fixed $k ge 3$. We show that the problem, for any $k ge 5$, remains NP-hard for graphs whose domination number is $O(k)$, but it is FPT in the vertex cover number.
Combinatorial algorithms such as those that arise in graph analysis, modeling of discrete systems, bioinformatics, and chemistry, are often hard to parallelize. The Combinatorial BLAS library implements key computational primitives for rapid development of combinatorial algorithms in distributed-memory systems. During the decade since its first introduction, the Combinatorial BLAS library has evolved and expanded significantly. This paper details many of the key technical features of Combinatorial BLAS version 2.0, such as communication avoidance, hierarchical parallelism via in-node multithreading, accelerator support via GPU kernels, generalized semiring support, implementations of key data structures and functions, and scalable distributed I/O operations for human-readable files. Our paper also presents several rules of thumb for choosing the right data structures and functions in Combinatorial BLAS 2.0, under various common application scenarios.
We introduce and study a discrete multi-period extension of the classical knapsack problem, dubbed generalized incremental knapsack. In this setting, we are given a set of $n$ items, each associated with a non-negative weight, and $T$ time periods with non-decreasing capacities $W_1 leq dots leq W_T$. When item $i$ is inserted at time $t$, we gain a profit of $p_{it}$; however, this item remains in the knapsack for all subsequent periods. The goal is to decide if and when to insert each item, subject to the time-dependent capacity constraints, with the objective of maximizing our total profit. Interestingly, this setting subsumes as special cases a number of recently-studied incremental knapsack problems, all known to be strongly NP-hard. Our first contribution comes in the form of a polynomial-time $(frac{1}{2}-epsilon)$-approximation for the generalized incremental knapsack problem. This result is based on a reformulation as a single-machine sequencing problem, which is addressed by blending dynamic programming techniques and the classical Shmoys-Tardos algorithm for the generalized assignment problem. Combined with further enumeration-based self-reinforcing ideas and newly-revealed structural properties of nearly-optimal solutions, we turn our basic algorithm into a quasi-polynomial time approximation scheme (QPTAS). Hence, under widely believed complexity assumptions, this finding rules out the possibility that generalized incremental knapsack is APX-hard.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
