The Experts below are selected from a list of 306 Experts worldwide ranked by ideXlab platform
Rzążewski Paweł - One of the best experts on this subject based on the ideXlab platform.
-
Complexity of Token Swapping and its Variants
2018Co-Authors: Bonnet Édouard, Miltzow Tillmann, Rzążewski PawełAbstract:In the Token Swapping problem we are given a graph with a token placed on each Vertex. Each token has exactly one Destination Vertex, and we try to move all the tokens to their Destinations, using the minimum number of swaps, i.e., operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that Token Swapping is $W[1]$-hard parameterized by the length $k$ of a shortest sequence of swaps. In fact, we prove that, for any computable function $f$, it cannot be solved in time $f(k)n^{o(k / \log k)}$ where $n$ is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial $n^{O(k)}$-time algorithm. We also consider two generalizations of the Token Swapping, namely Colored Token Swapping (where the tokens have different colors and tokens of the same color are indistinguishable), and Subset Token Swapping (where each token has a set of possible Destinations). To complement the hardness result, we prove that even the most general variant, Subset Token Swapping, is FPT in nowhere-dense graph classes. Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases.Comment: 23 pages, 7 Figure
-
Complexity of token swapping and its variants
'Springer Science and Business Media LLC', 2018Co-Authors: Bonnet Édouard, Miltzow Tillmann, Rzążewski PawełAbstract:AbstractIn the Token Swapping problem we are given a graph with a token placed on each Vertex. Each token has exactly one Destination Vertex, and we try to move all the tokens to their Destinations, using the minimum number of swaps, i.e., operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that Token Swapping is W[1]-hard parameterized by the length k of a shortest sequence of swaps. In fact, we prove that, for any computable function f, it cannot be solved in time f(k)no(k/logk) where n is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial nO(k)-time algorithm. We also consider two generalizations of the Token Swapping, namely Colored Token Swapping (where the tokens have colors and tokens of the same color are indistinguishable), and Subset Token Swapping (where each token has a set of possible Destinations). To complement the hardness result, we prove that even the most general variant, Subset Token Swapping, is FPT in nowhere-dense graph classes. Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases
-
Complexity of Token Swapping and Its Variants
'Springer Science and Business Media LLC', 2018Co-Authors: Bonnet Édouard, Miltzow Tillmann, Rzążewski PawełAbstract:In the Token Swapping problem we are given a graph with a token placed on each Vertex. Each token has exactly one Destination Vertex, and we try to move all the tokens to their Destinations, using the minimum number of swaps, i.e. operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that Token Swapping is W[ 1 ] -hard parameterized by the length k of a shortest sequence of swaps. In fact, we prove that, for any computable function f, it cannot be solved in time f(k) no ( k / log k ) where n is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial nO ( k )-time algorithm. We also consider two generalizations of the Token Swapping, namely Colored Token Swapping (where the tokens have colors and tokens of the same color are indistinguishable), and Subset Token Swapping (where each token has a set of possible Destinations). To complement the hardness result, we prove that even the most general variant, Subset Token Swapping, is FPT in nowhere-dense graph classes. Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases.SCOPUS: ar.jinfo:eu-repo/semantics/publishe
-
Complexity of token swapping and its variants
Springer Verlag, 2018Co-Authors: Bonnet Édouard, Tillmann Miltzow, Rzążewski PawełAbstract:International audienceIn the Token Swapping problem we are given a graph with a token placed on each Vertex. Each token has exactly one Destination Vertex, and we try to move all the tokens to their Destinations, using the minimum number of swaps, i.e., operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that Token Swapping is W [1]-hard parameterized by the length k of a shortest sequence of swaps. In fact, we prove that, for any computable function f , it cannot be solved in time f (k)n o(k/ log k) where n is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial n O(k)-time algorithm. We also consider two generalizations of the Token Swapping, namely Colored Token Swapping (where the tokens have colors and tokens of the same color are indistinguishable), and Subset Token Swapping (where each token has a set of possible Destinations). To complement the hardness result, we prove that even the most general variant, Subset Token Swapping, is FPT in nowhere-dense graph classes. Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases
R. Ravi - One of the best experts on this subject based on the ideXlab platform.
-
Minimum Makespan Multi-Vehicle Dial-a-Ride
ACM Transactions on Algorithms, 2015Co-Authors: Inge Li Gørtz, Viswanath Nagarajan, R. RaviAbstract:Dial-a-Ride problems consist of a set V of n vertices in a metric space (denoting travel time between vertices) and a set of m objects represented as source-Destination pairs {(si,ti)}mi=1, where each object requires to be moved from its source to Destination Vertex. In the multi-vehicle Dial-a-Ride problem, there are q vehicles, each having capacity k and where each vehicle j ∈ [q] has its own depot-Vertex rj ∈ V. A feasible schedule consists of a capacitated route for each vehicle (where vehicle j originates and ends at its depot rj) that together move all objects from their sources to Destinations. The objective is to find a feasible schedule that minimizes the maximum completion time (i.e., makespan) of vehicles, where the completion time of vehicle j is the time when it returns to its depot rj at the end of its route. We study the preemptive version of multi-vehicle Dial-a-Ride, in which an object may be left at intermediate vertices and transported by more than one vehicle, while being moved from source to Destination. Our main results are an O(log3n)-approximation algorithm for preemptive multi-vehicle Dial-a-Ride, and an improved O(log t)-approximation for its special case when there is no capacity constraint (here t≤ n is the number of distinct depot-vertices). There is an Ω (log1/4-e n) hardness of approximation known even for single vehicle capacitated Dial-a-Ride [Gortz 2006]. For uncapacitated multi-vehicle Dial-a-Ride, we show that there are instances when natural lower bounds (used in our algorithm) are ˜Ω(log t) factor away from the optimum. We also consider the special class of metrics induced by graphs excluding any fixed minor (e.g., planar metrics). In this case, we obtain improved guarantees of O(log2 n) for capacitated multi-vehicle Dial-a-Ride, and O(1) for the uncapacitated problem.
-
Minimum Makespan Multi-vehicle Dial-a-Ride
arXiv: Data Structures and Algorithms, 2011Co-Authors: Inge Li Goertz, Viswanath Nagarajan, R. RaviAbstract:Dial a ride problems consist of a metric space (denoting travel time between vertices) and a set of m objects represented as source-Destination pairs, where each object requires to be moved from its source to Destination Vertex. We consider the multi-vehicle Dial a ride problem, with each vehicle having capacity k and its own depot-Vertex, where the objective is to minimize the maximum completion time (makespan) of the vehicles. We study the "preemptive" version of the problem, where an object may be left at intermediate vertices and transported by more than one vehicle, while being moved from source to Destination. Our main results are an O(log^3 n)-approximation algorithm for preemptive multi-vehicle Dial a ride, and an improved O(log t)-approximation for its special case when there is no capacity constraint. We also show that the approximation ratios improve by a log-factor when the underlying metric is induced by a fixed-minor-free graph.
-
ESA - Minimum Makespan Multi-vehicle Dial-a-Ride
Lecture Notes in Computer Science, 2009Co-Authors: Inge Li Gørtz, Viswanath Nagarajan, R. RaviAbstract:Dial-a-Ride problems consist of a set V of n vertices in a metric space (denoting travel time between vertices) and a set of m objects represented as source-Destination pairs \(\{(s_i,t_i)\}^m_{i=1}\), where each object requires to be moved from its source to Destination Vertex. In the multi-vehicle Dial-a-Ride problem, there are q vehicles each having capacity k and where each vehicle j ∈ [q] has its own depot-Vertex r j ∈ V. A feasible schedule consists of a capacitated route for each vehicle (where vehicle j originates and ends at its depot r j ) that together move all objects from their sources to Destinations. The objective is to find a feasible schedule that minimizes the maximum completion time (i.e. makespan) of vehicles, where the completion time of vehicle j is the time when it returns to its depot r j at the end of its route. We consider the preemptive version of multi-vehicle Dial-a-Ride, where an object may be left at intermediate vertices and transported by more than one vehicle, while being moved from source to Destination. Approximation algorithms for the single vehicle Dial-a-Ride problem (q = 1) have been considered in [3,10].
Bonnet Édouard - One of the best experts on this subject based on the ideXlab platform.
-
Complexity of Token Swapping and its Variants
2018Co-Authors: Bonnet Édouard, Miltzow Tillmann, Rzążewski PawełAbstract:In the Token Swapping problem we are given a graph with a token placed on each Vertex. Each token has exactly one Destination Vertex, and we try to move all the tokens to their Destinations, using the minimum number of swaps, i.e., operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that Token Swapping is $W[1]$-hard parameterized by the length $k$ of a shortest sequence of swaps. In fact, we prove that, for any computable function $f$, it cannot be solved in time $f(k)n^{o(k / \log k)}$ where $n$ is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial $n^{O(k)}$-time algorithm. We also consider two generalizations of the Token Swapping, namely Colored Token Swapping (where the tokens have different colors and tokens of the same color are indistinguishable), and Subset Token Swapping (where each token has a set of possible Destinations). To complement the hardness result, we prove that even the most general variant, Subset Token Swapping, is FPT in nowhere-dense graph classes. Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases.Comment: 23 pages, 7 Figure
-
Complexity of token swapping and its variants
'Springer Science and Business Media LLC', 2018Co-Authors: Bonnet Édouard, Miltzow Tillmann, Rzążewski PawełAbstract:AbstractIn the Token Swapping problem we are given a graph with a token placed on each Vertex. Each token has exactly one Destination Vertex, and we try to move all the tokens to their Destinations, using the minimum number of swaps, i.e., operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that Token Swapping is W[1]-hard parameterized by the length k of a shortest sequence of swaps. In fact, we prove that, for any computable function f, it cannot be solved in time f(k)no(k/logk) where n is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial nO(k)-time algorithm. We also consider two generalizations of the Token Swapping, namely Colored Token Swapping (where the tokens have colors and tokens of the same color are indistinguishable), and Subset Token Swapping (where each token has a set of possible Destinations). To complement the hardness result, we prove that even the most general variant, Subset Token Swapping, is FPT in nowhere-dense graph classes. Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases
-
Complexity of Token Swapping and Its Variants
'Springer Science and Business Media LLC', 2018Co-Authors: Bonnet Édouard, Miltzow Tillmann, Rzążewski PawełAbstract:In the Token Swapping problem we are given a graph with a token placed on each Vertex. Each token has exactly one Destination Vertex, and we try to move all the tokens to their Destinations, using the minimum number of swaps, i.e. operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that Token Swapping is W[ 1 ] -hard parameterized by the length k of a shortest sequence of swaps. In fact, we prove that, for any computable function f, it cannot be solved in time f(k) no ( k / log k ) where n is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial nO ( k )-time algorithm. We also consider two generalizations of the Token Swapping, namely Colored Token Swapping (where the tokens have colors and tokens of the same color are indistinguishable), and Subset Token Swapping (where each token has a set of possible Destinations). To complement the hardness result, we prove that even the most general variant, Subset Token Swapping, is FPT in nowhere-dense graph classes. Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases.SCOPUS: ar.jinfo:eu-repo/semantics/publishe
-
Complexity of token swapping and its variants
Springer Verlag, 2018Co-Authors: Bonnet Édouard, Tillmann Miltzow, Rzążewski PawełAbstract:International audienceIn the Token Swapping problem we are given a graph with a token placed on each Vertex. Each token has exactly one Destination Vertex, and we try to move all the tokens to their Destinations, using the minimum number of swaps, i.e., operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that Token Swapping is W [1]-hard parameterized by the length k of a shortest sequence of swaps. In fact, we prove that, for any computable function f , it cannot be solved in time f (k)n o(k/ log k) where n is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial n O(k)-time algorithm. We also consider two generalizations of the Token Swapping, namely Colored Token Swapping (where the tokens have colors and tokens of the same color are indistinguishable), and Subset Token Swapping (where each token has a set of possible Destinations). To complement the hardness result, we prove that even the most general variant, Subset Token Swapping, is FPT in nowhere-dense graph classes. Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases
Scott Shenker - One of the best experts on this subject based on the ideXlab platform.
-
ICALP - On the Resiliency of Randomized Routing Against Multiple Edge Failures
2016Co-Authors: Marco Chiesa, Ilya Nikolaevskiy, Andrei Gurtov, Aleksander Madry, Michael Shapira, Slobodan Mitrović, Scott ShenkerAbstract:We study the Static-Routing-Resiliency problem, motivated by routing on the Internet: Given a graph G = (V,E), a unique Destination Vertex d, and an integer constant c > 0, does there exist a static and Destination-based routing scheme such that the correct delivery of packets from any source s to the Destination d is guaranteed so long as (1) no more than c edges fail and (2) there exists a physical path from s to d? We embark upon a study of this problem by relating the edge-connectivity of a graph, i.e., the minimum number of edges whose deletion partitions G, to its resiliency. Following the success of randomized routing algorithms in dealing with a variety of problems (e.g., Valiant load balancing in the network design problem), we embark upon a study of randomized routing algorithms for the Static-Routing-Resiliency problem. For any k-connected graph, we show a surprisingly simple randomized algorithm that has expected number of hops O(|V|k) if at most k-1 edges fail, which reduces to O(|V|) if only a fraction t of the links fail (where t < 1 is a constant). Furthermore, our algorithm is deterministic if the routing does not encounter any failed link.
-
on the resiliency of randomized routing against multiple edge failures
International Colloquium on Automata Languages and Programming, 2016Co-Authors: Marco Chiesa, Ilya Nikolaevskiy, Andrei Gurtov, Aleksander Madry, Slobodan Mitrovic, Michael Shapira, Scott ShenkerAbstract:We study the Static-Routing-Resiliency problem, motivated by routing on the Internet: Given a graph G = (V,E), a unique Destination Vertex d, and an integer constant c > 0, does there exist a static and Destination-based routing scheme such that the correct delivery of packets from any source s to the Destination d is guaranteed so long as (1) no more than c edges fail and (2) there exists a physical path from s to d? We embark upon a study of this problem by relating the edge-connectivity of a graph, i.e., the minimum number of edges whose deletion partitions G, to its resiliency. Following the success of randomized routing algorithms in dealing with a variety of problems (e.g., Valiant load balancing in the network design problem), we embark upon a study of randomized routing algorithms for the Static-Routing-Resiliency problem. For any k-connected graph, we show a surprisingly simple randomized algorithm that has expected number of hops O(|V|k) if at most k-1 edges fail, which reduces to O(|V|) if only a fraction t of the links fail (where t < 1 is a constant). Furthermore, our algorithm is deterministic if the routing does not encounter any failed link.
-
Exploring the Limits of Static Failover Routing.
arXiv: Networking and Internet Architecture, 2014Co-Authors: Marco Chiesa, Ilya Nikolaevskiy, Aurojit Panda, Andrei Gurtov, Michael Schapira, Scott ShenkerAbstract:We present and study the Static-Routing-Resiliency problem, motivated by routing on the Internet: Given a graph $G$, a unique Destination Vertex $d$, and an integer constant $c>0$, does there exist a static and Destination-based routing scheme such that the correct delivery of packets from any source $s$ to the Destination $d$ is guaranteed so long as (1) no more than $c$ edges fail and (2) there exists a physical path from $s$ to $d$? We embark upon a systematic exploration of this fundamental question in a variety of models (deterministic routing, randomized routing, with packet-duplication, with packet-header-rewriting) and present both positive and negative results that relate the edge-connectivity of a graph, i.e., the minimum number of edges whose deletion partitions $G$, to its resiliency.
Michiel Smid - One of the best experts on this subject based on the ideXlab platform.
-
SODA - On the spanning and routing ratio of theta-four
2019Co-Authors: Prosenjit Bose, Jean-lou De Carufel, Darryl Hill, Michiel SmidAbstract:We present a routing algorithm for the Θ4-graph that computes a path between any two vertices s and t having length at most 17 times the Euclidean distance between s and t. To compute this path, at each step, the algorithm only uses knowledge of the location of the current Vertex, its (at most four) outgoing edges, the Destination Vertex, and one additional bit of information in order to determine the next edge to follow. This provides the first known online, local, competitive routing algorithm with constant routing ratio for the Θ4-graph, as well as improving the best known upper bound on the spanning ratio of these graphs from 237 to 17. We also show that without this additional bit of information, the routing ratio increases to 290 ≈ 17.03.
-
Improved Routing on the Delaunay Triangulation
2018Co-Authors: Nicolas Bonichon, Prosenjit Bose, Jean-lou De Carufel, Darryl Hill, Vincent Despré, Michiel SmidAbstract:A geometric graph G = (P,E) is a set of points in the plane and edges between pairs of points, where the weight of the edge is equal to the Euclidean distance between the points. In k-local routing we find a path through G from a source Vertex s to a Destination Vertex t, using only knowledge of the present location, the locations of s and t, and the k-neighbourhood of the current Vertex. We present an algorithm for 1-local routing on the Delaunay triangulation, and show that it finds a path between a source Vertex s and a target Vertex t that is not longer than 3.56|st|, improving the previous bound of 5.9.
-
ESA - Improved Routing on the Delaunay Triangulation.
2018Co-Authors: Nicolas Bonichon, Prosenjit Bose, Jean-lou De Carufel, Darryl Hill, Vincent Despré, Michiel SmidAbstract:A geometric graph G = (P,E) is a set of points in the plane and edges between pairs of points, where the weight of the edge is equal to the Euclidean distance between the points. In k-local routing we find a path through G from a source Vertex s to a Destination Vertex t, using only knowledge of the present location, the locations of s and t, and the k-neighbourhood of the current Vertex. We present an algorithm for 1-local routing on the Delaunay triangulation, and show that it finds a path between a source Vertex s and a target Vertex t that is not longer than 3.56|st|, improving the previous bound of 5.9.
-
On the Spanning and Routing Ratio of Theta-Four
arXiv: Computational Geometry, 2018Co-Authors: Prosenjit Bose, Jean-lou De Carufel, Darryl Hill, Michiel SmidAbstract:We present a routing algorithm for the Theta-4-graph that computes a path between any two vertices s and t having length at most 17 times the Euclidean distance between s and t. To compute this path, at each step, the algorithm only uses knowledge of the location of the current Vertex, its (at most four) outgoing edges, the Destination Vertex, and one additional bit of information in order to determine the next edge to follow. This provides the first known online, local, competitive routing algorithm with constant routing ratio for the Theta-4-graph, as well as improving the best known upper bound on the spanning ratio of these graphs from 237 to 17.