Let f be a drawing in the Euclidean plane of a graph G, which is understood to be a 1dimensional simplicial complex. We assume that every edge of G is drawn by f as a curve of constant algebraic complexity, and the ratio of the length of the longest simple path to the the length of the shortest edge is poly(n). In the drawing f, a path P of G, or its image in the drawing π = f(P), is βstretch if π is a simple (nonselfintersecting) curve, and for every pair of distinct points p ∈ P and q ∈ P , the length of the subcurve of π connecting f(p) with f(q) is at most β∥f(p) − f(q)∥, where ∥.∥ denotes the Euclidean distance. We introduce and study the βstretch Path Problem (βSP for short), in which we are given a pair of vertices s and t of G, and we are to decide whether in the given drawing of G there exists a βstretch path P connecting s and t. We also output P if it exists. The βSP quantifies a notion of “near straightness” for paths in a graph G, motivated by gerrymandering regions in a map, where edges of G represent natural geographical/political boundaries that may be chosen to bound election districts. The notion of a βstretch path naturally extends to cycles, and the extension gives a measure of how gerrymandered a district is. Furthermore, we show that the extension is closely related to several studied measures of local fatness of geometric shapes. We prove that βSP is strongly NPcomplete. We complement this result by giving a quasipolynomial time algorithm, that for a given ε > 0, β ∈ O(poly(log V (G))), and s, t ∈ V (G), outputs a βstretch path between s and t, if a (1 − ε)βstretch path between s and t exists in the drawing.
more »
« less
Locally Fair Partitioning
We model the societal task of redistricting political districts as a partitioning problem: Given a set of n points in the plane, each belonging to one of two parties, and a parameter k, our goal is to compute a partition P of the plane into regions so that each region contains roughly s = n/k points. P should satisfy a notion of "local" fairness, which is related to the notion of core, a wellstudied concept in cooperative game theory. A region is associated with the majority party in that region, and a point is unhappy in P if it belongs to the minority party. A group D of roughly s contiguous points is called a deviating group with respect to P if majority of points in D are unhappy in P. The partition P is locally fair if there is no deviating group with respect to P.This paper focuses on a restricted case when points lie in 1D. The problem is nontrivial even in this case. We consider both adversarial and "beyond worstcase" settings for this problem. For the former, we characterize the input parameters for which a locally fair partition always exists; we also show that a locally fair partition may not exist for certain parameters. We then consider input models where there are "runs" of red and blue points. For such clustered inputs, we show that a locally fair partition may not exist for certain values of s, but an approximate locally fair partition exists if we allow some regions to have smaller sizes. We finally present a polynomialtime algorithm for computing a locally fair partition if one exists.
more »
« less
 Award ID(s):
 2113798
 NSFPAR ID:
 10411106
 Date Published:
 Journal Name:
 Proceedings of the AAAI Conference on Artificial Intelligence
 Volume:
 36
 Issue:
 5
 ISSN:
 21595399
 Page Range / eLocation ID:
 4752 to 4759
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Let P be a set n points in a ddimensional space. Tverberg theorem says that, if n is at least (k − 1)(d + 1), then P can be par titioned into k sets whose convex hulls intersect. Partitions with this property are called Tverberg partitions. A partition has tolerance t if the partition remains a Tverberg partition after removal of any set of t points from P. A tolerant Tverberg partition exists in any dimensions provided that n is sufficiently large. Let N(d,k,t) be the smallest value of n such that tolerant Tverberg partitions exist for any set of n points in R d . Only few exact values of N(d,k,t) are known. In this paper, we study the problem of finding Radon partitions (Tver berg partitions for k = 2) for a given set of points. We develop several algorithms and found new lower bounds for N(d,2,t).more » « less

Coin toss has been extensively studied in the cryptography literature, and the wellaccepted notion of fairness (henceforth called strong fairness) requires that a corrupt coalition cannot cause nonnegligible bias. It is wellunderstood that twoparty coin toss is impossible if one of the parties can prematurely abort; further, this impossibility generalizes to multiple parties with a corrupt majority (even if the adversary is computationally bounded and failstop only). Interestingly, the original proposal of (twoparty) coin toss protocols by Blum in fact considered a weaker notion of fairness: imagine that the (randomized) transcript of the coin toss protocol defines a winner among the two parties. Now Blum's notion requires that a corrupt party cannot bias the outcome in its favor (but selfsacrificing bias is allowed). Blum showed that this weak notion is indeed attainable for two parties assuming the existence of oneway functions. In this paper, we ask a very natural question which, surprisingly, has been overlooked by the cryptography literature: can we achieve Blum's weak fairness notion in multiparty coin toss? What is particularly interesting is whether this relaxation allows us to circumvent the corrupt majority impossibility that pertains to strong fairness. Even more surprisingly, in answering this question, we realize that it is not even understood how to define weak fairness for multiparty coin toss. We propose several natural notions drawing inspirations from game theory, all of which equate to Blum's notion for the special case of two parties. We show, however, that for multiple parties, these notions vary in strength and lead to different feasibility and infeasibility results.more » « less

We study the problem of fair kmedian where each cluster is required to have a fair representation of individuals from different groups. In the fair representation kmedian problem, we are given a set of points X in a metric space. Each point x ∈ X belongs to one of ℓ groups. Further, we are given fair representation parameters αj and β_j for each group j ∈ [ℓ]. We say that a kclustering C_1, ⋅⋅⋅, C_k fairly represents all groups if the number of points from group j in cluster C_i is between α_j C_i and β_j C_i for every j ∈ [ℓ] and i ∈ [k]. The goal is to find a set of k centers and an assignment such that the clustering defined by fairly represents all groups and minimizes the ℓ_1objective ∑_{x ∈ X} d(x, ϕ(x)). We present an O(log k)approximation algorithm that runs in time n^{O(ℓ)}. Note that the known algorithms for the problem either (i) violate the fairness constraints by an additive term or (ii) run in time that is exponential in both k and ℓ. We also consider an important special case of the problem where and for all j ∈ [ℓ]. For this special case, we present an O(log k)approximation algorithm that runs in time.more » « less

null (Ed.)Motivated by applications in gerrymandering detection, we study a reconfiguration problem on connected partitions of a connected graph G. A partition of V(G) is connected if every part induces a connected subgraph. In many applications, it is desirable to obtain parts of roughly the same size, possibly with some slack s. A Balanced Connected kPartition with slack s, denoted (k, s)BCP, is a partition of V(G) into k nonempty subsets, of sizes n1,…,nk with ni−n/k≤s , each of which induces a connected subgraph (when s=0 , the k parts are perfectly balanced, and we call it kBCP for short). A recombination is an operation that takes a (k, s)BCP of a graph G and produces another by merging two adjacent subgraphs and repartitioning them. Given two kBCPs, A and B, of G and a slack s≥0 , we wish to determine whether there exists a sequence of recombinations that transform A into B via (k, s)BCPs. We obtain four results related to this problem: (1) When s is unbounded, the transformation is always possible using at most 6(k−1) recombinations. (2) If G is Hamiltonian, the transformation is possible using O(kn) recombinations for any s≥n/k , and (3) we provide negative instances for s≤n/(3k) . (4) We show that the problem is PSPACEcomplete when k∈O(nε) and s∈O(n1−ε) , for any constant 0<ε≤1 , even for restricted settings such as when G is an edgemaximal planar graph or when k≥3 and G is planar.more » « less