Critical edges for the assignment problem: Complexity and exact resolution

This paper investigates two problems related to the determination of critical edges for the minimum cost assignment problem. Given a complete bipartite balanced graph with n$n$ vertices on each part and with costs on its edges, k$k$Most Vital Edges Assignment consists of determining a set of k$k$ edges whose removal results in the largest increase in the cost of a minimum cost assignment. A dual problem, Min Edge Blocker Assignment, consists of removing a subset of edges of minimum cardinality such that the cost of a minimum cost assignment in the remaining graph is larger than or equal to a specified threshold. We show that k$k$Most Vital Edges Assignment is NP$NP$-hard to approximate within a factor c<2$c<2$ and Min Edge Blocker Assignment is NP$NP$-hard to approximate within a factor 1.36$1.36$. We also provide an exact algorithm for k$k$Most Vital Edges Assignment that runs in O(n^k+2)$O\left(n^{k+2}\right)$. This algorithm can also be used to solve exactly Min Edge Blocker Assignment.     

银吸收边附近X射线衰减系数测量

在北京同步辐射装置的4B7A中能X光束线上,光源能区为2.1~6.0keV,能量分辨大于5000,高次谐波小于0.1%,光源强度大于109光子/s。通过全能区多能点的透过率精确测量Ag样品质量厚度,然后采用Ag薄膜对单能X光子的透过率进行测量,给出了Ag薄膜在吸收边(3.4~3.9keV)的衰减系数。建立了Ag样品吸收边附近衰减系数同步辐射测量方法。通过不确定度分析给出衰减系数测量不确定度小于1%,填补了在该区间衰减系数的空白。     

Well‐Balanced Designs for Data Placement

The problem we consider in this article is motivated by data placement, in particular data replication in distributed storage and retrieval systems. We are given a set V of v servers along with b files (data, documents). Each file is replicated on exactly k servers. A placement consists in finding a family of b subsets of V (representing the files) called blocks, each of size k. Each server has some probability to fail and we want to find a placement that minimizes the variance of the number of available files. It was conjectured that there always exists an optimal placement (with variance better than any other placement for any value of the probability of failure). We show that the conjecture is true, if there exists a well‐balanced design—that is, a family of blocks—each of size k, such that each j‐element subset of V, , belongs to the same or almost the same number of blocks (difference at most one). The existence of well‐balanced designs is a difficult problem as it contains, as a subproblem, the existence of Steiner systems. We completely solve the case and give bounds and constructions for and some values of v and b.     

Multicriteria movement synchronization scheduling problems and algorithms

This article deals with multicriteria optimization models and algorithms of movement scheduling for many objects to synchronize their movement (2CMSS problem). The model consists of two parts: (1) node–disjoint path planning visiting specified nodes for K objects with a given vector of intermediate nodes for each one (NDSP problem); (2) movement synchronization in some intermediate nodes (MS problem). For synchronous movement, two categories of criteria are defined: time of movement and ‘distance’ of K-moved objects from the movement pattern. We defined the problem as a discrete-continuous, non-linear, two-criteria mathematical programming problem. We proposed to use a two-stage algorithm to solve the 2CMSS problem (as lexicographic solution): At first we have to find the vector of node–disjoint shortest paths for K objects visiting intermediate nodes to set optimal paths under the assumption that we use maximal possible velocities on each arc belonging to a path for each object (solution of the NDSP problem), and next we try to decrease the values of velocities to optimize the second criterion (synchronization, solution of the MS problem). Experimental analyses of effectiveness and complexity of the algorithms are presented.     

A counterexample related to topological sums

In this paper we construct compact metric spaces , which are topologically distinct but whose topological sums and are homeomorphic.

     

Spanning even subgraphs of 3‐edge‐connected graphs

By Petersen's theorem, a bridgeless cubic graph has a 2‐factor. H. Fleischner extended this result to bridgeless graphs of minimum degree at least three by showing that every such graph has a spanning even subgraph. Our main result is that, under the stronger hypothesis of 3‐edge‐connectivity, we can find a spanning even subgraph in which every component has at least five vertices. We show that this is in some sense best possible by constructing an infinite family of 3‐edge‐connected graphs in which every spanning even subgraph has a 5‐cycle as a component. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 37–47, 2009     

The electrochemistry of electrode edges and its relevance to partially blocked voltammetric electrodes

Analytical mathematics and digital simulation are used to predict the response, to a potential jump, of the junction between insulating and conducting regions of an electrode. The simulation is carried out differentially and employs other novel features. Concentrations in the vicinity of edges of positive and negative curvatures, as well as straight edges, are analyzed by the model and thereby the faradaic current densities and currents are predicted. It is shown that, in addition to the well-understood cottrellian current arising from the surface of the conducting electrode, currents are generated that are proportional to the length of the edge and to its curvature. These results are then applied to inlaid disks and to partially blocked electrodes. The possibility is explored of using the response to a potential step to gain information on the geometry of a partially blocked electrode.     

Supereulerian regular matroids without small cocircuits

A cycle of a matroid is a disjoint union of circuits. A matroid is supereulerian if it contains a spanning cycle. To answer an open problem of Bauer in 1985, Catlin proved in [J. Graph Theory 12 (1988) 29–44] that for sufficiently large $n$, every 2-edge-connected simple graph $G$ with $\text{◂=▸}n=\mid V\left(G\right)\mid$ and minimum degree $\text{◂≥▸}\delta \left(G\right)\ge \frac{n}{5}$ is supereulerian. In [Eur. J. Combinatorics, 33 (2012), 1765–1776], it is shown that for any connected simple regular matroid $M$, if every cocircuit $D$ of $M$ satisfies $\text{◂≥▸}\mid D\mid \ge \max \left\{\frac{\text{◂−▸}r\left(M\right)-5}{5},6\right\}$, then $M$ is supereulerian. We prove the following. (i) Let $M$ be a connected simple regular matroid. If every cocircuit $D$ of $M$ satisfies $\text{◂≥▸}\mid D\mid \ge \max \left\{\frac{\text{◂+▸}r\left(M\right)+1}{10},9\right\}$, then $M$ is supereulerian. (ii) For any real number $c$ with , there exists an integer $f\left(c\right)$ such that if every cocircuit $D$ of a connected simple cographic matroid $M$ satisfies $\mid D\mid \ge \text{◂lim▸}\max \text{◂{}▸}\{c\text{◂()▸}\left(r\left(M\right)+1\right),f\left(c\right)\}$, then $M$ is supereulerian.     

Thermoelectricity in a Quasiperiodic Lattice Beyond Nearest-Neighbor Electron Hopping

A new route to obtain a large figure of merit (>1) is reported, for the first time, by considering a one-dimensional quasiperiodic lattice where an electron can hop beyond usual nearest-neighbor sites. A finite positional correlation is imposed among the constituent lattice sites, following the well-known Aubry-André-Harper (AAH) form. In the presence of second-neighbor hopping, the AAH lattice exhibits energy dependent mobility edge which plays the central role for efficient energy conversion. Employing a tight-binding framework, all the thermoelectric quantities are computed based on the standard nonequilibrium Green's function formalism. The analysis can be utilized to investigate thermoelectric phenomena in similar kinds of other aperiodic systems possessing higher order electron hopping.