Graph clustering is a fundamental task in network analysis where the goal is to detect sets of nodes that are well-connected to each other but sparsely connected to the rest of the graph. We present faster approximati...
详细信息
ISBN:
(纸本)9798400701245
Graph clustering is a fundamental task in network analysis where the goal is to detect sets of nodes that are well-connected to each other but sparsely connected to the rest of the graph. We present faster approximation algorithms for an NP-hard parameterized clustering framework called LambdaCC, which is governed by a tunable resolution parameter and generalizes many other clustering objectives such as modularity, sparsest cut, and cluster deletion. Previous LambdaCC algorithms are either heuristics with no approximation guarantees, or computationally expensive approximation algorithms. We provide fast new approximation algorithms that can be made purely combinatorial. These rely on a new parameterized edge labeling problem we introduce that generalizes previous edge labeling problems that are based on the principle of strong triadic closure and are of independent interest in social network analysis. Our methods are orders of magnitude more scalable than previous approximation algorithms and our lower bounds allow us to obtain a posteriori approximation guarantees for previous heuristics that have no approximation guarantees of their own.
Finding a single best solution is the most common objective in combinatorial optimization problems. However, such a single solution may not be applicable to real-world problems as objective functions and constraints a...
详细信息
ISBN:
(纸本)9781577358800
Finding a single best solution is the most common objective in combinatorial optimization problems. However, such a single solution may not be applicable to real-world problems as objective functions and constraints are only "approximately" formulated for original real-world problems. To solve this issue, finding multiple solutions is a natural direction, and diversity of solutions is an important concept in this context. Unfortunately, finding diverse solutions is much harder than finding a single solution. To cope with the difficulty, we investigate the approximability of finding diverse solutions. As a main result, we propose a framework to design approximation algorithms for finding diverse solutions, which yields several outcomes including constant-factor approximation algorithms for finding diverse matchings in graphs and diverse common bases in two matroids and PTASes for finding diverse minimum cuts and interval schedulings.
Given a simple polygon P, the minimum convex cover problem seeks to cover P with the fewest convex polygons that lie within P. The maximum hidden set problem seeks to place within P a maximum cardinality set of points...
详细信息
ISBN:
(纸本)9798350318944
Given a simple polygon P, the minimum convex cover problem seeks to cover P with the fewest convex polygons that lie within P. The maximum hidden set problem seeks to place within P a maximum cardinality set of points no two of which see each other. We give constant factor approximation algorithms for both problems. Previously, the best approximation factor for the minimum convex cover was logarithmic;for the maximum hidden set problem, no approximation algorithm was known.
We consider two-cost network design models in which edges of the input graph have an associated cost and length. We build upon recent advances in hop-constrained oblivious routing to obtain two sets of results. We add...
详细信息
We consider the problem of assigning students to schools, when students have different utilities for schools and schools have capacity. There are additional group fairness considerations over students that can be capt...
详细信息
We introduce efficient (1 + epsilon)-approximation algorithms for the binary matrix factorization (BMF) problem, where the inputs are a matrix A is an element of{0, 1}(nxd), a rank parameter k > 0, as well as an ac...
详细信息
We introduce efficient (1 + epsilon)-approximation algorithms for the binary matrix factorization (BMF) problem, where the inputs are a matrix A is an element of{0, 1}(nxd), a rank parameter k > 0, as well as an accuracy parameter epsilon > 0, and the goal is to approximate A as a product of low-rank factors U is an element of{0, 1}(nxk) and V is an element of {0, 1}(kxd). Equivalently, we want to find U and V that minimize the Frobenius loss parallel to UV - A parallel to(2)(F). Before this work, the state-of-the-art for this problem was the approximation algorithm of Kumar et al. [ICML 2019], which achieves a C-approximation for some constant C >= 576. We give the first (1 + epsilon)-approximation algorithm using running time singly exponential in k, where k is typically a small integer. Our techniques generalize to other common variants of the BMF problem, admitting bicriteria (1 + epsilon)-approximation algorithms for L-p loss functions and the setting where matrix operations are performed in F-2. Our approach can be implemented in standard big data models, such as the streaming or distributed models.
We study the approximability of an existing framework for clustering edge-colored hypergraphs, which is closely related to chromatic correlation clustering and is motivated by machine learning and data mining applicat...
详细信息
We study the approximability of an existing framework for clustering edge-colored hypergraphs, which is closely related to chromatic correlation clustering and is motivated by machine learning and data mining applications where the goal is to cluster a set of objects based on multiway interactions of different categories or types. We present improved approximation guarantees based on linear programming, and show they are tight by proving a matching integrality gap. Our results also include new approximation hardness results, a combinatorial 2-approximation whose runtime is linear in the hypergraph size, and several new connections to well-studied objectives such as vertex cover and hypergraph multiway cut.
Emerging reconfigurable optical communication technologies allow to enhance datacenter topologies with demand-aware links optimized towards traffic patterns. This paper studies the algorithmic problem of jointly optim...
详细信息
ISBN:
(数字)9798350383508
ISBN:
(纸本)9798350383515
Emerging reconfigurable optical communication technologies allow to enhance datacenter topologies with demand-aware links optimized towards traffic patterns. This paper studies the algorithmic problem of jointly optimizing topology and routing in such demand-aware networks to minimize congestion, along two dimensions: (1) splittable or unsplittable flows, and (2) whether routing is segregated, i.e., whether routes can or cannot combine both demand-aware and demand-oblivious (static) *** splittable and segregated routing, we show that the problem is generally 2-approximable, but APX-hard even for uniform demands induced by a bipartite demand graph. For unsplittable and segregated routing, we establish upper and lower bounds of O (log m/ log log m) and Ω (log m/ log log m), respectively, for polynomial-time approximation algorithms, where m is the number of static links. We further reveal that under un-/splittable and non-segregated routing, even for demands of a single source (resp., d estina tion), the problem cannot be approximated better than $\Omega \left({\frac{{{c_{\max }}}}{{{c_{\min }}}}}\right)$ unless P=NP, where c
max
(resp., c
min
) denotes the maximum (resp., minimum) capacity. It remains NP-hard for uniform capacities, but is tractable for a single commodity and uniform *** trace-driven simulations show a significant reduction in network congestion compared to existing solutions.
Given a connected vertex-weighted graph G, the maximum weight internal spanning tree (MaxwIST) problem asks for a spanning tree of G that maximizes the total weight of internal nodes. This problem is NP-hard and APX-h...
详细信息
We present an (e(O(p)) log l/log log l)-approximation algorithm for socially fair clustering with the l(p)-objective. In this problem, we are given a set of points in a metric space. Each point belongs to one (or seve...
详细信息
We present an (e(O(p)) log l/log log l)-approximation algorithm for socially fair clustering with the l(p)-objective. In this problem, we are given a set of points in a metric space. Each point belongs to one (or several) of l groups. The goal is to find a k-medians, k-means, or, more generally, l-clustering that is simultaneously good for all of the groups. More precisely, we need to find a set of k centers C so as to minimize the maximum over all groups j of Sigma (u in group j) (d(u;C)p). The socially fair clustering problem was independently proposed by Abbasi, Bhaskara, and Venkatasubramanian (2021) and Ghadiri, Samadi, and Vempala (2021). Our algorithm improves and generalizes their O (l)-approximation algorithms for the problem. The natural LP relaxation for the problem has an integrality gap of Omega(l). In order to obtain our result, we introduce a strengthened LP relaxation and show that it has an integrality gap of Theta( log l/log log l) for a fixed p. Additionally, we present a bicriteria approximation algorithm, which generalizes the bicriteria approximation of Abbasi et al. (2021).
暂无评论