19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Consensus Strategies for Signed Profiles on Graphs
Presented by Dr. Manoj CHANGAT
Type: Oral presentation
Track: Metric Graph Theory
Content
The majority strategy for a set of clients on a connected graph can
be described as follows: if we are at vertex $v$, then we move to
neighbor $w$ of $v$ if a majority of the clients is closer to $w$
than to $v$. Following the majority strategy by Mulder [Discrete
Applied Math. 80 (1997), 97–105], plurality strategy for clients
were proposed in [ K..Balakrishnan, M.Changat and H.M.Mulder,
Plurality strategy in graphs, Austra. J. Combin. 46 (2010),
191--202]. This strategy is used as a method for finding the median
in the sense of a consensus location for a desirable facility which
minimize the sum of the distances to the location of the clients and
hence this strategy is known as a consensus strategy. By
associating signs +1 or -1 for clients both desirable and
undesirable facilities can be simultaneously considered. In this
paper, we extend the plurality strategy applied on profiles to
signed profiles and use these strategies for locating both desirable
and undesirable facilities (antimedians). We prove that for signed
profiles, the plurality strategy will produce medians and the
opposite strategy known as scarcity strategy will produce
antimedians for every signed profile if and only if the graphs have
both connected medians and antimedians. We prove a similar result
for the Hill Climbing( Descent) strategy and for the Steepest
Ascent Hill Climbing ( Steepest Descent) strategy. Nice examples of
graphs which have both connected medians and antimedians are also
presented.
Place
Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled
Co-authors
- Dr. Kannan BALAKRISHNAN Cochin University of Science and Technology
- Dr. Martyn MULDER Erasmus University
- Mrs. Ajitha SUBHAMATHI University of Kerala