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) is an element of E carries a projection p...
详细信息
ISBN:
(纸本)9781611974782
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) is an element of E carries a projection pi(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 N3-2 root 2 approximate to N-0.17 We then design, for any epsilon > 0, a polynomial-time approximation algorithm for semi random LABEL-COVER whose approximation ratio is N3-2 root 2+epsilon. 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-Omega(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+epsilon for any epsilon > 0.
The MAXIMUM CARPOOL MATCHING problem is a star packing problem in directed graphs. Formally, given a directed graph G = (V, A), a capacity function c : V -> N, and a weight function w : A -> R, a feasible carpoo...
详细信息
ISBN:
(数字)9783319587479
ISBN:
(纸本)9783319587479;9783319587462
The MAXIMUM CARPOOL MATCHING problem is a star packing problem in directed graphs. Formally, given a directed graph G = (V, A), a capacity function c : V -> N, and a weight function w : A -> R, a feasible carpool matching is a triple (P, D, M), where P (passengers) and D (drivers) form a partition of V, and M is a subset of A boolean AND (P x D), under the constraints that for every vertex d is an element of D, deg(in)(M) (d) <= c(d), and for every vertex p is an element of P, dego(ut)(M) (p) <= 1. In the MAXIMUM CARPOOL MATCHING problem we seek for a matching (P, D, M) that maximizes the total weight of M. The problem arises when designing an online carpool service, such as Zimride [1], that tries to connect between passengers and drivers based on (arbitrary) similarity function. The problem is known to be NP-hard, even for uniform weights and without capacity constraints. We present a 3-approximation algorithm for the problem and 2-approximation algorithm for the unweighted variant of the problem.
We initiate the study of approximating the largest induced expander in a given graph G. Given a Delta-regular graph G with n vertices, the goal is to find the set with the largest induced expansion of size at least de...
详细信息
ISBN:
(纸本)9781611974782
We initiate the study of approximating the largest induced expander in a given graph G. Given a Delta-regular graph G with n vertices, the goal is to find the set with the largest induced expansion of size at least delta . n. We design a bi-criteria approximation algorithm for this problem;if the optimum has induced spectral expansion lambda our algorithm returns a lambda/log(2)delta exp(Delta/lambda)-(spectral) expander of size at least (5n (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.
Distributed cloud networking builds on network functions virtualization (NFV) and software defined networking (SDN) to enable the deployment of network services in the form of elastic virtual network functions (VNFs) ...
详细信息
ISBN:
(纸本)9781509053360
Distributed cloud networking builds on network functions virtualization (NFV) and software defined networking (SDN) to enable the deployment of network services in the form of elastic virtual network functions (VNFs) instantiated over general purpose servers at distributed cloud locations. We address the design of fast approximation algorithms for the NFV service distribution problem (NSDP), whose goal is to determine the placement of VNFs, the routing of service flows, and the associated allocation of cloud and network resources that satisfy client demands with minimum cost. We show that in the case of load-proportional costs, the resulting fractional NSDP can be formulated as a multi-commodity-chain flow problem on a cloud-augmented graph, and design a queue-length based algorithm, named QNSD, that provides an O (is an element of) approximation in time O (1/is an element of). We then address the case in which resource costs are a function of the integer number of allocated resources and design a variation of QNSD that effectively pushes for flow consolidation into a limited number of active resources to minimize overall cloud network cost.
As we are currently in the information age, people expect access to information to exist by default. In order to facilitate the communication of knowledge, efficient networks must be built. In particular, the networks...
详细信息
As we are currently in the information age, people expect access to information to exist by default. In order to facilitate the communication of knowledge, efficient networks must be built. In particular, the networks must be built satisfying some con- straints while minimizing cost or time. These constraints often make these problems NP-hard. In this thesis, we investigate two different sets of problems: communicating information quickly and building cheap networks. In the communication problems, the goal is to minimize the number of rounds of communication. In the network design problems the goal is to construct a network of minimum cost. First, we study the communication problem of computing a minimum time sched- ule to spread rumors in a given graph under the telephone, radio, and wireless (also called edge-star) models. In all of these communication models, the communication happens in discrete rounds. In the telephone model, a matching is given every round and matched nodes exchange all their information with each other. In the radio model, any subset of nodes can broadcast in a round but only nodes with a single broad- casting neighbor get a message. If a node has two or more neighbors broadcasting, they receive no messages due to interference. In the wireless model, any subset of nodes can broadcast in a round and a non-broadcasting node can tune to listen to ex- actly one of its neighbors. The various rumor spreading problems assume a message at several or all nodes and that each message must reach some target node or set of nodes. The goal is to deliver all messages to their destinations in a minimum num- ber of rounds. The various problems we study include gossip, multicommodity, and asymmetric multicommodity. In the gossip problem, the goal is to communicate mes- sages from every node to every other node. In multicommodity, pairs of nodes are given must exchange their messages with each other. In asymmetric multicommodity, ordered pairs of nodes are give
Certain answers are a widely accepted semantics of query answering over incomplete databases. Since their computation is a coNP-hard problem, recent research has focused on developing evaluation algorithms with correc...
详细信息
Certain answers are a widely accepted semantics of query answering over incomplete databases. Since their computation is a coNP-hard problem, recent research has focused on developing evaluation algorithms with correctness guarantees, that is, techniques computing a sound but possibly incomplete set of certain answers. In this paper, we show how novel evaluation algorithms with correctness guarantees can be developed leveraging conditional tables and the conditional evaluation of queries, while retaining polynomial time data complexity.
The celebrated Cheeger's Inequality (Alon and Milman 1985;Alon 1986) establishes a bound on the edge expansion of a graph via its spectrum. This inequality is central to a rich spectral theory of graphs, based on ...
详细信息
The celebrated Cheeger's Inequality (Alon and Milman 1985;Alon 1986) establishes a bound on the edge expansion of a graph via its spectrum. This inequality is central to a rich spectral theory of graphs, based on studying the eigenvalues and eigenvectors of the adjacency matrix (and other related matrices) of graphs. It has remained open to define a suitable spectral model for hypergraphs whose spectra can be used to estimate various combinatorial properties of the hypergraph. In this article, we introduce a new hypergraph Laplacian operator generalizing the Laplacian matrix of graphs. In particular, the operator is induced by a diffusion process on the hypergraph, such that within each hyperedge, measure flows from vertices having maximum weighted measure to those having minimum. Since the operator is nonlinear, we have to exploit other properties of the diffusion process to recover the Cheeger's Inequality that relates hyperedge expansion with the "second eigenvalue" of the resulting Laplacian. However, we show that higher-order spectral properties cannot hold in general using the current framework. Since higher-order spectral properties do not hold for the Laplacian operator, we instead use the concept of procedural minimizers to consider higher-order Cheeger-like inequalities. For any k is an element of N, we give a polynomial-time algorithm to compute an O(log r)-approximation to the kth procedural minimizer, where r is the maximum cardinality of a hyperedge. We show that this approximation factor is optimal under the SSE hypothesis (introduced by Raghavendra and Steurer (2010)) for constant values of k. Moreover, using the factor-preserving reduction from vertex expansion in graphs to hypergraph expansion, we show that all our results for hypergraphs extend to vertex expansion in graphs.
We study the following geometric representation problem: Given a graph whose vertices correspond to axis-aligned rectangles with fixed dimensions, arrange the rectangles without overlaps in the plane such that two rec...
详细信息
We study the following geometric representation problem: Given a graph whose vertices correspond to axis-aligned rectangles with fixed dimensions, arrange the rectangles without overlaps in the plane such that two rectangles touch if the graph contains an edge between them. This problem is called Contact Representation of Word Networks (Crown) since it formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. Crown is known to be NP-hard, and there are approximation algorithms for certain graph classes for the optimization version, Max-Crown, in which realizing each desired adjacency yields a certain profit. We present the first O(1)-approximation algorithm for the general case, when the input is a complete weighted graph, and for the bipartite case. Since the subgraph of realized adjacencies is necessarily planar, we also consider several planar graph classes (namely stars, trees, outerplanar, and planar graphs), improving upon the known results. For some graph classes, we also describe improvements in the unweighted case, where each adjacency yields the same profit. Finally, we show that the problem is APX-complete on bipartite graphs of bounded maximum degree.
We consider a well-studied multi-echelon (deterministic) inventory control problem, known in the literature as the one-warehouse multi-retailer (OWMR) problem. We propose a simple and fast 2-approximation algorithm fo...
详细信息
We consider a well-studied multi-echelon (deterministic) inventory control problem, known in the literature as the one-warehouse multi-retailer (OWMR) problem. We propose a simple and fast 2-approximation algorithm for this NP-hard problem, by recombining the solutions of single-echelon relaxations at the warehouse and at the retailers. We then show that our approach remains valid under quite general assumptions on the cost structures and under capacity constraints at some retailers. In particular, we present the first approximation algorithms for the OWMR problem with nonlinear holding costs, truckload discount on procurement costs, or with capacity constraints at some retailers. In all cases, the procedure is purely combinatorial and can be implemented to run in low polynomial time.
The projection games (aka Label Cover) problem is of great importance to the field of approximation algorithms, since most of the NP-hardness of approximation results we know today are reductions from Label Cover. In ...
详细信息
The projection games (aka Label Cover) problem is of great importance to the field of approximation algorithms, since most of the NP-hardness of approximation results we know today are reductions from Label Cover. In this paper we design several approximation algorithms for projection games: (1) A polynomial-time approximation algorithm that improves on the previous best approximation by Charikar et al. (Algorithmica 61(1):190-206, 2011). (2) A sub-exponential time algorithm with much tighter approximation for the case of smooth projection games. (3) A polynomial-time approximation scheme (PTAS) for projection games on planar graphs and a tight running time lower bound for such approximation schemes. The conference version of this paper had only the PTAS but not the running time lower bound.
暂无评论