Search

Network coding (NC), when combined with multipath routing, enables a linear programming (LP) formulation for a multi-source multicast with intra-session network coding (MISNC) problem. However, it is still hard to solve using conventional methods due to the enormous scale of variables or constraints. In this paper, we try to solve this problem in terms of throughput maximization from an algorithmic perspective. We propose a novel formulation based on the extreme flow decomposition technique, which facilitates the design and analysis of approximation and online algorithms. For the offline scenario, we develop a fully polynomial time approximation scheme (FPTAS) which can find a (1 + ω) -approximation solution for any specified ω > 0. For the online scenario, we develop an online primal-dual algorithm which proves O (1) -competitive and violates link capacities by a factor of O (log ⁡ m) , where m is the link number. The proposed algorithms share an elegant primal-dual form and thereby have inherent advantages of simplicity, efficiency, and scalability. To better understand the proposed approach, we devise delicate numerical examples on an extended butterfly network to validate the effects of algorithmic parameters and make an interesting comparison between the offline and online cases. We also perform large-scale simulations on real networks to validate the effectiveness of the proposed FPTAS and online algorithm. • Extreme flow decomposition technique for intra-session network coding. • Offline FPTAS with provable approximation ratio. • Online primal-dual algorithm with provable competitive ratio. • Large-scale experiments using public datasets. [ABSTRACT FROM AUTHOR]

We introduce and study two natural generalizations of the Connected Vertex Cover (VC) problem: the p -Edge-Connected and p -Vertex-Connected VC problem (where p ≥ 2 is a fixed integer). We obtain an 2 O (p k) n O (1) -time algorithm for p -Edge-Connected VC and an 2 O (k 2) n O (1) -time algorithm for p -Vertex-Connected VC. Thus, like Connected VC, both constrained VC problems are FPT. Furthermore, like Connected VC, neither problem admits a polynomial kernel unless NP ⊆ coNP/poly, which is highly unlikely. We prove however that both problems admit time efficient polynomial sized approximate kernelization schemes. Finally, we describe a 2 (p + 1) -approximation algorithm for the p -Edge-Connected VC. The proofs for the new VC problems require more sophisticated arguments than for Connected VC. In particular, for the approximation algorithm we use Gomory-Hu trees and for the approximate kernels a result on small-size spanning p -vertex/edge-connected subgraphs of a p -vertex/edge-connected graph by Nishizeki and Poljak (1994) [30] and Nagamochi and Ibaraki (1992) [27]. [ABSTRACT FROM AUTHOR]

We introduce a novel domination problem, which we call Dual Domination (DD). We assume that the nodes in a network are partitioned into two categories: Positive nodes (V +) and negative nodes (V −). We study the Maximum Bounded Dual Domination , where, given a bound k , the problem is to find a set D ⊆ V + , which maximizes the number of nodes dominated in V + , dominating at most k nodes in V −. We show that such problem is hard to approximate to a factor better than (1 − 1 / e). We give a polynomial time algorithm with approximation guaranteed (1 − e − 1 / Δ) , where Δ represents the maximum number of neighbors in V + of any node in V − , and an O (| V | k 2) time algorithm to solve the problem on trees. We also study two related problems named Maximum Dual Domination and minimum Negative Dual Domination. For both problems, we show hardness results and provide O (| V |) time algorithms on trees. [ABSTRACT FROM AUTHOR]

For several decades, much effort has been put into identifying classes of CNF formulas whose satisfiability can be decided in polynomial time. Classic results are the linear-time tractability of Horn formulas (Aspvall, Plass, and Tarjan, 1979) and Krom (i.e., 2CNF) formulas (Dowling and Gallier, 1984). Backdoors, introduced by Williams, Gomes and Selman (2003), gradually extend such a tractable class to all formulas of bounded distance to the class. Backdoor size provides a natural but rather crude distance measure between a formula and a tractable class. Backdoor depth, introduced by Mählmann, Siebertz, and Vigny (2021), is a more refined distance measure, which admits the utilization of different backdoor variables in parallel. We propose FPT approximation algorithms to compute backdoor depth into the classes Horn and Krom. This leads to a linear-time algorithm for deciding the satisfiability of formulas of bounded backdoor depth into these classes. [ABSTRACT FROM AUTHOR]

We study the problem of maximizing a monotone submodular function subject to a Multiple Knapsack constraint. The input is a set I of items, each has a non-negative weight, and a set of bins of arbitrary capacities. Also, we are given a submodular, monotone and non-negative function f over subsets of the items. The objective is to find a packing of a subset of items A ⊆ I in the bins such that f (A) is maximized. Our main result is an almost optimal polynomial time (1 − e − 1 − ε) -approximation algorithm for the problem, for any ε > 0. The algorithm relies on a structuring technique which converts a general multiple knapsack constraint to a constraint in which the bins are partitioned into groups of exponentially increasing cardinalities, each consisting of bins of uniform capacity. We derive the result by combining structuring with a refined analysis of techniques for submodular optimization subject to knapsack constraints. [ABSTRACT FROM AUTHOR]

We study the approximability of the NP-complete Maximum Minimal Feedback Vertex Set problem. Informally, this natural problem seems to lie in an intermediate space between two more well-studied problems of this type: Maximum Minimal Vertex Cover , for which the best achievable approximation ratio is n , and Upper Dominating Set , which does not admit any n 1 − ϵ approximation. We confirm and quantify this intuition by showing the first non-trivial polynomial time approximation for Maximum Minimal Feedback Vertex Set with a ratio of O (n 2 / 3) , as well as a matching hardness of approximation bound of n 2 / 3 − ϵ , improving the previously known hardness of n 1 / 2 − ϵ. Having settled the problem's approximability in polynomial time, we move to the context of super-polynomial time. We devise a generalization of our approximation algorithm which, for any desired approximation ratio r , produces an r -approximate solution in time n O (n / r 3 / 2). This time-approximation trade-off is essentially tight under the ETH. [ABSTRACT FROM AUTHOR]

We study clustering problems such as k -Median, k -Means, and Facility Location in graphs of low highway dimension, which is a graph parameter modeling transportation networks. It was previously shown that approximation schemes for these problems exist, which either run in quasi-polynomial time (assuming constant highway dimension) (Feldmann et al., 2018) [8] or run in FPT time (parameterized by the number of clusters k , the highway dimension, and the approximation factor) (Becker et al., 2018; Braverman et al., 2021) [9,10]. In this paper we show that a polynomial-time approximation scheme (PTAS) exists (assuming constant highway dimension). We also show that the considered problems are NP-hard on graphs of highway dimension 1. [ABSTRACT FROM AUTHOR]

• The placement of data and the scheduling of request are studied in edge caching. • Network unreliability and limited storage and bandwidth resources are considered. • Two algorithms with different computation complexity and cache efficiency are developed. • The experiments are conducted to evaluate the performance of proposed caching strategies. Edge caching is a prevailing media delivery technology where data is hosted at the edge nodes with computing and storage capability in close proximity to users, in order to expand the backhaul network capacity and enhance users' quality of experience (QoE). The existing work in this area often neglects the fact that large-scale distributed cache networks are not particularly reliable and many edge nodes are prone to failure. In this paper we investigate and develop a novel, cooperative caching mechanism for content placement and request routing. We aim to minimize the content access delay and achieve the optimization in polynomial time, taking into account failures in an unreliable network environment with limited edge storage and bandwidth. We introduce two optimization algorithms: 1) a primal-dual algorithm that is based on the Lagrangian dual decomposition and subgradient method, and 2) a greedy-based approximation algorithm with a proven approximation ratio. Numerical results show that the proposed algorithms outperform other comparative approaches in synthetic and real network environments, and the approximation algorithm is particularly suitable for networking scenarios with sparse node connectivity and resources in short supply. [ABSTRACT FROM AUTHOR]

A chordless cycle, or equivalently a hole, in a graph G is an induced subgraph of G which is a cycle of length at least 4. We prove that the Erdős-Pósa property holds for chordless cycles, which resolves the major open question concerning the Erdős-Pósa property. Our proof for chordless cycles is constructive: in polynomial time, one can find either k + 1 vertex-disjoint chordless cycles, or c 1 k 2 log ⁡ k + c 2 vertices hitting every chordless cycle for some constants c 1 and c 2. It immediately implies an approximation algorithm of factor O (opt log ⁡ opt) for Chordal Vertex Deletion. We complement our main result by showing that chordless cycles of length at least ℓ for any fixed ℓ ≥ 5 do not have the Erdős-Pósa property. [ABSTRACT FROM AUTHOR]

Translocation has been long learned as a basic operation to rearrange the structure of a genome. Translocation sorting asks to find a shortest sequence of translocations that transforms one genome into another, which has attracted attention of many scientists in algorithm design. Signed translocation sorting can be solved in polynomial time. Unsigned translocation sorting turns out to be NP-Hard and Max-SNP-Hard. The best known approximation algorithm by now for unsigned translocation sorting can achieve a performance ratio 1.408. In this paper, we propose a new approximation algorithm for unsigned translocation sorting which can achieve a asymptotic performance ratio 1.375. [ABSTRACT FROM AUTHOR]

In this paper we focus on problems inapproximable in polynomial time and explore how quickly their approximability improves as the allowed running time is gradually increased from polynomial to (sub-)exponential. We tackle a number of problems: For Min Independent Dominating Set , Max Induced Path , Forest and Tree , for any r ( n ) , a simple, known scheme gives an approximation ratio of r in time roughly r n / r . We show that, if this running time could be significantly improved, the ETH would fail. For Max Minimal Vertex Cover we give a r -approximation in time 2 n / r . We match this with a similarly tight result. We also give a log ⁡ r -approximation for Min ATSP in time 2 n / r and an r -approximation for Max Grundy Coloring in time r n / r . Finally, we investigate the approximability of Min Set Cover , when measuring the running time as a function of the number of sets in the input. [ABSTRACT FROM AUTHOR]

A complete weighted graph G = ( V , E , w ) is called Δ β -metric, for some β ≥ 1 / 2 , if G satisfies the β -triangle inequality, i.e., w ( u , v ) ≤ β ⋅ ( w ( u , x ) + w ( x , v ) ) for all vertices u , v , x ∈ V . Given a Δ β -metric graph G = ( V , E , w ) and a center c ∈ V , and an integer p , the Δ β -Star p -Hub Center problem ( Δ β -S p HCP) is to find a depth-2 spanning tree T of G rooted at c such that c has exactly p children (also called hubs) and the diameter of T is minimized. In this paper, we study Δ β -S p HCP for all β ≥ 1 2 . We show that for any ϵ > 0 , to approximate the Δ β -S p HCP to a ratio g ( β ) − ϵ is NP-hard and give r ( β ) -approximation algorithms for the same problem where g ( β ) and r ( β ) are functions of β . A subclass of metric graphs is identified that Δ β -S p HCP is polynomial-time solvable. Moreover, some r ( β ) -approximation algorithms given in this paper meet approximation lower bounds. [ABSTRACT FROM AUTHOR]

We study the multi-budgeted version of the metric Survivable Network Design Problem (SND) (Jain, 2001), also known as Steiner Network problem, where besides the usual connectivity requirements (i.e., lower bound on the number edge-disjoint paths) between pre-specified pairs of points, we are also asked to satisfy a set of extra linear constraints (the budgets). Based on combinatorial properties of extreme point solutions of the natural LP relaxation of the problem and using the iterative method, we design new approximation algorithms with the following performance guarantee: if any edge participates in at most f ∈ N budgets, then we show how we can device an ( f + 2 , f + 2 ) bi-criteria approximation algorithm in polynomial time i.e., return a solution with cost at most ( 2 + f ) times the optimal one with a potential budget overflow bounded from above by the same factor. In other words, the approximation and budget violation guarantee we achieve is a linear function of the maximum frequency among all the edges in the budgets, as opposed to a function of the number of budgets themselves and this constitutes a strict improvement over the previous approaches. Our approach is flexible enough and we demonstrate how it can be used to provide a ( 4 , 4 ) bi-criteria algorithm for the Minimum Weighted Bounded Degree version of the SND problem in which we have the standard SND connectivity constraints and, additionally, for every vertex v in the graph we have an upper bound on the sum of the weights of the edges incident to that edge in any feasible solution. These problems, besides their obvious theoretical interest, have numerous real life applications from Cloud Computing to Optical Networking systems. [ABSTRACT FROM AUTHOR]

We consider the design of dominant strategy incentive compatible, revenue-maximizing auctions for an indivisible good, when bidders' values are drawn from a correlated distribution. For independent distributions, Myerson showed that the optimal auction for risk-neutral bidders remains incentive compatible regardless of bidders' risk attitudes. We show that, for correlated distributions, the same is true when only two bidders are involved, whereas for more bidders, randomization can generate strictly more revenue. However, for risk-neutral bidders, we show this gain is never more than a 5 3 -factor. This is a consequence of two results of independent interest: (1) a polynomial-time derandomization of auctions for two bidders; (2) a polynomial-time computable deterministic auction that 5 3 -approximates the optimal revenue extractable from risk-neutral bidders. Moreover, we give a polynomial-time algorithm to compute optimal auctions for a constant number of bidders, and for any number of bidders we give polynomial-time algorithms with approximation factors arbitrarily close to 3 2 . [ABSTRACT FROM AUTHOR]

Line of Sight (LoS) networks were designed to model wireless communication in settings which may contain obstacles. For fixed positive integer d , and positive integer ω , a graph G = (V , E) is a (d -dimensional) LoS network with range parameter ω if it can be embedded in a finite cube of the d -dimensional integer grid so that each pair of vertices in V are adjacent if and only if their embedding coordinates differ only in one position and such difference is less than ω. In this paper we investigate a dynamic programming (DP) approach which can be used to obtain efficient algorithmic solutions for various combinatorial problems in LoS networks. In particular DP solves the Maximum Independent Set (MIS) problem in LoS networks optimally, for any ω , on narrow LoS networks (i.e. networks which can be embedded in a k × k ... × k × n region, for some fixed k independent of n). In the unrestricted case it has been shown that the (decision version of the) problem is NP-hard when 2 < ω = O (n 1 − δ) , for fixed 0 < δ < 1. We describe how DP can be used as a building block in the design of good approximation algorithms in this case. In particular we present a semi-online polynomial-time approximation scheme for the MIS problem in narrow d -dimensional LoS networks, as well as a polynomial-time 2-approximation algorithm and a fast polynomial time approximation scheme for the MIS problem in arbitrary d -dimensional LoS networks. Finally we comment on how the approach can be adapted to prove similar results for a number of important optimization problems in LoS networks. [ABSTRACT FROM AUTHOR]