哈明距离下的网络逆问题研究综述

逆优化问题研究的是如何改变原问题中的权参数,使得某些给定的解是问题在新的权参数下的最优解,且使总的改造费用尽可能少.作为逆优化问题中相对较新的一个分支,哈明距离下的网络逆问题具有较大的理论研究及实际应用价值.此文首先介绍了逆优化问题和哈明距离下的网络逆问题以及它们的应用,然后详细介绍了哈明距离下的网络逆问题的研究动态及使用的研究方法.最后给出了该领域中的一些值得研究的问题.     

图的最小完整度

主要研究了图的完整度,并给出若干关于完整度的结果. 对于所有的顶点数和边数都给定的连通图类,如何确定该图类中完整度最小的图. 同时研究了对于顶点数和完整度都给定的连通图类,如何确定该图类中边数最多的图的问题. 这些结果为图的最小完整度的优化设计提供了理论和方法.     

三圈图的Harary指数

图G的Harary指数是指图G中所有顶点对间的距离倒数之和. 三圈图是指边数等于顶点数加2的连通图. 研究了三圈图的Harary数, 给出了所有三圈图中具有极大Harary指数的图的结构以及含有三个圈的三圈图中具有次大Harary指数的图的结构.     

若干图类的Wiener指数的极值

一个图的Wiener指数是指这个图中所有点对的距离和.Wiener指数在理论化学中有广泛应用. 本文刻画了给定顶点数及特定参数如色数或团数的图中Wiener指数达最小值的图, 同时也刻画了给定顶点数及团数的图中Wiener指数达最大值的图.     

图的部分控制集问题的修正 Greedy算法

部分控制集问题是对于给定的顶点赋权图G=(V,E;c)和正整数K,寻找图G一个顶点子集T,使得在其控制下的顶点个数不小于K且T中顶点权和达到最小。本文讨论了部分控制集问题的NP-困难性;给出了该问题的一种修正Greedy近似算法,并对其近似度H(K)给出了证明。     

单圈图的最低及最高电阻地位

一个连通图的一个顶点的电阻地位是这个顶点到该图的其它所有顶点的电阻距离之和. 一个连通图的最低(最高)电阻地位是这个图的所有顶点的电阻地位的最小值(最大值). 我们确定了在给定阶数的单圈图中最低(最高)电阻地位的极值和相应的极图,还讨论了单圈图的最低(最高)电阻地位与围长的关系.     

运用重心的性质证题举例

<正>三角形的三条中线的交点叫三角形的重心,由重心的定义可知它有如下性质:(1)连顶点与重心,其延长线必通过对边的中心;(2)中线必过重心;(2)重心到各边中点的距离等于该边中线的1/3,重心到顶点的距离等于该边中线的2/3;即重心到顶点的距离与重心到对边中点距离之比为2∶1;     

一类三圈图的Wiener指数

图G的Wiener指数是指图G中所有顶点对间的距离之和,即W（G）=∑dc（u,u）,{u,u}CG其中de（u,u）表示G中顶点u,u之间的距离.三圈图是指边数与顶点数之差等于2的连通图,任意两个圈至多只有一个公共点的三圈图记为T_n~3.研究了三圈图T_n~3的Wiener指数,给出了其具有最小、次小Wiener指数的图结构.     

电阻-距离谱的若干结果

对连通图$G$的顶点$u$和$v$, $u$与$v$在$G$中的电阻距离$r_G(u,v)$等于相邻顶点之间的电阻为单位电阻的$G$对应的电网中$u$与$v$之间的等效电阻. 图$G$的电阻-距离特征值是$G$的电阻-距离矩阵$R(G)=(r_G(u,v))_{u,v\in V(G)}$的特征值. 我们分别确定了不同于完全图与完全图删去一条边后得到的图及给定割边数目的使得最大电阻-距离特征值取得最小值的唯一的连通图, 还讨论了最小电阻-距离特征值的性质.     

区间图上可带负权的2-中位选址问题

本文研究了区间图上可带负权的2-中位选址问题.根据目标函数的不同,可带负权的$p-$中位选址问题($p\geq 2$)可分为两类：即 MWD 和 WMD 模型;前者是所有顶点与服务该顶点的设施之间的最小权重距离之和,后者是所有顶点与相应设施之间的权重最小距离之和.在本篇论文中,我们讨论了区间图上可带负权2-中位选址问题的两类模型,并分别设计时间复杂度为$O(n^2)$的多项式时间算法.     

The directional p-median problem: Definition,complexity, and algorithms

An instance of a p-median problem gives n demand points. The objective is to locate p supply points in order to minimize the total distance of the demand points to their nearest supply point. p-Median is polynomially solvable in one dimension but NP-hard in two or more dimensions, when either the Euclidean or the rectilinear distance measure is used. In this paper, we treat the p-median problem under a new distance measure, the directional rectilinear distance, which requires the assigned supply point for a given demand point to lie above and to the right of it. In a previous work, we showed that the directional p-median problem is polynomially solvable in one dimension; we give here an improved solution through reformulating the problem as a special case of the constrained shortest path problem. We have previously proven that the problem is NP-complete in two or more dimensions; we present here an efficient heuristic to solve it. Compared to the robust Teitz and Bart heuristic, our heuristic enjoys substantial speedup while sacrificing little in terms of solution quality, making it an ideal choice for real-world applications with thousands of demand points.     

A game-theoretic approach for downgrading the?1-median in the?plane with Manhattan metric

This paper deals with downgrading the 1-median, i.e., changing values of parameters within certain bounds such that the optimal objective value of the location problem with respect to the new values is maximized. We suggest a game-theoretic view at this problem which leads to a characterization of an optimal solution. This approach is demonstrated by means of the Downgrading 1-median problem in the plane with Manhattan metric and implies an O(nlog²n)\mathcal {O}(n\log^{2}n) time algorithm for this problem.     

Reverse 2-median problem on trees

This paper concerns the reverse 2-median problem on trees and the reverse 1-median problem on graphs that contain exactly one cycle. It is shown that both models under investigation can be transformed to an equivalent reverse 2-median problem on a path. For this new problem an algorithm is proposed, where n is the number of vertices of the path. It is also shown that there exists an integral solution if the input data are integral.     

Inverse median location problems with variable coordinates

Given n points in \mathbbR^d{\mathbb{R}^d} with nonnegative weights, the inverse 1-median problem with variable coordinates consists in changing the coordinates of the given points at minimum cost such that a prespecified point in \mathbbR^d{\mathbb{R}^d} becomes the 1-median. The cost is proportional to the increase or decrease of the corresponding point coordinate. If the distances between points are measured by the rectilinear norm, the inverse 1-median problem is NP{\mathcal{NP}}-hard, but it can be solved in pseudo-polynomial time. Moreover, a fully polynomial time approximation scheme exists in this case. If the point weights are assumed to be equal, the corresponding inverse problem can be reduced to d continuous knapsack problems and is therefore solvable in O(nd) time. In case that the squared Euclidean norm is used, we derive another efficient combinatorial algorithm which solves the problem in O(nd) time. It is also shown that the inverse 1-median problem endowed with the Chebyshev norm in the plane is NP{\mathcal{NP}}-hard. Another pseudo-polynomial algorithm is developed for this case, but it is shown that no fully polynomial time approximation scheme does exist.     

The gravity p-median model

In this paper we propose a new model for the p-median problem. In the standard p-median problem it is assumed that each demand point is served by the closest facility. In many situations (for example, when demand points are communities of customers and each customer makes his own selection of the facility) demand is divided among the facilities. Each customer selects a facility which is not necessarily the closest one. In the gravity p-median problem it is assumed that customers divide their patronage among the facilities with the probability that a customer patronizes a facility being proportional to the attractiveness of that facility and to a decreasing utility function of the distance to the facility.     

Inverse 1-median problem on trees under weighted Hamming distance

The inverse 1-median problem consists in modifying the weights of the customers at minimum cost such that a prespecified supplier becomes the 1-median of modified location problem. A linear time algorithm is first proposed for the inverse problem under weighted l _?? norm. Then two polynomial time algorithms with time complexities O(n log n) and O(n) are given for the problem under weighted bottleneck-Hamming distance, where n is the number of vertices. Finally, the problem under weighted sum-Hamming distance is shown to be equivalent to a 0-1 knapsack problem, and hence is ${\mathcal{NP}}$ -hard.     

A method for solving to optimality uncapacitated location problems

In this paper we develop a method for solving to optimality a general 0–1 formulation for uncapacitated location problems. This is a 3-stage method that solves large problems in reasonable computing times.The 3-stage method is composed of a primal-dual algorithm, a subgradient optimization to solve a Lagrangean dual and a branch-and-bound algorithm. It has a hierarchical structure, with a given stage being activated only if the optimal solution could not be identified in the preceding stage.The proposed method was used in the solution of three well-known uncapacitated location problems: the simple plant location problem, thep-median problem and the fixed-chargep-median problem. Computational results are given for problems of up to the size 200 customers ×200 potential facility sites.     

The backup 2-median problem on block graphs

The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O（n log n q- m）-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph.     

A Lagrangian search method for the <Emphasis Type="Italic">P</Emphasis>-median problem

In this paper, we propose a novel algorithm for solving the classical P-median problem. The essential aim is to identify the optimal extended Lagrangian multipliers corresponding to the optimal solution of the underlying problem. For this, we first explore the structure of the data matrix in P-median problem to recast it as another equivalent global optimization problem over the space of the extended Lagrangian multipliers. Then we present a stochastic search algorithm to find the extended Lagrangian multipliers corresponding to the optimal solution of the original P-median problem. Numerical experiments illustrate that the proposed algorithm can effectively find a global optimal or very good suboptimal solution to the underlying P-median problem, especially for the computationally challenging subclass of P-median problems with a large gap between the optimal solution of the original problem and that of its Lagrangian relaxation.