%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Please do not change the following statements. You must start from line 43 "==>start from here" %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\thispagestyle{empty} \documentclass[12pt, reqno]{amsart} \usepackage{amsmath, amsthm, amscd, amsfonts, amssymb, graphicx, color} %\usepackage[bookmarksnumbered, colorlinks, plainpages]{hyperref} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % If you want to insert other packages. Insert them here %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \makeatletter \oddsidemargin.9375in \evensidemargin \oddsidemargin \marginparwidth1.9375in \makeatother \def\affilfont{\normalfont\fontsize{10}{12}\selectfont\centering} \def\affil#1{\par\vskip12pt{\affilfont#1\par}\vskip15pt} \def\Speaker{$^{*}$\protect\footnotetext{$^{*}$ S\lowercase{peaker.}}} \def\authorsaddresses#1{\dedicatory{#1}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{xca}[theorem]{Exercise} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \numberwithin{equation}{section} %\thispagestyle{empty} \begin{document} %\pagenumbering{gobble} \setcounter{page}{1} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% ==>start from here %% Start from here %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Insert title of your article. Note: \title[short title]{full title} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title[The inverse 1-median problem]{The inverse 1-median problem on a plane and on a cycle with negative weights} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Author's name must be inserted here %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \author[M. Galavii]{Mohammadreza Galavii\Speaker} %%%%%%%%%%%%%%%%%%%%%%%% % Addresses %%%%%%%%%%%%%%%%%%%%%%%% \authorsaddresses{ Department of Mathematics, University of Zabol,\\ P. O. Box 98615-538, Zabol , Iran\\ galavi@opt.math.tu-graz.ac.at} %%%%%%%%%%%%%%%%%%%%%%%%%%%% % Subject class; see http://www.ams.org/mathscinet/msc/msc2010.html %%%%%%%%%%%%%%%%%%%%%%%%%%%% \subjclass[2010]{Primary 90C27; Secondary 90B80, 90B85.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % keywords; Note that the number of keywords must be at least 3 items and at most 5 items. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \keywords{Location, inverse location, nonlinear programming, combinatorial optimization.} \maketitle %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Abstract of your extended abstract % Note: the abstract should be 200 words or less with no reference number therein. %The speaker is responsible for the proper formatting his/her talk by using the style %file of the booklet of abstracts. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{abstract} This article considers two problems, the first one is the inverse Fermat-Weber problem, provided the Euclidean 1-median is a vertex and the second one is the inverse $1$-maxian problem on cycles. For any two problems, the aim is to change the vertex weights at minimum total cost with respect to given modification bounds such that a prespecified vertex becomes 1-median. If the prespecified point coincides with one of the given $n$ points in the plane, it is shown that the corresponding inverse problem can be written as convex problem and hence is solvable in polynomial time to any fixed precision. We show that the inverse $1$-maxian problem on a cycles with positive edge-lengths and unit cost can be solved in $O(n^2)$-time. \end{abstract} %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%% % The body of your extended abstract %%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Note that The number of %% pages of the extended abstract should have 3-4 pages. Papers prepared %% in less than 3 pages, more than 4 pages or out of the style of the conference will be %% returned %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} In recent years inverse optimization problems found an increased interest. The \emph{inverse optimization problem} consists in changing parameters of the problem at minimum cost such that a prespecified solution becomes optimal. Recently, inverse $p$-median problem has been investigated by Burkard, Pleschiutsching and Zhang~\cite{BPZ}. They showed that the discrete inverse $p$-median problem with real weights can be solved in polynomial time provided $p$ is fixed and not an input parameter. They presented a greedy-like $O(n\log n)$-time algorithm for the inverse $1$-median problem in the plane provided the distances between the points are measurde in the Manhattan or maximum metric. Also, they showed that the inverse $1$-median problem on a cycle with positive vertex weights can be solved in $O(n^2)$ time. The inverse Fermat-Weber problem was studied by Burkard, Galavii, and Gassner~\cite{BGG}. The authors derived a combinatorial approach which solves the problem in $O(n\log n)$-time for unit cost and under the assumption that the prespecified point that should become a $1$-median does not coincide with a given point in the plane. Galavii~\cite{GAL} showed that the inverse $1$-median problem on a tree with positive weights can be solved in linear time. In this paper we investigate the inverse Fermat-Weber problem on a plane, provided the Euclidean $1$-median is a vertex and also the inverse $1$-median problem on cycles with negative weights. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % References %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bibliographystyle{amsplain} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Please cite your relevant papers but at most total 5 papers/books. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{thebibliography}{5} \bibitem{BGG} R. E. Burkard, M. Galavii and E. Gassner, \textit{The inverse Fermat-Weber problem}, European J. Oper. Res. 206 (2010), no. 1, 11--17. \bibitem{BPZ} R. E. Burkard, C. Pleschiutschnig and J. Z. Zhang, \textit{Inverse median problems}, Discrete Optim. 1 (2004), no. 1, 23--39. \bibitem{CG} R. L. Church and R.S. Garfinkel, \textit{Locating an obnoxious facility on a network}, Transport. Sci. 12 (1978), no. 2, 107--118. \bibitem{GAL} M. Galavii, \textit{The inverse $1$-median problem on a tree and on a path}, Electron. Notes Discrete Math. 36 (2010), 1241--1248. \bibitem{HAK} S. L. Hakimi, \textit{Optimum location of switching center and the absolute centers and medians of a gragh}, Oper. Res. 12 (1964), no. 3, 450--459. \end{thebibliography} \end{document}