Let G be a connected graph and k be a positive integer. A vertex subset D of G is a k-hop connected dominating set if the subgraph of G induced by D is connected, and for every vertex v in G, there is a vertex u in D ...
详细信息
Let G be a connected graph and k be a positive integer. A vertex subset D of G is a k-hop connected dominating set if the subgraph of G induced by D is connected, and for every vertex v in G, there is a vertex u in D such that the distance between v and u in G is at most k. We study the problem of finding a minimum k-hop connected dominating set of a graph (Mink-CDS). We prove that Mink-CDS is NP-hard on planar bipartite graphs of maximum degree 4. We also prove that Mink-CDS is APX-complete on bipartite graphs of maximum degree 4. We present inapproximability thresholds for Mink-CDS on bipar- tite and on (1, 2)-split graphs. Interestingly, one of these thresholds is a parameter of the input graph which is not a function of its number of vertices. We also discuss the complex- ity of computing this graph parameter. On the positive side, we show an approximation algorithm for Mink-CDS. When k = 1, we present two new approximation algorithms for the weighted version of the problem, one of them restricted to graphs with a poly- nomially bounded number of minimal separators. Finally, also for the weighted variant of the problem where k = 1, we discuss an integer linear programming formulation and conduct a polyhedral study of its associated polytope.
In the Maximum Duo-Preservation String Mapping problem we are given two strings and wish to map the letters of the former to the letters of the latter as to maximise the number of duos. A duo is a pair of consecutive ...
详细信息
A k-dominating set in a graph G = (V,E) is a set U ¢ V such that ever vertex of G is either in U or has at least k neighbors in U. In this paper we give simple distributed approximation algorithms in the local mo...
详细信息
A k-dominating set in a graph G = (V,E) is a set U ¢ V such that ever vertex of G is either in U or has at least k neighbors in U. In this paper we give simple distributed approximation algorithms in the local model for the minimum k-dominating set problem for k ≥ 2 in graphs with no K3,h-minor and graphs with no K4,4-minor. In particular, this gives fast distributed approximations for graphs of bounded genus and linklessly embeddable graphs. The algorithms give a constant approximation ratio and run in a constant number of rounds. In addition, we will give a (1 + €)-approximation for an arbitrary fixed € > 0 which runs in O(log∗ n) rounds where n is the order of a graph.
Stochastic optimization has established itself as a major method to handle uncertainty in various optimization problems by modeling the uncertainty by a probability distribution over possible ***,the main focus in st...
详细信息
Stochastic optimization has established itself as a major method to handle uncertainty in various optimization problems by modeling the uncertainty by a probability distribution over possible ***,the main focus in stochastic optimization has been various stochastic mathematical programming(such as linear programming,convex programming).In recent years,there has been a surge of interest in stochastic combinatorial optimization problems from the theoretical computer science *** this article,we survey some of the recent results on various stochastic versions of classical combinatorial optimization *** most problems in this domain are NP-hard(or#P-hard,or even PSPACE-hard),we focus on the results which provide polynomial time approximation algorithms with provable approximation *** discussions are centered around a few representative problems,such as stochastic knapsack,stochastic matching,multi-armed bandit *** use these examples to introduce several popular stochastic models,such as the fixed-set model,2-stage stochastic optimization model,stochastic adaptive probing model etc,as well as some useful techniques for designing approximation algorithms for stochastic combinatorial optimization problems,including the linear programming relaxation approach,boosted sampling,content resolution schemes,Poisson approximation *** also provide some open research questions along the *** purpose is to provide readers a quick glimpse to the models,problems,and techniques in this area,and hopefully inspire new contributions.
In the Euclidean TSP with neighborhoods (TSPN), we are given a collection of n regions (neighborhoods) and we seek a shortest tour that visits each region. As a generalization of the classical Euclidean TSP, TSPN is a...
详细信息
We reveal a connection between coordination mechanisms for unrelated machine scheduling and cost-sharing protocols. Using this connection, we interpret three coordination mechanisms from the recent literature as Shapl...
详细信息
Many known optimal NP-hardness of approximation results are reductions from a problem called LABEL-COVER. The input is a bipartite graph G = (L, R, E) and each edge e = (x, y) ∈ E carries a projection π_e that maps ...
详细信息
ISBN:
(纸本)9781510836358
Many known optimal NP-hardness of approximation results are reductions from a problem called LABEL-COVER. The input is a bipartite graph G = (L, R, E) and each edge e = (x, y) ∈ E carries a projection π_e that maps labels to x to labels to y. The objective is to find a labeling of the vertices that satisfies as many of the projections as possible. It is believed that the best approximation ratio efficiently achievable for LABEL-COVER is of the form N~(-c) where N = nk, n is the number of vertices, k is the number of labels, and 0 < c < 1 is some constant. Inspired by a framework originally developed for DENSEST k-SUBGRAPH, we propose a "log density threshold" for the approximability of Label-Cover. Specifically, we suggest the possibility that the Label-Cover approximation problem undergoes a computational phase transition at the same threshold at which local algorithms for its random counterpart fail. This threshold is N~(3-2{sqroot})≈N~(-0.17). We then design, for any ε > 0, a polynomial-time approximation algorithm for semi-random LABEL-COVER whose approximation ratio is N~(3-2{sqroot}+ε). In our semi-random model, the input graph is random (or even just expanding), and the projections on the edges are arbitrary. For worst-case LABEL-COVER we show a polynomial-time algorithm whose approximation ratio is roughly N~(-0.233). The previous best efficient approximation ratio was N~(-0.25). We present some evidence towards an N~(-c) threshold by constructing integrality gaps for N~(Ω(1)) rounds of the Sum-of-squares/Lasserre hierarchy of the natural relaxation of Label Cover. For general 2CSP the "log density threshold" is N~(-0.25), and we give a polynomial-time algorithm in the semi-random model whose approximation ratio is N~(-0.25+ε) for any ε>0.
We study the 0-Low Rank approximation Problem, where the goal is, given an m×n matrix A, to output a rank-k matrix A for which kA-Ak0 is minimized. Here, for a matrix B, kBk0 denotes the number of its non-zero en...
详细信息
We initiate the study of approximating the largest induced expander in a given graph G. Given a Δ-regular graph G with n vertices, the goal is to find the set with the largest induced expansion of size at least δ...
详细信息
ISBN:
(纸本)9781510836358
We initiate the study of approximating the largest induced expander in a given graph G. Given a Δ-regular graph G with n vertices, the goal is to find the set with the largest induced expansion of size at least δ·n. We design a bi-criteria approximation algorithm for this problem; if the optimum has induced spectral expansion λ our algorithm returns a λ/log~2 δ exp(Δ/λ)-(spectral) expander of size at least δn (up to constants). Our proof introduces and employs a novel semidefinite programming relaxation for the largest induced expander problem. We expect to see further applications of our SDP relaxation in graph partitioning problems. In particular, because of the close connection to the small set expansion problem, one may be able to obtain new insights into the unique games problem.
The multiprocessor scheduling problem is one of the classic NP-hard optimization problems. The goal of this paper is to prepare algorithms for scheduling problem where set of tasks is performed on parallel identical p...
详细信息
暂无评论