BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//UM//UM*Events//EN
CALSCALE:GREGORIAN
BEGIN:VTIMEZONE
TZID:America/Detroit
TZURL:http://tzurl.org/zoneinfo/America/Detroit
X-LIC-LOCATION:America/Detroit
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20070311T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20071104T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260522T140614
DTSTART;TZID=America/Detroit:20260604T140000
DTEND;TZID=America/Detroit:20260604T160000
SUMMARY:Presentation:Combinatorial Optimization Problems Arising from Graph-Based Models
DESCRIPTION:Abstract:\n\nWe propose and analyze several graph-defined combinatorial optimization problems inspired by multiple application areas.  \n\nFirst\, 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.  \n\nNext\, 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.
UID:148410-21904197@events.umich.edu
URL:https://events.umich.edu/event/148410
CLASS:PUBLIC
STATUS:CONFIRMED
CATEGORIES:Dissertation,Graduate,Graduate Students,Mathematics
LOCATION:East Hall - 4088
CONTACT:
END:VEVENT
END:VCALENDAR