下载文档原格式
Generalized Network Design ProblemsbyCorinne Feremans1,2Martine Labb´e1Gilbert Laporte3March20021Institut de Statistique et de Recherche Op´e rationnelle,Service d’Optimisation,CP210/01, Universit´e Libre de Bruxelles,boulevard du Triomphe,B-1050Bruxelles,Belgium,e-mail: mlabbe@smg.ulb.ac.be2Universiteit Maastricht,Faculty of Economics and Business Administration Depart-ment,Quantitative Economics,P.O.Box616,6200MD Maastricht,The Netherlands,e-mail:C.Feremans@KE.unimaas.nl3Canada Research Chair in Distribution Management,´Ecole des Hautes´Etudes Com-merciales,3000,chemin de la Cˆo te-Sainte-Catherine,Montr´e al,Canada H3T2A7,e-mail: gilbert@crt.umontreal.ca1AbstractNetwork design problems consist of identifying an optimal subgraph ofa graph,subject to side constraints.In generalized network design prob-lems,the vertex set is partitioned into clusters and the feasibility conditionsare expressed in terms of the clusters.Several applications of generalizednetwork design problems arise in thefields of telecommunications,trans-portation and biology.The aim of this review article is to formally definegeneralized network design problems,to study their properties and to pro-vide some applications.1IntroductionSeveral classical combinatorial optimization problems can be cast as Network Design Problems(NDP).Broadly speaking,an NDP consists of identifying an optimal subgraph F of an undirected graph G subject to feasibility conditions. Well known NDPs are the Minimum Spanning Tree Problem(MSTP),the Trav-eling Salesman Problem(TSP)and the Shortest Path Problem(SPP).We are interested here in Generalized NDPs,i.e.,in problems where the vertex set of G is partitioned into clusters and the feasibility conditions are expressed in terms of the clusters.For example,one may wish to determine a minimum length tree spanning all the clusters,a Hamiltonian cycle through all the clusters,etc.Generalized NDPs are important combinatorial optimization problems in their own right,not all of which have received the same degree of attention by operational researchers.In order to solve them,it is useful to understand their structure and to exploit the relationships that link them.These problems also underlie several important applications areas,namely in thefields of telecommu-nications,transportation and biology.Our aim is to formally define generalized NDPs,to study their properties and to provide examples of their applications.We willfirst define an unified notational framework for these problems.This will be followed by complexity results and by the study of seven generalized NDPs.2Definitions and notationsAn undirected graph G=(V,E)consists of afinite non-empty vertex set V= {1,...,n}and an edge set E⊆{{i,j}:i,j∈V}.Costs c i and c ij are assigned to vertices and edges respectively.Unless otherwise specified,c i=0for i∈V and c ij≥0for{i,j}∈E.We denote by E(S)={{i,j}∈E:i,j∈S},the subset of edges having their two end vertices in S⊆V.A subgraph F of G is denoted2by F=(V F,E F),V F⊆V,E F⊆E(V F),and its cost c(F)is the sum of its vertex and edge costs.It is convenient to define an NDP as a problem P associated with a subset of terminal vertices T⊆V.A feasible solution to P is a subgraph F=(V F,E F),where T⊆V F,satisfying some side constraints.If T=V,then the NDP is spanning;if T⊂V,it is non-spanning.Let G(T)=(T,E(T))and denote by F P(T)the subset of feasible solutions to the spanning problem P de-fined on the graph G(T).Let S⊆V be such that S∩T=∅,and denote by F P(T,S)the set of feasible solutions of the non-spanning problem P on graph G(S∪T)that spans T,and possibly some vertices from S.In this framework,feasible NDP solutions correspond to a subset of edges satisfying some constraints.Natural spanning NDPs are the following.1.The Minimum Spanning Tree Problem(MSTP)(see e.g.,Magnanti andWolsey[45]).The MSTP is to determine a minimum cost tree on G that includes all the vertices of V.This problem is polynomially solvable.2.The Traveling Salesman Problem(TSP)(see e.g.,Lawler,Lenstra,RinnooyKan and Shmoys[42]).The TSP consists offinding a minimum cost cycle that passes through each vertex exactly once.This problem is N P-hard.3.The Minimum Perfect Matching Problem(MPMP)(see e.g.,Cook,Cun-ningham,Pulleyblank and Schrijver[8]).A matching M⊆E is a subset of edges such that each vertex of M is adjacent to at most one edge of M.A perfect matching is a matching that contains all the vertices of G.The problem consists offinding a perfect matching of minimum cost.This problem is polynomial.4.The Minimum2-Edge-Connected Spanning Network(M2ECN)(see e.g.,Gr¨o tschel,Monma and Stoer[26]and Mahjoub[46].The M2ECN consists offinding a subgraph with minimal total cost for which there exists two edge-disjoint paths between every pair of vertices.5.The Minimum Clique Problem(MCP).The MCP consists of determining aminimum total cost clique spanning all the vertices.This problem is trivial since the whole graph corresponds to an optimal solution.We also consider the following two non-spanning NDPs.1.The Steiner Tree Problem(STP)(see Winter[61]for an overview).TheSTP is to determine a tree on G that spans a set T of terminal vertices at minimum cost.A Steiner tree may contain vertices other than those of T.These vertices are called the Steiner vertices.This problem is N P-hard.32.The Shortest Path Problem(SPP)(see e.g.,Ahuja,Magnanti and Orlin[1]).Given an origin o and a destination d,o,d∈V,the SPP consists of deter-mining a path of minimum cost from o to d.This problem is polynomially solvable.It can be seen as a particular case of the STP where T={o,d}.In generalized NDPs,V is partitioned into clusters V k,k∈K.We now formally define spanning and non-spanning generalized NDPs.Definition1(“Exactly”generalization of spanning problem).Let G= (V,E)be a graph partitioned into clusters V k,k∈K.The“exactly”generaliza-tion of a spanning NDP P on G consists of identifying a subgraph F=(V F,E F) of G yieldingmin{c(F):|V F∩V k|=1,F∈F P( k∈K(V F∩V k))}.In other words,F must contain exactly one vertex per cluster.Two differ-ent generalizations are considered for non-spanning NDPs.Definition2(“Exactly”generalizations of non-spanning problem).Let G=(V,E)be a graph partitioned into clusters V k,k∈K,and let{K T,K S}be a partition of K.The“exactly”T-generalization of a non-spanning problem NDP P on G consists of identifying a subgraph F=(V F,E F)of G yielding min{c(F):|V F∩V k|=1,k∈K T,F∈F P( k∈K T(V F∩V k), k∈K S V k)}.The“exactly”S-generalization of a non-spanning problem NDP P on G consists of identifying a subgraph F=(V F,E F)of G yieldingmin{c(F):|V F∩V k|=1,k∈K S,F∈F P( k∈K T V k, k∈K S(V F∩V k))}.In other words,in the“exactly”T-generalization,F must contain exactly one vertex per cluster V k with k∈K T,and possibly other vertices in k∈K S V k.In the“exactly”S-generalization,F must contain exactly one vertex per cluster V k with k∈K S,and all vertices of k∈K T V k.We can replace|V F∩V k|=1in the above definitions by|V F∩V k|≥1 or|V F∩V k|≤1,leading to the“at least”version or“at most”version of the generalization.The“exactly”,“at least”and“at most”versions of a generalized NDP P are denoted by E-P,L-P and M-P,respectively.In the“at most”and in the“exactly”versions,intra-cluster edges are neglected.In this case,we call the graph G,|K|-partite complete.In the“at least”version the intra-cluster edges are taken into account.43Complexity resultsWe provide in Tables1and2the complexity of the generalized versions in their three respective forms(“exactly”,“at least”and“at most”)for the seven NDPs considered.Some of these combinations lead to trivial problems.Obviously,if a classical NDP is N P-hard,its generalization is also N P-hard.The indication“∅is opt”means that the empty set is feasible and is optimal for the correspond-ing problem.References about complexity results for the classical version of the seven problems considered can be found in Garey and Johnson[20].As can be seen from Table2,two cases of the generalized SPP are N P-hard by reduction from the Hamiltonian Path Problem(see Garey and Johnson[20]). Li,Tsao and Ulular[43]show that the“at most”S-generalization is polynomial if the shrunk graph is series-parallel but provide no complexity result for the gen-eral case.A shrunk graph G S=(V S,E S)derived from a graph G partitioned into clusters is defined as follows:V S contains one vertex for each cluster of G, and there exists an edge in E S whenever an edge between the two corresponding clusters exists in G.An undirected graph is series-parallel if it is not contractible to K4,the complete graph on four vertices.A graph G is contractible to an-other graph H if H can be obtained from G by deleting and contracting edges. Contracting an edge means that its two end vertices are shrunk and the edge is deleted.We now provide a short literature review and applications for each of the seven generalized NDPs considered.Table1:Complexity of classical and generalized spanning NDPs Problem MSTP TSP MPMP M2ECN MCP Classical Polynomial N P-hard Polynomial N P-hard Trivial,polynomial Exactly N P-hard[47]N P-hard Polynomial N P-hard N P-hard(with vertexcost)[35]At least N P-hard[31]N P-hard Polynomial N P-hard Equivalent toexactlyAt most∅is opt∅is opt∅is opt∅is opt∅is opt5Table2:Complexity of classical and generalized non-spanning NDPsProblem STP SPPClassical N P-hard PolynomialExactly T-generalization N P-hard PolynomialExactly S-generalization N P-hard N P-hardAt least T-generalization N P-hard PolynomialAt least S-generalization N P-hard N P-hardAt most T-generalization∅is opt∅is optAt most S-generalization N P-hard Polynomial if shrunk graphis series-parallel[43]4The generalized minimum spanning tree prob-lemThe Generalized Minimum Spanning Tree Problem(E-GMSTP)is the problemoffinding a minimum cost tree including exactly one vertex from each vertexset from the partition(see Figure1a for a feasible E-GMSTP solution).Thisproblem was introduced by Myung,Lee and Tcha[47].Several formulations areavailable for the E-GMSTP(see Feremans,Labb´e and Laporte[17]).The Generalized Minimum Spanning Tree Problem in its“at least”version(L-GMSTP)is the problem offinding a minimum cost tree including at least onevertex from each vertex set from the partition(see Figure1b for a feasible solu-tion of L-GMSTP).This problem was introduced by Ihler,Reich and Widmayer[31]as a particular case of the Generalized Steiner Tree Problem(see Section9)under the name“Class Tree Problem”.Dror,Haouari and Chaouachi[11]showthat if the family of clusters covers V without being pairwise disjoint,then theL-GMSTP defined on this family can be transformed into the original L-GMSTPon a graph G′obtained by substituting each vertex v∈ ℓ∈L Vℓ,L⊆K by|L| copies vℓ∈Vℓ,ℓ∈L,and adding edges of weight zero between each pair of thesenew vertices(clique of weight zero between vℓforℓ∈L).This can be done aslong as there is nofixed cost on the vertices,and this transformation does nothold for the“exactly”version of the problem.Applications modeled by the E-GMSTP are encountered in telecommuni-cations,where metropolitan and regional networks must be interconnected by atree containing a gateway from each network.For this internetworking,a vertexhas to be chosen in each local network as a hub and the hub vertices must be con-nected via transmission links such as opticalfiber(see Myung,Lee and Tcha[47]).6Figure 1a: E−GMSTP Figure 1b: L−GMSTPFigure1:Feasible GMSTP solutionsThe L-GMSTP has been used to model and solve an important irrigation network design problem arising in desert environments,where a set of|K|poly-gon shaped parcels share a common source of water.Each parcel is represented by a cluster made up of the polygon vertices.Another cluster corresponds to the water source vertex.The problem consists of designing a minimal length irriga-tion network connecting at least one vertex from each parcel to the water source. This irrigation problem can be modeled as an L-GMSTP as follows.Edges corre-spond to the boundary lines of the parcel.The aim is to construct a minimal cost tree such that each parcel has at least one irrigation source(see Dror,Haouari and Chaouachi[11]).Myung,Lee and Tcha[47]show that the E-GMSTP is strongly N P-hard, using a reduction from the Node Cover Problem(see Garey and Johnson[20]). These authors also provide four integer linear programming formulations.A branch-and-bound method is developed and tested on instances involving up to 100vertices.For instances containing between120and200vertices,the method is stopped before thefirst branching.The lower bounding procedure is a heuris-tic method which approximates the linear relaxation associated with the dual of a multicommodityflow formulation for the E-GMSTP.A heuristic algorithm finds a primal feasible solution for the E-GMSTP using the lower bound.The branching strategy performed in this method is described in Noon and Bean[48].A cluster isfirst selected and branching is performed on each vertex of this cluster.In Faigle,Kern,Pop and Still[14],another mixed integer formulation for the E-GMSTP is given.The linear relaxation of this formulation is computed for a set of12instances containing up to120vertices.This seems to yield an7optimal E-GMSTP solution for all but one instance.The authors also use the subpacking formulation from Myung,Lee and Tcha[47]in which the integrality constraints are kept and the subtour constraints are added dynamically.Three instances containing up to75vertices are tested.A branch-and-cut algorithm for the same problem is described in Feremans[15].Several families of valid inequalities for the E-GMSTP are introduced and some of these are proved to be facet defiputational results show that instances involving up to200vertices can be solved to optimality using this method.A comparison with the computational results obtained in Myung,Lee and Tcha[47]shows that the gap between the lower bound and the upper bound obtained before branching is reduced by10%to20%.Pop,Kern and Still[51]provide a polynomial approximation algorithm for the E-GMSTP.Its worst-case ratio is bounded by2ρif the cluster size is bounded byρ.This algorithm is derived from the method described in Magnanti and Wolsey[45]for the Vertex Weighted Steiner Tree Problem(see Section9).Ihler,Reich,Widmayer[31]show that the decision version of the L-GMSTP is N P-complete even if G is a tree.They also prove that no constant worst-case ratio polynomial-time algorithm for the L-GMSTP exists unless P=N P,even if G is a tree on V with edge lengths1and0.They also develop two polynomial-time heuristics,tested on instances up to250vertices.Finally,Dror,Haouari and Chaouachi[11]provide three integer linear programming formulations for the L-GMSTP,two of which are not valid(see Feremans,Labb´e and Laporte[16]). The authors also describefive heuristics including a genetic algorithm.These heuristics are tested on20instances up to500vertices.The genetic algorithm performs better than the other four heuristics.An exact method is described in Feremans[15]and compared to the genetic algorithm in Dror,Haouari and Chaouachi[11].These results show that the genetic algorithm is time consuming compared to the exact approach of Feremans[15].Moreover the gap between the upper bound obtained by the genetic algorithm and the optimum value increases as the size of the problem becomes larger.5The generalized traveling salesman problem The Generalized Traveling Salesman Problem,denoted by E-GTSP,consists of finding a least cost cycle passing through each cluster exactly once.The sym-metric E-GTSP was introduced by Henry-Labordere[28],Saskena[56]and Sri-vastava,Kumar,Garg and Sen[60]who proposed dynamic programming formu-lations.Thefirst integer linear programming formulation is due to Laporte and Nobert[40]and was later enhanced by Fischetti,Salazar and Toth[18]who in-8troduced a number of facet defining valid inequalities for both the E-GTSP and the L-GTSP.In Fischetti,Salazar and Toth[19],a branch-and-cut algorithm is developed,based on polyhedral results developed in Fischetti,Salazar and Toth [18].This method is tested on instances whose edge costs satisfy the triangular inequality(for which E-GTSP and L-GTSP are equivalent).Moreover heuristics producing feasible E-GTSP solutions are provided.Noon[50]has proposed several heuristics for the GTSP.The most sophis-ticated heuristic published to date is due to Renaud and Boctor[53].It is a generalization of the heuristic proposed in Renaud,Boctor and Laporte[54]for the classical TSP.Snyder and Daskin[59]have developed a genetic algorithm which is compared to the branch-and-cut algorithm of Fischetti,Salazar and Toth[19]and to the heuristics of Noon[50]and of Renaud and Boctor[53].This genetic algorithm is slightly slower than other heuristics,but competitive with the CPU times obtained in Fischetti,Salazar and Toth[19]on small instances, and noticeably faster on the larger instances(containing up to442vertices).Approximation algorithms for the GTSP with cost function satisfying the triangle inequality are described in Slav´ık[58]and in Garg,Konjevod and Ravi [21].A non-polynomial-time approximation heuristic derived from Christofides heuristic for the TSP[7]is presented in Dror and Haouari[10];it has a worst-case ratio of2.Transformations of the GTSP instances into TSP instances are studied in Dimitrijevi´c and Saric[9],Laporte and Semet[41],Lien,Ma and Wah[44],Noon and Bean[49].According to Laporte and Semet[41],they do not provide any significant advantage over a direct approach since the TSP resulting from the transformation is highly degenerate.The GTSP arises in several application contexts,several of which are de-scribed in Laporte,Asef-Vaziri and Sriskandarajah[38].These are encountered in post box location(Labb´e and Laporte[36])and in the design of postal deliv-ery routes(Laporte,Chapleau,Landry,and Mercure[39]).In thefirst problem the aim is to select a post box location in each zone of a territory in order to achieve a compromise between user convenience and mail collection costs.In the second application,collection routes must be designed through several post boxes at known locations.Asef-Vaziri,Laporte,and Sriskandarajah[3]study the problem of optimally designing a loop-shaped system for material transportation in a factory.The factory is partitioned into|K|rectilinear zones and the loop must be adjacent to at least one side of each zone,which can be formulated as a GTSP.The GTSP can also be used to model a simple case of the stochastic vehicle routing problem with recourse(Dror,Laporte and Louveaux[12])and some families of arc routing problems(Laporte[37]).In the latter application,a9symmetric arc routing problem is transformed into an equivalent vertex routing problem by replacing edges by vertices.Since the distance from edge e1to edge e2depends on the traversal direction,each edge is represented by two vertices, only one of which is used in the solution.This gives rise to a GTSP.6The generalized minimum perfect matching problemThe E-GMPMP and L-GMPMP are polynomial.Indeed,the E-GMPMP remains a classical MPMP on the shrunk graph,where c kℓ:=min{c ij:i∈V k,j∈Vℓ}for {k,ℓ}∈E S.Moreover the L-GMPMP can be reduced to the E-GMPMP.7The generalized minimum2-edge-connected network problemThe Generalized Minimum Cost2-Edge-Connected Network Problem(E-G2ECN) consists offinding a minimum cost2-edge-connected subgraph that contains ex-actly one vertex from each cluster(Figure2).Figure2:A feasible E-G2ECN solutionThis problem arises in the context of telecommunications when copper wire is replaced with high capacity opticfiber.Because of its high capacity,this new technology allows for tree-like networks.However,this new network becomes failure-sensitive:if one edge breaks,all the network is disconnected.To avoid this situation,the network has to be reliable and must fulfill survivability condi-tions.Since two failures are not likely to occur simultaneously,it seems reasonable to ask for a2-connected network.10This problem is a generalization of the GMSTP.Local networks have to be interconnected by a global network;in every local network,possible locations for a gate(location where the global network and local networks can be intercon-nected)of the global network are given.This global network has to be connected, survivable and of minimum cost.The E-G2ECNP and the L-G2ECNP are studied in Huygens[29].Even when the edge costs satisfy the triangle inequality,the E-G2ECNP and the L-G2ECNP are not equivalent.These problems are N P-hard.There cannot exist a polynomial-time heuristic with bounded worst-case ratio for E-G2ECNP.In Huy-gens[29],new families of facet-defining inequalities for the polytope associated with L-G2ECNP are provided and heuristic methods are described.8The generalized minimum clique problemIn the Generalized Minimum Clique Problem(GMCP)non-negative costs are associated with vertices and edges and the graph is|K|-partite complete.The GMCP consists offinding a subset of vertices containing exactly one vertex from each cluster such that the cost of the induced subgraph(the cost of the selected vertices plus the cost of the edges in the induced subgraph)is minimized(see Figure3).Figure3:A feasible GMSCP solutionThe GMCP appears in the formulation of particular Frequency Assignment Problems(FAP)(see Koster[34]).Assume that“...we have to assign a frequency to each transceiver in a mobile telephone network,a vertex corresponds to a transceiver.The domain of a vertex is the set of frequencies that can be assigned to that transceiver.An edge indicates that communication from one transceiver may interfere with communication from the other transceiver.The penalty of an11edge reflects the priority with which the interference should be avoided,whereas the penalty of a vertex can be seen as the level of preference for the frequen-cies.”(Koster,Van Hoesel and Kolen[35]).The GMCP can also be used to model the conformations occurring in pro-teins(see Althaus,Kohlbacher,Lenhof and M¨u ller[2]).These conformations can be adequately described by a rather small set of so-called rotamers for each amino-acid.The problem of the prediction of protein complex from the structures of its single components can then be reduced to the search of the set of rotamers, one for each side chain of the protein,with minimum energy.This problem is called the Global Minimum Energy Conformation(GMEC).The GMEC can be formulated as follows.Each residue side chain of the protein can take a number of possible rotameric states.To each side chain is associated a cluster.The vertices of this cluster represent the possible rotameric states for this chain.The weight on the vertices is the energy associated with the chain in this rotameric state. The weight on the edges is the energy coming from the combination of rotameric states for different side chains.The GMCP is N P-hard(Koster,Van Hoesel and Kolen[35]).Results of polyhedral study for the GCP were embedded in a cutting plane approach by these authors to solve difficult instances of frequency assignment problems. The structure of the graph in the frequency assignment application is exploited using tree decomposition approach.This method gives good lower bounds for difficult instances.Local search algorithms to solve FAP are also investigated. Two techniques are presented in Althaus,Kohlbacher,Lenhof and M¨u ller[2]to solve the GMEC:a“multi-greedy”heuristic and a branch-and-cut algorithm. Both methods are able to predict the correct complex structure on the instances tested.9The generalized Steiner tree problemThe standard generalization of the STP is the T-Generalized Steiner Tree Prob-lem in its“at least”version(L-GSTP).Let T⊆V be partitioned into clusters. The L-GSTP consists offinding a minimum cost tree of G containing at least one vertex from each cluster.This problem is also known as the Group Steiner Tree Problem or the Class Steiner Tree Problem.Figure4depicts a feasible L-GSTP solution.The L-GSTP is a generalization of the L-GMSTP since the L-GSTP defined on a family of clusters describing a partition of V is a L-GMSTP.This problem was introduced by Reich and Widmayer[52].The L-GSTP arises in wire-routing with multi-port terminals in physical Very Large Scale Integration(VLSI)design.The traditional model assuming sin-12Figure4:A feasible L-GSTP solutiongle ports for each of the terminals to be connected in a net of minimum length is a case of the classical STP.When the terminal is a collection of different pos-sible ports,so that the net can be connected to any one of them,we have an L-GSTP:each terminal is a collection of ports and we seek a minimum length net containing at least one port from each terminal group.The multiple port locations for a single terminal may also model different choices of placing a single port by rotating or mirroring the module containing the port in the placement (see Garg,Konjevod and Ravi[21]).More detailed applications of the L-GSTP in VLSI design can be found in Reich and Widmayer[52].The L-GSTP is N P-hard because it is a generalization of an N P-hard problem.When there are no Steiner vertices,the L-GSTP remains N P-hard even if G is a tree(see Section4).This is a major difference from the classical STP(if we assume that either there is no Steiner vertices or that G is a tree,the complexity of STP becomes polynomial).Ihler,Reich and Widmayer[31]show that the graph G can be transformed(in linear time)into a graph G′(without clusters)such that an optimal Steiner tree on G′can be transformed back into an optimal generalized Steiner tree in G.Therefore,any algorithm for the STP yields an algorithm for the L-GSTP.Even if there exist several contributions on polyhedral aspects(see among others Goemans[24],Goemans and Myung[23],Chopra and Rao[5],[6])and exact methods(see for instance Koch and Martin[33])for the classical problem, only a few are known,as far as we are aware,for the L-GSTP.Polyhedral aspects are studied in Salazar[55]and a lower bounding procedure is described in Gillard and Yang[22].13A number of heuristics for the L-GSTP have been proposed.Early heuris-tics for the L-GSTP are developed in Ihler[30]with an approximation ratio of |K|−1.Two polynomial-time heuristics are tested on instances up to250vertices in Ihler,Reich and Widmayer[31],while a randomized algorithm with polylog-arithmic approximation guarantee is provided in Garg,Konjevod,Ravi[21].A series of polynomial-time heuristics are described in Helvig,Robins,Zelikovsky [27]with worst-case ratio of O(|K|ǫ)forǫ>0.These are proved to empirically outperform one of the heuristic developed in Ihler,Reich and Widmayer[31].In the Vertex Weighted Steiner Tree Problem(VSTP)introduced by Segev [57],weights are associated with the vertices in V.These weights can be negative, in which case they represent profit gained by selecting the vertex.The problem consists offinding a minimum cost Steiner tree(the sum of the weights of the selected vertices plus the sum of the weights of the selected edges).This problem is a special case of the Directed Steiner Tree Problem(DSP)(see Segev[57]). Given a directed graph G=(V,A)with arc weights,afixed vertex and a subset T⊆V,the DSP requires the identification of a minimum weighted directed tree rooted at thefixed vertex and spanning T.The VSTP has been extensively studied(see Duin and Volgenant[13],Gorres[25],Goemans and Myung[23], Klein and Ravi[32]).As far as we know,no Generalized Vertex Weighted Steiner Tree Problem has been addressed.An even more general problem would be the Vertex Weighted Directed Steiner Tree Problem.10The generalized shortest path problemLi,Tsao and Ulular[43]describe an S-generalization of the SPP in its“at most”version(M-GSPP).Let o and d be two vertices of G and assume that V\{o,d}is partitioned into clusters.The M-GSPP consists of determining a shortest path from o to d that contains at most one vertex from each cluster.Note that the T-generalization is of no interest since it reduces to computing the shortest paths between all the pairs of vertices belonging to the two different clusters.In the problem considered by Li,Tsao and Ulular[43],each vertex is as-signed a non-negative weight.The problem consists offinding a minimum cost path from o to d such that the total vertex weight on the path in each traversed cluster does not exceed a non-negative integerℓ(see Figure5).This problem with ℓ=1and vertex weights equal to one for each vertex coincides with the M-GSPP.The problem arises in optimizing the layout of private networks embedded in a larger telecommunication network.A vertex in V\{o,d}represents a digital cross connect center(DCS)that treats the information and insures the transmis-sion.A cluster corresponds to a collection of DCS located at the same location14。
embeddings 的结果通俗解释：
Embeddings 的结果通俗解释如下：
Embedding 是一种将数据从高维空间映射到低维空间的方法，其结果可以看作是一种降维表示。
对于单词或文本数据，Embedding 可以将每个单词或文本表示为一个向量，这个向量包含了该单词或文本的语义信息和上下文信息。
通过训练，Embedding 可以学习到单词或文本之间的相似性和关联性，从而生成具有语义相似性的向量。
这些向量可以用于多种任务，如聚类、分类、文本相似性比较等。
在文本分类任务中，Embedding 可以将文本表示为向量，然后使用这些向量进行分类。
在聚类任务中，Embedding 可以将相似的文本聚类在一起。
在文本相似性比较任务中，Embedding 可以比较两个文本的相似性程度。
dtnl练习题DTNL（Deep Textual Natural Language Processing）是一种深度文本自然语言处理技术，它结合了深度学习和自然语言处理的方法，旨在提高对文本语义的理解和处理能力。
在本文中，我们将通过一系列练习题来巩固我们对DTNL的学习和应用。
练习一：文本分类请根据以下文本内容，判断最适合的分类标签：1. "我是一名程序员，专注于深度学习和自然语言处理技术的研究。
"2. "最近我在学习机器学习领域的知识，特别是神经网络和卷积神经网络的应用。
"3. "我是一名医生，专门从事神经科学的研究工作，致力于寻找治疗神经系统疾病的新方法。
"最适合的分类标签是：科技与计算机。
练习二：情感分析请对以下句子进行情感分析，判断其情感倾向（积极、消极、中性）：1. "这部电影太棒了，我非常喜欢。
"2. "这本书太糟糕了，我完全不喜欢。
"3. "今天的天气真是太糟糕了，下雨了整整一天。
"情感倾向分别是：积极、消极、消极。
练习三：命名实体识别请从以下句子中识别出人名、地名和组织名等命名实体：1. "华为是一家全球知名的科技公司。
"2. "张伟是中国最常见的名字之一。
"3. "上海是中国最繁华的城市之一，拥有许多世界知名企业的总部。
"命名实体识别结果：1. 人名：无，地名：无，组织名：华为。
2. 人名：张伟，地名：中国，组织名：无。
3. 人名：无，地名：上海、中国，组织名：无。
练习四：关键词提取请从以下文本中提取出关键词："深度学习是一种机器学习的方法，主要应用于自然语言处理、图像识别等领域。
深度学习的原理基于神经网络，通过不断学习和调整参数来提高模型的准确性和性能。
"关键词提取结果：深度学习、机器学习、方法、自然语言处理、图像识别、神经网络、学习、调整参数、模型、准确性、性能。
ChatGPT如何避免陷入无限循环和回避问题ChatGPT是OpenAI开发的一种人工智能语言模型，它可以根据输入的提示和上下文生成相应的文本回复。
然而，由于其开放性和自由度高，有时会面临一些挑战，比如陷入无限循环和回避问题。
本文将探讨ChatGPT如何避免这些问题，并提供一些解决方案。
首先，ChatGPT陷入无限循环是指在与用户的对话中，模型不断重复相同或类似的回答，无法进行有意义的对话。
这通常是因为模型倾向于选择最高概率的回答，而在某些情况下，最常见的回答可能是重复的。
为了解决这个问题，一种方法是引入多样性机制，使得模型能够生成多样的回答。
OpenAI研究人员通过在生成回答时引入随机性，从而提高了回答的多样性。
他们还尝试了一种称为“惩罚机制”的方法，通过让模型对相似性较高的回答进行惩罚，来促使其生成不同的回答。
另一个问题是ChatGPT可能会回避问题，即选择回答与问题不相关或模糊的内容。
这可能是因为在训练过程中，模型接触到了大量与问题无关的数据，导致其在生成回答时选择不相关的内容。
为了解决这个问题，OpenAI采取了一种称为“微调”的方法，即在训练过程中使用人类进行常识修正。
研究人员通过使用基于规则的模型对生成的回答进行筛选和修正，从而提高了回答的质量。
此外，在发布了研究原型后，OpenAI还收集了大量用户反馈，并不断改进模型以提高其问答准确性。
除了技术手段外，ChatGPT的使用方式也可以帮助避免陷入无限循环和回避问题。
用户可以通过明确的问题、限制回答长度或者要求给出多个回答选项来引导模型生成更有意义的回答。
此外，对于重要的或敏感的问题，用户也可以选择人工审核或人工干预的方式来保证回答的准确性。
尽管ChatGPT在避免陷入无限循环和回避问题上已经取得了一定的进展，但仍然存在一些挑战。
比如，生成回答可能涉及到虚假信息、歧视性语言或其他不当内容。
OpenAI意识到这一点，并坚持将合规性和安全性作为开发的重要目标。
Computers have revolutionized the way we live and work,and their uses are incredibly diverse and widespread.Here are some of the most common and impactful applications of computers in our daily lives:munication:Computers have transformed the way we communicate.Email, instant messaging,and social media platforms allow us to stay in touch with friends, family,and colleagues across the globe instantly.cation:In the educational sector,computers are used for research,online learning, and digital classrooms.They provide access to a wealth of information and enable interactive learning experiences.3.Business and Finance:Computers are integral to business operations,from managing inventory to processing transactions.They are also used in financial modeling,stock trading,and accounting.4.Entertainment:Computers have revolutionized the entertainment industry.They are used for gaming,streaming movies and music,and creating digital art and animations.5.Healthcare:In healthcare,computers are used for managing patient records,conducting research,and aiding in diagnostics and treatment plans.6.Data Analysis:Computers are essential for data collection,storage,and analysis.They help in making informed decisions in various fields such as science,marketing,and policymaking.7.Manufacturing:Computers are used to control machinery and automate processes in manufacturing,leading to increased efficiency and reduced human error.8.Transportation:Computers are used in transportation systems for navigation,traffic management,and vehicle control,including autonomous vehicles.9.Science and Research:Computers are used for complex calculations,simulations,and modeling in scientific research,helping to push the boundaries of knowledge in fields such as physics,chemistry,and biology.10.Home Automation:Computers are at the heart of smart homes,controlling lighting, heating,security systems,and appliances.11.Creative Industries:In the creative industries,computers are used for graphic design,music production,film editing,and3D modeling.12.Ecommerce:Computers have enabled the growth of online shopping,making it easier for consumers to purchase goods and services from anywhere.ernment and Public Services:Governments use computers for managing public records,providing services to citizens,and ensuring national security.14.Agriculture:Computers are used in precision farming to monitor crop health, optimize irrigation,and increase yield.15.Space Exploration:In space exploration,computers are used to control spacecraft, analyze data from space missions,and simulate space environments.In conclusion,the versatility of computers is astounding,and their influence on modern society is profound.As technology continues to advance,the applications of computers are likely to expand even further,offering new opportunities and challenges for the future.。
embedding的数学推理在数学领域中，embedding是一种常见的概念。
它指的是将一个数学结构嵌入到另一个更大或更复杂的数学结构中的过程。
通过embedding，我们可以将一个抽象或较简单的数学对象表示为更具体或更复杂的数学对象的一部分。
在本文中，我们将探讨embedding在数学推理中的应用和意义。
首先，我们来了解一下embedding的基本概念。
在数学中，embedding通常是通过将一个结构映射到另一个结构的方式实现的。
比如，我们可以将一个整数嵌入到一个实数集合中，或者将一个图形嵌入到一个三维空间中。
通过这种映射，我们可以保留原始结构的一些特性，并在更大或更复杂的结构中进行推理和分析。
其次，让我们来看一下embedding在数学推理中的应用。
首先，embedding可以帮助我们理解和解决复杂的数学问题。
通过将问题中的抽象对象嵌入到一个更具体的数学结构中，我们可以更好地理解问题的性质和规律，并从中寻找解决方案。
例如，在代数学中，通过将一个抽象的向量空间嵌入到一个更具体的欧几里德空间中，我们可以更容易地推导出向量的性质和操作规则。
此外，embedding还可以帮助我们建立数学对象之间的关联和联系。
通过将一个数学对象嵌入到另一个对象中，我们可以将它们之间的关系转化为更容易理解和处理的问题。
例如，在图论中，通过将一个图嵌入到一个更大的图中，我们可以将图的结构性质转化为更大图的性质，从而更好地研究和解决问题。
最后，embedding在数学推理中的使用要注意一些技巧和限制。
首先，我们要确保嵌入的过程是保持结构特性的，即在嵌入后，原始结构的一些重要性质仍然得以保留。
其次，我们要注意嵌入的精确性，以确保嵌入后的结构能够准确地代表原始结构。
同时，我们还需要注意嵌入的操作是否可逆，即能否从嵌入后的结构中恢复出原始结构。
总而言之，embedding是一种在数学推理中常用的技术，它可以帮助我们理解和解决复杂的数学问题，建立数学对象之间的关联和联系。
When youre busy with your homework,you might be engaging in a variety of activities.Here are some detailed aspects of what that could entail:1.Researching Topics:You might be looking up information on various subjects, whether its through books,online resources,or academic databases.2.Writing Essays:This involves drafting,organizing thoughts,developing arguments, and ensuring that the content is wellstructured and coherent.pleting Assignments:Assignments can range from short answer questions to problemsolving tasks in subjects like math,science,or humanities.4.Reading Textbooks and Articles:To understand the material better,you might be reading through chapters or articles related to the subject youre studying.5.Taking Notes:While studying or reading,you could be taking notes to help remember important points and concepts.6.Revising and Editing:After completing a draft of your work,you might be revising it for clarity,grammar,and style.ing Educational Software or Apps:There are many tools available that can help with homework,from language translation apps to math problem solvers.8.Participating in Group Projects:Sometimes homework involves collaboration with classmates,which could include discussions,shared research,and collective writing. 9.Preparing for Presentations:If your homework includes preparing for a class presentation,you might be working on your speaking notes,visual aids,or practicing your delivery.10.Solving Practical Problems:In subjects like science or engineering,you might be conducting experiments or solving practical problems as part of your homework.11.Engaging in Creative Tasks:For subjects like art or music,homework could involve creating a piece of art or composing a piece of music.12.Reviewing Lectures or Class Notes:To reinforce what was taught in class,you might be reviewing lecture recordings or your class notes.13.Managing Time:Balancing the time spent on different subjects and ensuring that all assignments are completed on time is a crucial part of managing homework.14.Seeking Help:If youre struggling with a particular topic,you might be reaching out to teachers,tutors,or classmates for help.15.SelfAssessment:You could be using quizzes or practice tests to check your understanding of the material.Remember,effective homework management is about more than just getting the work done its also about understanding the material and being able to apply it.。
一、选择题1.在人工智能领域，以下哪项技术是实现自然语言处理（NLP）的基础？A.深度学习（正确答案）B.区块链C.云计算D.物联网2.神经网络中的“激活函数”主要用于什么目的？A.增加网络的计算复杂度B.引入非线性因素，使网络能够学习复杂模式（正确答案）C.控制网络中的神经元数量D.加速网络的训练过程3.在构建机器学习模型时，数据预处理阶段通常不包括以下哪项内容？A.数据清洗B.特征选择C.模型评估（正确答案的相反阶段）D.数据标准化4.以下哪种算法常用于解决分类问题中的多分类问题？A.逻辑回归（主要用于二分类）B.决策树C.支持向量机（SVM，虽可多分类但非首选）D.Softmax回归（正确答案，特别是在神经网络中）5.强化学习中，“策略”一词指的是什么？A.环境的初始状态B.代理（Agent）选择动作的依据或规则（正确答案）C.奖励函数的定义D.代理与环境交互的次数6.在自然语言处理中，词嵌入（Word Embedding）的主要目的是什么？A.将文本数据转换为图像数据B.将词汇映射到高维空间中的向量，以捕捉语义信息（正确答案）C.简化文本数据的存储格式D.提高文本数据的加密安全性7.人工智能中的“知识图谱”主要用于什么？A.存储和表示结构化数据，支持复杂的查询和推理（正确答案）B.预测股票价格C.自动生成文本内容D.加速深度学习模型的训练过程8.在设计人工智能系统时，以下哪项是评估模型泛化能力的重要指标？A.训练集上的准确率B.测试集上的准确率（正确答案）C.模型的复杂度D.模型的训练时间。
学术--读书笔记：《AI3.0》--机器学习存在的问题vs⼈类学习作者：梅拉妮·⽶歇尔简介：机器学习的问题：1. 过拟合；2.缺乏可靠性和透明性，及其易受攻击性；3.缺乏常识；4.环境复杂和不可预测。
总的来说，⼈⼯智能领域最重要的开放问题是：如何系统的获取抽象能⼒、“域泛化”（domain generalization）能⼒，以及迁移学习能⼒。
⼈类拥有的知识、抽象和类⽐，是应赋予⼈⼯智能的核⼼⼈⼯神经⽹络的发展历史感知机：感知机设定正确的权重和阈值呢？罗森布拉特给出了⼀个受⼤脑启发的答案：感知机应该通过⾃⼰的学习获得权重和阈值罗森布拉特受到了⾏为主义⼼理学家伯勒斯·斯⾦纳（Burrhus F. Skinner）的启发，（斯⾦纳通过给⽼⿏和鸽⼦以正向和负向的强化来训练它们执⾏任务），罗森布拉特认为感知机也应该在样本上进⾏类似的训练：在触发正确的⾏为时奖励，⽽在犯错时惩罚。
如今，这种形式的条件计算在⼈⼯智能领域被称为监督学习（supervised learning）符号⼈⼯智能：深度学习的成功研究⼈员发现，编写规则的⼈类专家实际上或多或少依赖于潜意识中的知识（常识）以便明智地⾏动。
这种常识通常难以通过程序化的规则或逻辑推理来获取，⽽这种常识的缺乏严重限制了符号⼈⼯智能⽅法的⼴泛应⽤。
word2vec⽅法“通过与⼀个单词⼀同出现的词来认识它”。
可以应⽤与其他⽅⾯，包括社会。
多伦多⼤学的⼀个团队将这些语句称为“思维向量”（thought vectors），还有⼈尝试过⽤⽹络将段落和整个⽂档编码为向量，然⽽结果都是成败。
⾃然语⾔处理相关的研究在最初的⼏⼗年集中在符号化的、基于规则的⽅法上，就是那种给定语法和其他语⾔规则，并把这些规则应⽤到输⼊语句上的⽅法。
这些⽅法并没有取得很好的效果，看来通过使⽤⼀组明确的规则来捕捉语⾔的微妙是⾏不通的。
⾃动语⾳识别是深度学习在⾃然语⾔处理中的重⼤成就强化学习深度学习在近年来的成功与其说是⼈⼯智能的新突破，不如说要归功于互联⽹时代极易获得的海量数据和并⾏计算机硬件的快速处理能⼒。
a rX iv:mat h /35167v1[mat h.OA ]12Ma y23CONNES’EMBEDDING PROBLEM AND LANCE’S WEP NATHANIAL P.BROWN Abstract.A II 1-factor embeds into the ultraproduct of the hyperfinite II 1-factor if and only if it satisfies the von Neumann algebraic analogue of Lance’s weak expectation property (WEP).This note gives a self contained proof of this fact.1.Introduction On page 105in [2]Connes suggested that every separable II 1-factor ought to be embeddable into the ultraproduct,R ω,of the hyperfinite II 1-factor R .Largely due to work of Kirchberg,Voiculescu and,most recently,Haagerup this seemingly technical question has received more and more attention in recent years.Indeed,Kirchberg proved in [5]that this problem can be reformulated in an unexpected variety of ways (see [7]for a wonderful exposition of Kirchberg’s work),this problem turns out to be a necessary condition for Voiculescu’s ‘Unification Problem’(i.e.if the microstates and non-microstates approaches to free entropy yield the same quantity then every II 1-factor is embeddable)and,finally,Haagerup has shown that this problem is nearly sufficient for resolving the relative invariant subspace problem for II 1-factors (he showed that every operator in an embeddable II 1-factor which satisfies a mild non-degeneracy condition has invariant subspaces –see [4]).In [6]Lance introduced the weak expectation property (WEP)for C ∗-algebras.Blackadar shifted the point of view to von Neumann algebras with the following definition.Definition 1.1.Let M ⊂B (H )be a von Neumann algebra acting on some Hilbert space H and let A ⊂M be a weakly dense C ∗-subalgebra.Then M has a weak expectation relative to A if there exists a unital,completely positive map Φ:B (H )→M such that Φ(a )=a for all a ∈A .This notion was inspired by injectivity;M ⊂B (H )is injective if there exists a unital,completely positive map Φ:B (H )→M such that Φ(x )=x for all x ∈M .It follows from Arveson’s Extension Theorem that a C ∗-algebra A has the WEP if andonly if the enveloping von Neumann algebra A ∗∗has a weak expectation relative to A ⊂A ∗∗.In [1]we observed that the W ∗-version of the WEP is closely related to Connes’embedding problem.Theorem 1.2.Let M be a separable II 1-factor.Then M is embeddable into R ωif and only if M has a weak expectation relative to some weakly dense subalgebra.A simple corollary of this result states that many well known II 1-factors which are “far from being hyperfinite”(in the sense that they exhibit vastly different properties than R –no Cartan subalgebras,prime,property T,etc.)are in fact built out of R in a way which naturally mixes von Neumann algebraic and operator space notions.More precisely,we have the following approximation property.2NATHANIAL P.BROWNCorollary1.3.Let M⊂Rωbe a II1-factor,F⊂M be afinite set andǫ>0be given. Then there exists a subspace X⊂M such that X nearly contains F(withinǫin2-norm) and X∼=R(as operator systems).In other words,free group factors(and L(Γ)for any other residuallyfinite group)are the weak closure of(operator space isomorphic)copies of R.The purpose of this note is to give self contained proofs of these results as some details do not appear in[1].The proof turns out to be fairly elementary but relies on a mixture of classical ideas(invariant means)some new aspects of(finite)representation theory of C∗-algebras and a bit of trickery.Throughout this paper A will denote a separable unital C∗-algebra.Separability is really not necessary,but it is convenient.We will use the abbreviation u.c.p.for unital completely positive maps.Ifτis a state on a C∗-algebra A thenπτ:A→B(L2(A,τ))will denote the GNS representation.Note that if M is a II1-factor in standard form(i.e.acting,via GNS,on the L2-space coming from its unique trace)andπ:A→M⊂B(L2(M))is a∗-homomorphism with weakly dense range then we may,thanks to uniqueness of GNS representations,identifyπwith the GNS representation of A coming fromτ◦π,whereτis the unique trace on M.Finally,recall that if R denotes the hyperfinite II1-factor andω∈β(N)\N is a free ultra-filter then the ultraproduct Rωis defined to be l∞(R)={(x n):x n∈R,sup n x n <∞} modulo the ideal Iω={(x n):lim n→ω x n 2=0},where x 22=τ(x∗x)andτis the unique trace on R.It turns out that Rωis a II1-factor with tracial stateτω((x n))=lim n→ωτ(x n).2.Invariant Means on C∗-algebrasIn[2,Remark5.35]Connes points out that a hypertrace can be regarded as the analogue of an invariant mean on a group.We essentially take this as the definition of an invariant mean on a C∗-algebra.Definition2.1.Let A⊂B(H)be a C∗-algebra.A(tracial)stateτon A is called an invariant mean if there exists a stateψon B(H)which is(1)invariant under the action of the unitary group of A on B(H)(i.e.ψ(uT u∗)=ψ(T)for all T∈B(H)and unitaries u∈A)and(2)extendsτ(i.e.ψ|A=τ).We will denote by T(A)IM the set of all invariant means on A.The main result of this section gives an important characterization of invariant means. There are several other ways to characterize invariant means(cf.[1,Theorem3.1],[7,Theo-rem6.1])but we only present the ones we need.The main step in the proof((1)=⇒(2))is essentially due to Connes in the unique trace case and Kirchberg in general.We will isolate the main technical aspects in a lemma.Below,Tr(·)will denote the canonical(unbounded)trace on B(H)and,if H isfinite dimensional,tr(·)will denote the(unique)tracial state on B(H).Also,T⊂B(H)will be the trace class operators(i.e.the predual of B(H))and · 1,T r(resp. · 2,T r)will denote the L1-norm(resp.L2-norm)on T.Recall that the Powers-Størmer inequality states that if h,k∈T are positive then h−k 22,T r≤ h2−k2 1,T r.In particular,if u∈B(H)is a unitary and h≥0hasfinite rank then uh1/2−h1/2u 2,T r= uh1/2u∗−h1/2 2,T r≤ uhu∗−h 1/2.1,T r Lemma2.2.Let h∈B(H)be a positive,finite rank operator with rational eigenvalues and Tr(h)=1.Then there exists a u.c.p.mapφ:B(H)→M q(C)such that tr(φ(T))=Tr(hT)CONNES’EMBEDDING PROBLEM3 for all T∈B(H)and|tr(φ(uu∗)−φ(u)φ(u∗))|<2 uhu∗−h 1/21for every unitary operator u∈B(H).Proof.This proof is taken directly from the proof of[7,Theorem6.1]which,in turn,is based on work of Haagerup.Let v1,...,v k∈H be the eigenvectors of h and p1q the corresponding eigenvalues.Note that p j=q since Tr(h)=1.Let{w m}be any orthonormal basis of H and consider the following orthonormal subset of H⊗H:{v1⊗w1,...,v1⊗w p1}∪{v2⊗w1,...,v2⊗w p2}∪...∪{v k⊗w1,...,v k⊗w pk}.Let P∈B(H⊗H)be the orthogonal projection onto the span of these vectors.We encourage the reader to write down the matrix of P(T⊗1)P(in the basis above),for an arbitrary T∈B(H).Indeed,having done so the following facts become easy to verify.(1)1q k i=1p i<T v i,v i> = k i=1<T hv i,v i>=T r(T h).(2)1q(p i p j)1/2|T i,j|2.Hence,if we define a u.c.p.mapφ:B(H)→M q(C)byφ(T)=P(T⊗1)P then tr(φ(T))= T r(hT)for all T∈B(H)and,moreover,we have the following estimates:|T r(h1/2T h1/2T∗)−tr(φ(T)φ(T∗))|=ki,j=11q|T i,j|2p1/2i|p1/2i−p1/2j|≤ k i,j=11q|T i,j|2(p1/2i−p1/2j)2 1/2= T h1/2 2,T r h1/2T−T h1/2 2,T r.Now if T happens to be a unitary operator then T h1/2 2,T r= h1/2 2,T r=1and h1/2T−T h1/2 2,T r= T h1/2T∗−h1/2 2,T r and hence we can apply the Powers-Størmer inequality after the inequalities above to get:|T r(h1/2T h1/2T∗)−tr(φ(T)φ(T∗))|≤ T hT∗−h 1/21,T r.4NATHANIAL P.BROWNFinally,the Cauchy-Schwartz inequality applied to the Hilbert-Schmidt operators implies that for every unitary operator T∈B(H),tr(φ(T T∗)−φ(T)φ(T∗))≤|1−T r(h1/2T h1/2T∗)|+ T hT∗−h 1/21,T r=|T r(T hT∗)−T r(h1/2T h1/2T∗)|+ T hT∗−h 1/21,T r=|T r((T h1/2−h1/2T)h1/2T∗)|+ T hT∗−h 1/21,T r≤ h1/2T∗ 2,T r T h1/2−h1/2T 2,T r+ T hT∗−h 1/21,T r≤2 T hT∗−h 1/2.1,T rTheorem2.3.Letτbe a tracial state on A.Then the following are equivalent:(1)τ∈T(A)IM.(2)There exists a sequence of u.c.p.mapsφn:A→M k(n)(C)such that φn(ab)−φn(a)φn(b) 2,tr→0andτ(a)=lim n→∞tr◦φn(a),for all a,b∈A,where x 22,tr= tr(x∗x)for every x∈M k(n)(C).(3)For any faithful representation A⊂B(H)there exists a u.c.p.mapΦ:B(H)→πτ(A)′′such thatΦ(a)=πτ(a).Proof.(1)=⇒(2).Let A⊂B(H)be a faithful representation.Sinceτ∈T(A)IM we canfind a stateψon B(H)which extendsτand such thatψ(uT u∗)=ψ(T)for all unitaries u∈A and operators T∈B(H).Since the normal states on B(H)are dense in the set of all states on B(H)we canfind a net of positive operators hλ∈T such that T r(hλT)→ψ(T)for all T∈B(H).Sinceψ(u∗T u)=ψ(T)it follows that T r(hλT)−T r((uhλu∗)T)→0for every T∈B(H)and unitary u∈A.In other words,hλ−uhλu∗→0in the weak topology on T.Hence, by the Hahn-Banach theorem,there are convex combinations which tend to zero in L1-norm. In fact,takingfinite direct sums(i.e.considering n-tuples(u1hλu∗1−hλ,...,u n hλu∗n−hλ))one applies a similar argument to show that if F⊂A is afinite set of unitaries then for everyǫ>0 we canfind a positive trace class operator h∈T such that T r(h)=1,|T r(uh)−τ(u)|<ǫand h−uhu∗ 1<ǫfor all u∈F.Sincefinite rank operators are norm dense in T we may further assume that h isfinite rank with rational eigenvalues.Applying Lemma2.2to bigger and biggerfinite sets of unitaries and smaller and smaller epsilon’s we can construct a sequence of u.c.p.mapsφn:B(H)→M k(n)(C)such that tr(φn(u))→τ(u)and|tr(φn(uu∗)−φn(u)φn(u∗))|→0for every unitary u in a countable set with dense linear span in A.Sinceφn(uu∗)−φn(u)φn(u∗)≥0we have1−φn(u)φn(u∗) 22,tr≤ 1−φn(u)φn(u∗) tr(φn(uu∗)−φn(u)φn(u∗))→0.It follows that φn(ab)−φn(a)φn(b) 2,tr→0for every a,b∈A.Indeed,definingΦ=⊕φn: A→ΠM k(n)(C)⊂l∞(R)we can compose with the natural quotient map l∞(R)→Rωand it follows that every unitary such that φn(uu∗)−φn(u)φn(u∗) 22,tr→0and φn(u∗u)−φn(u∗)φn(u) 22,tr→0will fall in the multiplicative domain of the composition.However we have arranged that such unitaries have dense linear span and hence all of A falls in the multiplicative domain.(2)=⇒(3).Letφn:A→M k(n)(C)be a sequence of u.c.p.maps with the properties stated in the theorem.Identify each M k(n)(C)with a unital subfactor of R and we can define a u.c.p. map A→l∞(R)by x→(φn(x))∈ΠM k(n)(C)⊂l∞(R).Since theφn’s are asymptoticallyCONNES’EMBEDDING PROBLEM5 multiplicative in2-norm one gets aτ-preserving∗-homomorphism A→Rωby composing with the quotient map l∞(R)→Rω.The weak closure of A under this mapping will be isomorphic toπτ(A)′′and we can extend the mapping on A to all of B(H)because(a)l∞(R) is injective(hence wefirst extend into l∞(R))and(b)there exists a conditional expectation Rω→πτ(A)′′.(3)=⇒(1).Note that A falls in the multiplicative domain ofΦand henceΦis a bimodule map;i.e.Φ(aT b)=πτ(a)Φ(T)πτ(b)for all a,b∈A and T∈B(H).From this observation one easily checks that if we letτ′′denote the vector trace onπτ(A)′′thenτ′′◦Φis a state on B(H)which extendsτand which is invariant under the action of the unitary group of A on B(H).Henceτis an invariant mean.3.II1-factor representations of C∗(F∞)In this section we observe that every separable II1-factor contains a weakly dense copy of the universal C∗-algebra generated by a countably infinite set of unitaries(i.e.C∗(F∞)).Since every separable II1-factor M is generated by a countable number of unitaries it follows from universality that there is always a∗-homomorphism C∗(F∞)→M with weakly dense range. However,the next proposition completes the II1-factor representation theory of C∗(F∞);it is not particularly deep but rather amounts to some universal trickery.Proposition3.1.Let M be a II1-factor.There exists a∗-monomorphismρ:C∗(F∞)֒→M such thatρ(C∗(F∞))is weakly dense in M.Proof.Wefirst need to write C∗(F∞)as an inductive limit of free products of itself.That is,we defineA1=C∗(F∞),A2=A1∗C∗(F∞),...,A n=A n−1∗C∗(F∞),...,where∗denotes the full(i.e.universal)free product(with amalgamation over the scalars). Letting A denote the inductive limit of the sequence A1→A2→···it is easy to see(by universal considerations)that A∼=C∗(F∞).Since A is residuallyfinite dimensional(cf.[3]) we canfind a sequence of integers{k(n)}and a unital∗-monomorphismσ:A֒→ΠM k(n)(C). Note that we may naturally identify each A i with a subalgebra of A and hence,restricting σto this copy of A i,get an injection of A i intoΠM k(n)(C).To construct the desired embedding of A into M,it suffices to prove the existence of a sequence of unital∗-homomorphismsρi:A i→M with the following properties:(1)Eachρi is injective.=ρi,where we identify A i with the‘left side’of A i∗C∗(F∞)=A i+1.(2)ρi+1|Ai(3)The(increasing)union of{ρi(A i)}is weakly dense in M.To this end,wefirst choose an increasing sequence of projections p1≤p2≤···from M such thatτM(p i)→1.Then define orthogonal projections q2=p2−p1,q3=p3−p2,... and consider the II1-factors Q j=q j Mq j for j=2,3,....As is well known and not hard to construct,we can,for each j≥2,find a unital embeddingΠM k(n)(C)֒→Q j⊂M and thus we get a sequence of(orthogonal)embeddings A֒→ΠM k(n)(C)֒→Q j⊂M which will be denoted byσj.We are almost ready to construct theρi’s.Indeed,for each i∈N letπi:C∗(F∞)→p i Mp i be a(not necessarily injective!)∗-homomorphism with weakly dense range.We then define6NATHANIAL P.BROWNρ1asρ1=π1⊕ j ≥2σj |A 1 :A 1֒→p 1Mp 1⊕ Πj ≥2Q j ⊂M.Note that this is a unital ∗-monomorphism from A 1into M (since each σj is already faithful on all of A ).Now define a ∗-homomorphism θ2:A 2=A 1∗C ∗(F ∞)→p 2Mp 2as the free product of the ∗-homomorphisms A 1→p 2Mp 2,x →p 2ρ1(x )p 2,and π2:C ∗(F ∞)→p 2Mp 2.We then put ρ2=θ2⊕ j ≥3σj |A 2 :A 2֒→p 2Mp 2⊕ Πj ≥3Q j ⊂M.Note that ρ2|A 1=ρ1.Hopefully it is now clear how to proceed.In general,we construct a map (whose range is dense in p n +1Mp n +1)θn +1:A n +1=A n ∗C ∗(F ∞)→p n +1Mp n +1as the free product of the cutdown (by p n +1)of ρn and πn +1.This map need not be faithful and hence we take a direct sum with ⊕j ≥n +2σj |A n +1to remedy this deficiency.It is then easy tosee that these maps have all the required properties and hence the proof is complete.4.Proof of main resultWith Theorem 2.3and Proposition 3.1in hand we can now prove the main result.Theorem 4.1.Let M be a separable II 1-factor.Then M is embeddable into R ωif and only if M has a weak expectation relative to some weakly dense subalgebra.Proof.(=⇒)First assume that M ⊂R ω.By Proposition 3.1we may identify C ∗(F ∞)with a weakly dense subalgebra of M .Letting τdenote the unique trace on M we first claim that τ|C ∗(F ∞)is an invariant mean.To see this we note that since matrix algebras are weakly dense in R we can find a sequence M k (n )(C )⊂R such that each unitary in C ∗(F ∞)⊂M ⊂R ωlifts to a unitary in ΠM k (n )(C )⊂l ∞(R ).In other words,there is a ∗-homomorphism σ:C ∗(F ∞)→ΠM k (n )(C )such that π(σ(x ))=x for all x ∈C ∗(F ∞),where π:l ∞(R )→l ∞(R )/I ω=R ωis the canonical quotient mapping.By definition of the trace on R ωit follows that τ|C ∗(F ∞)is the weak −∗limit of traces on matrix algebras composed with homomorphisms C ∗(F ∞)→M k (n )(C )and hence τ|C ∗(F ∞)is an invariant mean.Now,if we move M to its left regular representation coming from τthen we can apply Theorem 2.3and conclude that M has a weak expectation relative to C ∗(F ∞).(⇐=)Now suppose that there exists a weakly dense C ∗-algebra A ⊂M ⊂B (H )and a u.c.p.map Φ:B (H )→M such that Φ(a )=a for all a ∈A .If τis the unique trace on M then it follows that τ|A is an invariant mean just as in the proof of (3)=⇒(1)from Theorem 2.3.From Theorem 2.3it follows that we can find a sequence of u.c.p.maps φn :A →M k (n )(C )which are asymptotically multiplicative (in 2-norm)and which asymptotically recover τ|A after composing with the traces on M k (n )(C ).Hence the u.c.p.mapping A →l ∞(R )given by x →(φn (x ))∈ΠM k (n )(C )⊂l ∞(R )induces a τ|A -preserving ∗-monomorphism A →R ωby composing with the quotient map l ∞(R )→R ω.It follows (essentially due to uniqueness of GNS representations)that the weak closure of A in R ωis isomorphic to M and the proof is complete. Finally we give the proof of the approximation property stated in the introduction.Note that a consequence of this result is that if Connes’embedding problem is true (i.e.every separable II 1-factor is embeddable)then R is the basic building block for all II 1-factors.It isCONNES’EMBEDDING PROBLEM7 hard for us to imagine that every II1-factor is built up from the inside by the nicest possible II1-factor,however a counterexample remains elusive.Corollary4.2.Let M⊂Rωbe a II1-factor,F⊂M be afinite set andǫ>0be given. Then there exists a complete order embeddingΦ:R֒→M(i.e.Φis an operator system isomorphism between R andΦ(R)–that is,Φis completely positive andΦ−1:Φ(R)→R is also completely positive)such that for each x∈F there exists r∈R such that x−Φ(r) 2<ǫ. Proof.Let afinite set F⊂M andǫ>0be given.Choose a projection p∈M such that τ(p)>1−ǫ.Note that the corner pMp is also embeddable into Rω(the fundamental group of Rωis R+).Now let C∗(F∞)⊂R be an identification with a dense subalgebra of R andπ:C∗(F∞)֒→pMp be a∗-monomorphism with weakly dense range.By Theorem2.3we canfind a u.c.p. mapΨ:R→pMp which extendsπ.Since we can alsofind a unital∗-homomorphism ν:R֒→(1−p)M(1−p)we get the desired complete order embedding by definingΦ:R→M byφ(r)=Ψ(r)⊕ν(r).References1.N.P.Brown,Invariant means andfinite representation theory of C∗-algebras,preprint2003.2.A.Connes,Classification of injective factors:cases II1,II∞,IIIλ,λ=1,Ann.Math.104(1976),73–115.3.K.R.Davidson,C∗-algebras by example,Fields Institute Monographs6,American Mathematical Society,Providence,RI,1996.4.U.Haagerup,Spectral decomposition of all operators in a II1-factor which is embeddable in Rω,MSRInotes,2001.5.E.Kirchberg,On nonsemisplit extensions,tensor products and exactness of group C∗-algebras,Invent.Math.112(1993),449–489.nce,On nuclear C∗-algebras,J.Funct.Anal.12(1973),157–176.7.N.Ozawa,About the QWEP conjecture,preprint2003.Department of Mathematics,Penn State University,State College,PA16802E-mail address:nbrown@。
