Abstract:

We propose and analyze several graph-defined combinatorial optimization problems inspired by multiple application areas.

First, we consider an influence maximization model that uses the independent cascade approach, but allows two types for packets of information, +1 and -1. These represent the change in a receiver's sentiments on a product or belief on an empirical question (regarded as their "bias"), which can be justified via Bayes' rule. The algorithmic problems we study may be viewed as taking a more fine-grained approach to traditional influence maximization problems, and correspondingly exhibit non-trivial behavior even in the unbudgeted version where packets are unlimited—including tractability that depends on the probability parameters of the independent cascade dynamics. On the other hand, we obtain NP-hardness results for the budgeted version more analogous to previous work. Several natural heuristics are shown to induce substantial reductions of bias in simulations with well-known social network datasets.

Next, given an undirected graph representing similarities between a set of items and an additive measure evaluating them, we treat the position of a special subset of items in an ordinal ranking through a collection of problems in which items may be combined if they are similar. The objective for these problems is to either maximize or minimize the absolute or relative rank of the special subset, with a meta-goal of assessing the robustness of the rank, even in the presence of a well-defined criterion. We classify the computational complexity of all four problems, mostly finding worst-case hardness, then find exact and approximate solutions to special cases and variants of the problems. These structured cases are inspired by numerous real-world examples and may be used to assess commonly cited facts across disparate domains, as we demonstrate for sources of greenhouse gas emissions that contribute to climate change. We then adapt our framework to require subsets of comparable measure, converting the above ranking problems into redistricting problems, with analogues to the former's grid variants. Emphasis is placed on worst-case deviations from proportional representation and an urban-rural model in which gerrymandering ability is curtailed.