Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHedge Connectivity without Hedge Overlaps
129
0
0.0
(
0
)
Added by
Rupei Xu
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Connectivity is a central notion of graph theory and plays an important role in graph algorithm design and applications. With emerging new applications in networks, a new type of graph connectivity problem has been getting more attention--hedge connectivity. In this paper, we consider the model of hedge graphs without hedge overlaps, where edges are partitioned into subsets called hedges that fail together. The hedge connectivity of a graph is the minimum number of hedges whose removal disconnects the graph. This model is more general than the hypergraph, which brings new computational challenges. It has been a long open problem whether this problem is solvable in polynomial time. In this paper, we study the combinatorial properties of hedge graph connectivity without hedge overlaps, based on its extremal conditions as well as hedge contraction operations, which provide new insights into its algorithmic progress.
rate research
Read More
Minimum Label Cut (or Hedge Connectivity) problem is defined as follows: given an undirected graph $G=(V, E)$ with $n$ vertices and $m$ edges, in which, each edge is labeled (with one or multiple labels) from a label set $L={ell_1,ell_2, ..., ell_{|L|}}$, the edges may be weighted with weight set $W ={w_1, w_2, ..., w_m}$, the label cut problem(hedge connectivity) problem asks for the minimum number of edge sets(each edge set (or hedge) is the edges with the same label) whose removal disconnects the source-sink pair of vertices or the whole graph with minimum total weights(minimum cardinality for unweighted version). This problem is more general than edge connectivity and hypergraph edge connectivity problem and has a lot of applications in MPLS, IP networks, synchronous optical networks, image segmentation, and other areas. However, due to limited communications between different communities, this problem was studied in different names, with some important existing literature citations missing, or sometimes the results are misleading with some errors. In this paper, we make a further investigation of this problem, give uniform definitions, fix existing errors, provide new insights and show some new results. Specifically, we show the relationship between non-overlapping version(each edge only has one label) and overlapping version(each edge has multiple labels), by fixing the error in the existing literature; hardness and approximation performance between weighted version and unweighted version and some useful properties for further research.
Most methods for decision-theoretic online learning are based on the Hedge algorithm, which takes a parameter called the learning rate. In most previous analyses the learning rate was carefully tuned to obtain optimal worst-case performance, leading to suboptimal performance on easy instances, for example when there exists an action that is significantly better than all others. We propose a new way of setting the learning rate, which adapts to the difficulty of the learning problem: in the worst case our procedure still guarantees optimal performance, but on easy instances it achieves much smaller regret. In particular, our adaptive method achieves constant regret in a probabilistic setting, when there exists an action that on average obtains strictly smaller loss than all other actions. We also provide a simulation study comparing our approach to existing methods.
We introduce and discuss a general criterion for the derivative pricing in the general situation of incomplete markets, we refer to it as the No Almost Sure Arbitrage Principle. This approach is based on the theory of optimal strategy in repeated multiplicative games originally introduced by Kelly. As particular cases we obtain the Cox-Ross-Rubinstein and Black-Scholes in the complete markets case and the Schweizer and Bouchaud-Sornette as a quadratic approximation of our prescription. Technical and numerical aspects for the practical option pricing, as large deviation theory approximation and Monte Carlo computation are discussed in detail.
For an integer $ellgeqslant 2$, the $ell$-component connectivity of a graph $G$, denoted by $kappa_{ell}(G)$, is the minimum number of vertices whose removal from $G$ results in a disconnected graph with at least $ell$ components or a graph with fewer than $ell$ vertices. This is a natural generalization of the classical connectivity of graphs defined in term of the minimum vertex-cut and is a good measure of robustness for the graph corresponding to a network. So far, the exact values of $ell$-connectivity are known only for a few classes of networks and small $ell$s. It has been pointed out in~[Component connectivity of the hypercubes, Int. J. Comput. Math. 89 (2012) 137--145] that determining $ell$-connectivity is still unsolved for most interconnection networks, such as alternating group graphs and star graphs. In this paper, by exploring the combinatorial properties and fault-tolerance of the alternating group graphs $AG_n$ and a variation of the star graphs called split-stars $S_n^2$, we study their $ell$-component connectivities. We obtain the following results: (i) $kappa_3(AG_n)=4n-10$ and $kappa_4(AG_n)=6n-16$ for $ngeqslant 4$, and $kappa_5(AG_n)=8n-24$ for $ngeqslant 5$; (ii) $kappa_3(S_n^2)=4n-8$, $kappa_4(S_n^2)=6n-14$, and $kappa_5(S_n^2)=8n-20$ for $ngeqslant 4$.
Let $G$ be an $n$-node graph without two disjoint odd cycles. The algorithm of Artmann, Weismantel and Zenklusen (STOC17) for bimodular integer programs can be used to find a maximum weight stable set in $G$ in strongly polynomial time. Building on structural results characterizing sufficiently connected graphs without two disjoint odd cycles, we construct a size-$O(n^2)$ extended formulation for the stable set polytope of $G$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
