You are an expert at summarizing long articles. Proceed to summarize the following text: 
many optimization problems of interest can be phrased as picking a maximum - weight independent subset from a ground set of elements , for a suitable definition of independence . a well - known example is the ( maximum - weight ) independent set problem on graphs , where we wish to find a set of vertices , no two of which are adjacent . a more tractable problem in this setting is the maximum - weight matching problem , in which we wish to find a set of edges such that no two edges share an endpoint . this notion of independence can be naturally extended to hypergraphs , where a set of hyperedges is considered independent if no two hyperedges share a vertex .    in the previous examples , independent sets are characterized by forbidding certain _ pairs _ of elements from the ground set . a somewhat related , but different notion of independence comes from the independent sets of a matroid . for example , in the uniform matroid of rank @xmath9 , any set of at most @xmath9 elements is independent . for graphic matroids , a set of edges in an undirected graph is independent if and only if it does not contain a cycle ; the optimization goal is to find a maximum - weight acyclic subgraph of a graph @xmath0 . in transversal matroids , a set of left - vertices of a bipartite graph is independent if and only if there is a matching that matches each vertex in this set to some right - vertex .    in many applications , the elements of the ground set and their weights are not known in advance , but arrive online one at a time . when an item arrives , we must immediately decide to either irrevocably accept it into the final solution , or reject it and never be able to go back to it again . we will be interested in competitive analysis , that is , comparing the performance of an online algorithm to an optimal offline algorithm which is given the whole input in advance . in this setting , even simple problems like selecting a maximum - weight element become difficult , because we do not know if elements that come in the future will have weight significantly higher or lower than the element currently under consideration . if we make no assumptions about the input , any algorithm can be fooled into performing arbitrarily poorly by ofering it a medium - weight item , followed by a high - weight item if it accepts , and a low - weight item if it rejects . to solve such problems , which frequently arise in practice , various assumptions are made . for instance , one might assume that weights are all drawn from a known distribution , or ( if independent sets may contain several elements ) that the weight of any single element is small compared to the weight of the best independent set . one useful assumption that can be made is that the elements of the ground set appear in a random order . the basic problem in which the goal is to select the maximum - weight element is well known as the _ secretary problem_. it was first published by martin gardner in @xcite , though it appears to have arisen as folklore a decade previously @xcite . an optimal solution is to observe the first @xmath10 elements , and select the first element from the rest with weight greater than the heaviest element seen in the first set ; this algorithm gives a @xmath11 probability of finding the heaviest element , and has been attributed to several authors ( see @xcite ) . motivated by this simple observation , several results have appeared for more complex problems in this random permutation model ; these are often called secretary - type problems . typically , given a random permutation of elements appearing in an online fashion , the goal is to find a maximum - weight independent set . for example , kleinberg @xcite gives a @xmath12-competitive algorithm for the problem of selecting at most @xmath9 elements from the set to maximize their sum . et al . _ @xcite give a constant - competitive algorithm for the more general knapsack secretary problem , in which each element has a size and weight , and the goal is to find a maximum - weight set of elements whose total size is at most a given integer @xmath13 . babaioff _ et al . _ @xcite had earlier introduced the so - called _ matroid secretary problem _ , and gave an @xmath14-competitive algorithm to find the max - weight independent set of elements , where @xmath9 is the rank of the underlying matroid . a @xmath15-competitive algorithm was also given in @xcite for the special case of graphic matroids ; this was based on their @xmath16-competitive algorithm algorithm for the important case of _ transversal matroids _ , where @xmath17 is the maximum degree of any left - vertex . recently , dimitrov and plaxton @xcite improved the latter to a ratio of @xmath15 for all transversal matroids . a significant open question is whether there exists a @xmath18-competitive algorithm for general matroids , or for other secretary problems with non - matroid constraints . these secretary - type problems arise in many practical situations where decisions must be made in real - time without knowledge of the future , or with very limited knowledge . for example , a factory needs to decide which orders to fulfil , without knowing whether more valuable orders will be placed later . buyers and sellers of houses must decide whether to go through with a transaction , though they may receive a better offer in a week or a month . below , we give an example from online advertising systems , which we use as a recurring motivation through the paper . internet - based systems are now being used to sell advertising space in other media , such as newspapers , radio and television broadcasts , etc . advertisers in these media typically plan advertising campaigns and reserve slots well in advance to coincide with product launches , peak shopping seasons , or other events . in such situations , it is unreasonable to run an auction immediately before the event to determine which ads are shown , as is done for sponsored search and other online advertising . consider an automatic advertising reservation system , in which the seller controls a number of _ slots _ , each representing a position in which an advertisement ( hereafter _ ad _ ) can be published . advertisers / bidders appear periodically , and report which slots they would like to place an ad in , and how much they are willing to pay for each slot . when an advertiser reports a bid , the system must immediately decide whether or not to accept it ; if a bid is accepted , the ad _ must _ be placed in the corresponding slot , and if not , the ad is permanently rejected . note that in disallowing the removal of an accepted ad , our model differs significantly from that of @xcite , in which the seller can subsequently remove an accepted ad if he makes a compensatory payment to the advertiser . we model this system as as an online edge - weighted matching problem on a bipartite graph @xmath19 : the vertices of set @xmath3 correspond to the set of slots , and those of set @xmath4 to the ads . for each vertex @xmath7 , its neighbors in @xmath3 correspond to the slots in which ad @xmath6 can appear , and the weight of edge @xmath20 is the amount the advertiser is willing to pay if @xmath6 appears in slot @xmath21 . initially , the seller knows the set of slots @xmath3 ; vertices of @xmath4 appear sequentially in a random order , as advertisers bid on slots . when a vertex @xmath7 is seen , all the edges from @xmath6 to @xmath3 are revealed , together with their weights ; the seller must immediately decide whether to accept ad @xmath6 , and if so , which of the relevant slots to place it in . the seller s goal , obviously , is to maximize his revenue . subsequently , we refer to this problem as bipartite vertex - at - a - time matching ( bvm ) . we describe our results for bvm and other problems below . recall that the elements of a transversal matroid are one partite set @xmath4 ( subsequently referred to as the _ left vertices _ ) of a bipartite graph , and a set of vertices @xmath22 is independent if the graph constains a perfect matching from @xmath23 to the other partite set . that is , the transversal matroid secretary problem is equivalent to the special case of bvm in which all edges incident to each @xmath7 have the same weight . ( equivalently , the weights are on vertices of @xmath4 instead of edges . ) in section  [ sec : bvm ] , we give a simpler and tighter analysis for an algorithm essentially similar to that of dimitrov and plaxton @xcite for transversal matroids ; this allows us to improve the competitive ratio from 16 to 8 , even for the more general bvm problem . in addition to an improved ratio , our methods are of interest as they appear robust to changes in the model and can be naturally applied to more general problems . we illustrate this in section  [ sec : hypergraphs ] by extending our algorithms to hypergraph problems , with applications to more complex advertising systems in which advertisers desire _ bundles _ of slots , as opposed to a single slot . in particular , we obtain constant - competitive algorithms for finding independent edge sets in hypergraphs of constant edge - size . we also introduce secretary problems with _ groups _ , to model applications in which we do not see a truly random permutation of elements . we assume that an adversary can group the elements arbitrarily , but once the groups are constructed , they appear in random order . when a group appears , the algorithm can see all the elements in the group . we discuss this idea further in section  [ sec : groups ] . finally , in section  [ sec : graphic ] , we obtain a simple @xmath8-competitive algorithm for the problem of finding independent edge - sets in graphic matroids , improving the ratio of 16 from @xcite . the majority of our algorithms follow the `` sample - and - price '' method common to many solutions to secretary problems . that is , we look at a random sample of elements containing a constant fraction of the input , and use the values observed to determine _ prices _ or thresholds . in the second half , we accept an element if its weight / value is above the given price . for instance , in the optimal solution to the original secretary problem , the price is set to be the highest value seen in the first @xmath11 fraction of the input , and we accept any element from the remaining set with value greater than this price . recall that in the bvm problem , the algorithm is initially given one partite set @xmath3 of a bipartite graph @xmath19 , together with the size of the other partite set @xmath4 . the algorithm sees the vertices of @xmath4 sequentially , in a random order . when a vertex @xmath7 is seen , all edges incident to @xmath6 are revealed , together with their weights . the algorithm must immediately either match @xmath6 to an available vertex of @xmath3 , or decide that @xmath6 will remain permanently unmatched . in this section , we show that an algorithm based on that of @xcite gives a competitive ratio of 8 for this problem . before presenting the algorithm for bvm , we describe a closely related algorithm simulate that is easier to analyze , and then show that our final algorithm does at least as well as simulate . let greedy denote the following greedy algorithm for the offline edge - weighted bipartite matching problem :    : + sort edges of @xmath24 in decreasing order of weight . + matching @xmath25 + for each edge @xmath26 , in sorted order + if @xmath27 is a matching : + @xmath28 + return @xmath29 . let @xmath30 denote the weight of a set of edges @xmath31 , and @xmath32 denote the weight of an optimum ( max - weight ) matching on @xmath0 . it is easy to see the following proposition , that greedy is a 2-approximation . @xmath33 . we now describe the algorithm simulate , which we use purely to analyze our final algorithm for bvm .    : + sort edges of @xmath34 in decreasing order of weight . + @xmath35 + mark each vertex @xmath7 as unassigned . + for each edge @xmath36 , in sorted order + if @xmath6 is unassigned * and * @xmath37 is a matching : + mark @xmath6 as assigned + flip a coin with probability @xmath38 of heads + if heads , @xmath39 + else @xmath40 + @xmath41 + for each vertex @xmath42 + if @xmath21 has degree @xmath43 in @xmath44 + delete all edges incident to @xmath21 from @xmath44 . say that an edge @xmath45 is _ considered _ by simulate if we flip a coin and assign @xmath45 to either @xmath46 or @xmath47 . we make two observations about simulate : once any edge incident to a vertex @xmath7 has been considered , no other edge incident to @xmath6 will be considered later . second , once an edge incident to @xmath42 has been added to @xmath46 , no subsequent edge incident to @xmath21 will be considered . ( note that multiple edges incident to @xmath21 might be considered until one of these edges is added to @xmath46 . ) observe that from our description of simulate , @xmath46 is a matching , but @xmath47 may not be , as a vertex @xmath42 may be incident to multiple edges of @xmath47 . hence , we have a final pruning step in case there are multiple edges incident to the same vertex of @xmath3 ; this gives us a matching @xmath44 . we now prove three statements about simulate , and later show that the matching returned by our online algorithm is at least as good as @xmath44 . [ prop : wm1 ] @xmath48 } \ge p { \text{\sc opt}}/2 $ ] . simulate tosses a coin ( at most ) once for each vertex in @xmath4 ; @xmath46 is precisely the matching one would obtain from running greedy on @xmath49 , where @xmath50 denotes the vertices which came up heads . ( if the coin for a vertex comes up tails , this vertex has no effect on @xmath46 . ) if @xmath51 denotes the weight of an optimum matching on @xmath52 , it is easy to see that @xmath53 } \ge p    { \text{\sc opt}}$ ] , and hence that @xmath48 } \ge p { \text{\sc opt}}/2 $ ] .    [ lem : wm2 ] @xmath54 } \ge ( 1-p ) { \text{\sc opt}}/2 $ ] . consider any history of coin tosses in which an arbitrary edge @xmath45 is being considered , and we are about to flip a coin to determine whether @xmath45 is added to @xmath46 or @xmath47 . its expected contribution to @xmath46 is @xmath55 , and to @xmath47 , is @xmath56 . this holds for each edge @xmath45 and any history in which @xmath45 can contribute to the weight of @xmath46 or @xmath47 ; hence @xmath54 } = \frac{(1-p)}{p }    { \mathbb{e}[w(m_1)]}$ ] , completing the proof . [ lem : wm3 ] @xmath57 } \ge \frac{p^2(1-p)}{2 } { \text{\sc opt}}$ ] .    for each vertex @xmath58 , let @xmath59 denote the revenue earned by vertex @xmath60 in @xmath47 , which we define as the sum of the weights of edges in @xmath47 incident to @xmath60 . ( hence , @xmath61 . ) for each edge @xmath45 incident to @xmath60 , let @xmath62}$ ] denote the expected revenue earned by @xmath60 in @xmath47 , conditioned on the fact that @xmath45 is the first edge incident to @xmath60 selected by simulate for @xmath47 . it is easy to see that @xmath62 } \le w(e)/p$ ] , by considering how @xmath60 can earn revenue : if the next edge incident to @xmath60 considered by simulate is added to @xmath46 ( which happens with probability @xmath38 ) , then @xmath60 earns precisely @xmath63 , as no later edge incident to @xmath60 can ever be considered . in general , if @xmath60 is incident to @xmath64 edges in @xmath47 , the revenue it earns is at most @xmath65 , and the probability of this event is at most @xmath66 ; this is because the next @xmath67 edges incident to @xmath60 that are considered must be added to @xmath47 , and the @xmath64th edge is added to @xmath46 . therefore , @xmath68 } \le w(e ) \sum_{i=1}^\infty i    \cdot p ( 1-p)^{i-1 } = w(e)/p$ ] . similarly , for each vertex @xmath58 , let @xmath69 denote the revenue earned by vertex @xmath60 in @xmath44 , which is the weight of the ( at most one ) edge incident to @xmath60 in @xmath44 . let @xmath70}$ ] denote the expected revenue earned by @xmath60 , conditioned on @xmath45 being the first edge incident to @xmath60 added to @xmath47 . with probability @xmath38 , the next considered edge incident to @xmath60 is added to @xmath46 , and hence @xmath60 has degree 1 in @xmath47 . @xmath70 } \ge p    w(e)$ ] , and so @xmath70 } \ge p^2 { \mathbb{e}[{revenue}_2(v)|e]}$ ] ; it follows that @xmath57 } \ge p^2 { \mathbb{e}[w(m_2 ) ] } = \frac{p^2      ( 1-p)}{2 } { \text{\sc opt}}$ ] .    before describing our final algorithm for ebp , we show that the matching returned by an intermediate algorithm sampleandpermute is at least as good as @xmath44 , which implies that we have a @xmath71-competitive algorithm : setting @xmath72 , we get a @xmath73-competitive algorithm . however , our pruning step allows us to take an edge for @xmath44 only if its right endpoint has degree 1 ; a more careful pruning step allows more edges in the matching . we use this fact to give a tighter analysis for the next algorithm , obtaining a competitive ratio of 8 .    : + @xmath74 + for each @xmath7 : + with probability @xmath38 , @xmath75 + @xmath76 greedy(@xmath77 $ ] ) . + for each @xmath42 : + set @xmath78 to be the weight of the edge incident to @xmath21 in @xmath46 . + @xmath79 + for each @xmath80 , in random order : + let @xmath81 be the highest - weight edge such that @xmath82 + add @xmath45 to @xmath47 . + if @xmath27 is a matching , add @xmath45 to @xmath29 . note that the matching @xmath46 in sampleandpermute is precisely the same as @xmath46 from simulate ; intuitively , in the former , we toss all the coins at once and run greedy , while in the latter , we toss coins while constructing the greedy matching . ( more precisely , the two algorithms to generate the matchings are equivalent . ) similarly , the `` matching '' @xmath47 in this algorithm is essentially @xmath47 from simulate . the difference between the two algorithms is in the pruning step : to construct @xmath44 in simulate , we delete all edges incident to any vertex @xmath42 with degree greater than 1 ; in sampleandpermute , we add to @xmath29 the first such edge seen in our permutation of @xmath83 . it follows immediately from lemma  [ lem : wm3 ] that @xmath84 } \ge p^2(1-p ) { \text{\sc opt}}/2 $ ] , but accounting for the difference in pruning allows the following tighter statement , which we prove in the appendix . [ lem : tighterbound ] @xmath84 } \ge \frac{p ( 1-p)}{2 } { \text{\sc opt}}$ ] . we now present our final algorithm , a trivial modification of sampleandpermute for the online bvm problem . + @xmath85 + let @xmath50 be the first @xmath9 vertices of @xmath4 . + @xmath76 greedy(@xmath77 $ ] ) . + for each @xmath42 : + set @xmath78 to be the weight of the edge incident to @xmath21 in @xmath46 . + @xmath25 + for each subsequent @xmath80 , : + let @xmath81 be the highest - weight edge such that @xmath82 + if @xmath27 is a matching , accept @xmath45 for @xmath29 . as the input to sampleandprice is a random permutation , @xmath50 is a subset of @xmath4 in which each vertex of @xmath4 is selected with probability @xmath38 ; it is easy to see that this algorithm is equivalent to sampleandpermute . therefore , @xmath84 } \ge \frac{p    ( 1-p)}{2 } { \text{\sc opt}}$ ] ; setting @xmath86 implies that the expected competitive ratio is 8 . in the hypergraph edge - at - a - time matching ( hem ) problem , we are initally given the vertex set of a hypergraph ; subsequently , hyperedges appear in a random order . when an edge ( together with its weight ) is revealed , the algorithm must immediately decide whether or not to accept it ; as before , the goal is for the algorithm to select a maximum - weight set of disjoint edges . for arbitrary hypergraphs , one can observe that even the offline version of this problem is np - complete ( and also hard to approximate ) via an easy reduction from the independent set problem . however , the difficulty is related to the size of the hyperedges ; if all edges contain only 2 vertices , for instance , then we are simply trying to find a matching in a ( possibly non - bipartite ) graph . ( even in this special case , the problem is of interest in an online setting . ) let @xmath17 denote the maximum size of an edge in the hypergraph . we provide an @xmath87-competitive algorithm for the hem problem by solving the more general hypergraph vertex - at - a - time matching ( hvm ) problem , described as follows : we are initally given a subset @xmath3 of the vertex set of a hypergraph . the remaining vertices @xmath4 arrive online ; each edge of the hypergraph is constrained to contain exactly one vertex of @xmath4 , together with some vertices of @xmath3 . the vertices of @xmath4 appear online in a random order ; when @xmath7 is revealed , the algorithm also sees all edges incident to @xmath6 , together with their weight . at this point , the algorithm must immediately decide whether or not to accept some edge containing @xmath6 , and if so , which edge ; again , the goal is for the algorithm to select a maximum - weight set of disjoint edges . here , let @xmath17 denote the maximum number of vertices of @xmath3 contained in a single edge ( so the largest edge has @xmath88 vertices ) . first , we observe that the hem problem with edge size @xmath17 reduces to the hvm problem with edge size @xmath88 : let @xmath3 be the vertex set of the original hypergraph , and add one vertex to @xmath4 for each original edge . an edge of the new hypergraph consists of an old edge , together with the corresponding vertex of @xmath4 . clearly , observing a random permutation of @xmath4 together with the incident edges is equivalent to a random permutation of the edge set of the original hypergraph . also , notice that the the bvm problem of section  [ sec : bvm ] is simply the special case of hvm when @xmath89 . ( see figure 1 at the end of this section . ) these hypergraph problems capture the notion of demand _ bundles_. for instance , in ad reservation systems , advertisers rarely make reservations for a single ad at a time ; they are more likely to plan advertising campaigns involving multiple individual ads . in many campaigns , advertisers create various ads which are related to and complement or reinforce each other ; these advertisers might be interested in acquiring a bundle or set of slots for this campaign . they submit to the reservation system the bundles they are interested in , together with the price they are willing to pay ; the system must either accept a request for an entire bundle or reject it , as it does not receive revenue for providing the advertiser with a part of the bundle . if each advertiser submits a request for a single bundle , we obtain the hem problem with vertex set corresponding to the set of slots . more generally , an advertiser may submit a request for _ one of _ a set of bundles , together with a price for each bundle . ( for example , an advertiser might want an ad to appear in any three out of four local newspapers . ) this leads to the hvm problem , with vertex set @xmath4 corresponding to the set of advertisers , and set @xmath3 to the set of slots : we receive a random permutation of advertisers , and each advertiser informs us of the bundles she is interested in , together with a price for each bundle . let greedy denote the offline algorithm for hvm that sorts edges in decreasing order of weight , and selects an edge if it is disjoint from all previously selected edges . for ease of exposition , we subsequently assume that the hypergraph is @xmath90-uniform ; that is , that each edge contains exactly @xmath17 vertices of @xmath3 together with one vertex of @xmath4 . greedy returns a @xmath90-approximation to the maximum - weight disjoint edge set . we again define an algorithm simulate , as in section  [ sec : bvm ] :    sort edges of @xmath24 in decreasing order of weight . + mark each vertex @xmath7 as unassigned . + @xmath35 + for each edge @xmath26 in sorted order : + let @xmath6 be the vertex of @xmath4 in @xmath45 + if @xmath6 is unassigned * and * @xmath45 is disjoint from @xmath46 : + mark @xmath6 as assigned . + flip a coin with probability @xmath38 of heads + if heads , add @xmath45 to @xmath46 + if tails , add @xmath45 to @xmath47 + @xmath91 + for each @xmath92 : + add @xmath45 to @xmath44 if @xmath45 is disjoint from the rest of @xmath47 .    as before , we let @xmath30 denote the weight of an edge set @xmath31 . the proofs of the following two propositions are exactly analogous to proposition  [ prop : wm1 ] and lemma  [ lem : wm2 ] . @xmath48 } \ge p \cdot { \text{\sc opt}}/(d+1)$ ] . @xmath54 } \ge ( 1-p ) { \text{\sc opt}}/(d+1)$ ] . it is now slightly more complex to bound the weight of @xmath44 than it was for the bvm problem ; for bvm , the set of edges in @xmath47 incident to @xmath58 interfere only with each other , but in the hypergraph version , edges @xmath93 and @xmath94 might not intersect , though they may both intersect @xmath95 , and hence all of @xmath96 will have to be deleted . however , we can use a similar intuition : in bvm , we charge all edges of @xmath47 incident to @xmath60 to the heaviest such edge ; in expectation , each edge is charged a constant number of times . for the hvm problem , we charge all the edges in a `` connected component '' to the heaviest edge in the component , and argue that ( with a suitable choice of @xmath38 ) the average size of the components is small . more formally , we prove the following lemma :    [ lem : hvm ] setting @xmath97 , @xmath57 } \ge \frac{{\text{\sc opt}}}{12 d(d+1)}$ ] . construct an auxiliary directed graph @xmath31 as follows : for each @xmath98 , add a corresponding vertex @xmath99 to @xmath31 . if @xmath100 is the heaviest edge in @xmath47 that intersects @xmath45 , add a directed arc from @xmath99 to @xmath101 to @xmath31 . ( if @xmath45 itself is this heaviest edge , @xmath99 has no out - neighbors . ) note that the graph @xmath31 is obviously a forest . for each @xmath92 , if @xmath99 is not the root of its tree in @xmath31 , we define @xmath102 to be 0 , and if it is the root , we set @xmath102 to be the weight of all edges of @xmath47 in the tree . clearly , @xmath103 . we define @xmath104 to be equal to the weight of @xmath45 iff @xmath45 is an edge in @xmath47 that does not intersect any other such edge . ( in which case , it follows that @xmath99 is the root of its tree . ) we prove that @xmath105 } \ge \frac{{\mathbb{e}[{revenue}_2(e)]}}{6}$ ] , which proves the lemma , since @xmath106 . first , note that the probability that any edge @xmath45 added to @xmath47 intersects an edge added later is at most @xmath107 : for each vertex @xmath108 of @xmath3 contained in @xmath45 , the probability that @xmath45 intersects a later edge because of @xmath108 is at most @xmath109 , as with probability @xmath110 , the next edge containing @xmath108 considered by simulate will be added to @xmath46 . as @xmath45 contains only @xmath17 vertices in @xmath3 , the desired probability is at most @xmath107 . ( every vertex of @xmath4 is incident to at most one edge in @xmath47 , and so @xmath45 can not intersect any other edge through its vertex in @xmath4 . ) it follows that the probability that any @xmath111 has a child is at most @xmath107 . we also count the expected number of children of @xmath99 ; the edge corresponding to each child of @xmath99 must share some vertex with @xmath45 , and the expected number of children through a particular vertex is at most @xmath112 . as @xmath45 contains @xmath17 vertices of @xmath3 , the expected number of children of @xmath99 is at most @xmath113 ; since @xmath114 , the expected number of children is at most @xmath115 . it follows that the expected size of a subtree rooted at @xmath99 is at most @xmath116 . note that @xmath102 and @xmath104 are both @xmath117 if @xmath99 is not the root of its tree in @xmath31 . conditioned on @xmath99 being a root , @xmath118 } \le 3 w(e)$ ] , as @xmath45 is the heaviest edge in its tree , and the expected size of the tree is at most @xmath116 . @xmath105}$ ] is at least @xmath119 , as @xmath45 intersects no previously added edges , and with probability at least @xmath107 , it intersects no edge added to @xmath47 later . therefore , the ratio of these expectations is at most @xmath120 , completing the proof . now , we define our final algorithm sampleandprice for the hvm problem :     + @xmath121 + let @xmath50 be the first @xmath9 elements of @xmath4 . + @xmath76 greedy(@xmath122 ) . + for each @xmath123 : + set @xmath124 to be the weight of the edge incident to @xmath60 in @xmath46 . + @xmath25 + for each subsequent @xmath80 : + let @xmath45 be the highest - weight edge containing @xmath6 such that for each @xmath125 , @xmath126 + if @xmath45 is disjoint from @xmath29 , add @xmath45 to @xmath29 .    as before , since the input is a random permutation of @xmath4 , @xmath50 is a subset of @xmath4 in which every vertex is selected independently with probability @xmath127 , and the matching @xmath29 is at least as good as @xmath44 from simulate . therefore , we have proved the following theorem :    [ thm : hvm ] sampleandprice is an @xmath87-competitive algorithm for the hvm secretary problem . note that @xmath29 may also contain extra edges that occur earlier in the permutation than edges they intersect ; for the bvm problem , this was the difference between lemma  [ lem : wm3 ] and the stronger bound [ lem : tighterbound ] . we do not provide a tighter analysis similar to lemma  [ lem : tighterbound ] for the hvm problem in this extended abstract , nor make an attempt to optimize the constants of lemma  [ lem : hvm ] . in particular , for the hem problem with @xmath128 ( finding an online matching in a non - bipartite graph @xmath129 , given a random permutatation of @xmath24 ) , we have a constant bound on the competitive ratio ; a smaller constant can easily be obtained . ( hvm ) at ( 2,3 ) hvm(@xmath88 ) ; ( hem ) at ( 0,1.5 ) hem(@xmath17 ) ; ( bvm ) at ( 4,1.5 ) bvm ; ( bem ) at ( 0,0 ) edge - at - a - time matchings ; at ( 0,-0.5 ) ( in arbitrary graphs ) ; ( tvs ) at ( 4,0 ) transversal matroid secretary ;    ( hvm )  ( hem ) ; ( hvm )  ( bvm ) ; ( hem )  ( bem ) ; ( bvm )  ( tvs ) ; consider a secretary - type problem in which , instead of receiving a random permutation of the elements , elements can be grouped by an adversary . the algorithm receives the number of groups in advance , instead of the number of elements . however , once the groups have been constructed , they arrive in random order ; when a group arrives , the algorithm can see all its elements at once . note that the groups are fixed in advance ; the adversary can not construct groups in response to the algorithm s choices or the set of groups seen so far . the effect of such grouping on the difficulty of the problem is not immediately clear : the adversary can ensure that some permutations of the element set never occur , which might make the problem more difficult . on the other hand , as the algorithm is allowed to see several elements at once , it may be easier to compute a good solution . for instance , consider the classical secretary problem with groups . an optimal algorithm will never hire any but the best secretary from a group , and it is easy to obtain an @xmath45-competitive algorithm : ignore all but the best secretary from each group , and run the standard secretary algorithm on these . that is , observe a constant ( @xmath11 ) fraction of the groups , and note the value / price of the best secretary seen so far . from the rest of the input , hire the best secretary from the first group with a secretary to beat this price . perhaps a reason this problem is as easy as the original version is that only one element is to be selected .    by way of contrast , consider the following matching problem , even restricted to bipartite graphs : the algorithm is initially given the vertex set of a bipartite graph , and an adversary groups the edges arbitrarily . the groups arrive in random order ; when a group arrives , the algorithm sees the weights of all edges it contains . the goal is to find a maximum - weight matching ; note that as a special case of hem with @xmath128 , we have an @xmath18-competitive algorithm for this problem without edge grouping . a natural sample - and - price algorithm for this problem is as follows : look at a constant fraction of the input , and construct a matching with these edges ( either the optimal matching , or the greedy matchings we used in the previous sections ) . use the weights of edges in the matching to set vertex prices , and in the remainder of the input , select an edge if its weight is at least the price of each of its endpoints , and if it does not conflict with edges already selected . unfortunately , this algorithm does not work : consider a bipartite graph @xmath130 , with @xmath131 and @xmath132 . we have two groups of edges : @xmath133 , with @xmath134 , and @xmath135 , with @xmath136 . assuming @xmath137 , @xmath138 corresponds to an optimal matching , with weight @xmath139 . if @xmath138 arrives first , the price of each @xmath140 is @xmath141 . subsequently , when @xmath142 arrives , @xmath143 = @xmath144 , and hence no edge of @xmath142 beats the price of its right endpoint . if @xmath142 arrives first , the price of each @xmath145 is @xmath146 . subsequently , when @xmath138 arrives , @xmath147 , and so no edge except @xmath148 beats the price of its left endpoint , for a total revenue of @xmath149 . we believe , therefore , that the introduction of groups affects these secretary - type problems in non - trivial ways , and these problems are likely to be of theoretical interest ; in addition , they have applications to problems where groups occur naturally , and we do not receive a random permutation of the entire element set . to take another example from the advertising world , when a merchant plans a campaign , she may submit to the reservation system multiple ads , together with the slots in which each ad can be placed , and a price for each ad - slot combination . even if the merchants arrive in a random order , this does not correspond to a random permutation of ads , and hence our previous analysis is not directly applicable . we model this ( as in bvm ) as an edge - weighted matching problem on a bipartite graph @xmath19 in which vertices of @xmath4 may be grouped ; here , the groups correspond to the set of ads for a given advertiser . the algorithm initially receives @xmath3 ( the set of slots ) , and the number of advertisers / groups ; the adversary can construct groups from @xmath4 arbitrarily . once the groups have been fixed , a random permutation of the groups is seen , and when a group arrives , the algorithm must decide which ads to accept , and where to place them ; as always , decisions are irrevocable . we refer to this as the bvm problem with groups . [ thm : bvmlogn ] there is an @xmath150-competitive algorithm for the bvm problem with groups . it is easy to prove this theorem using standard techniques : sample the first half of the vertices , and let @xmath151 denote the weight of the heaviest edge seen so far . pick an integer @xmath152 uniformly at random in @xmath153 $ ] , and set a threshold of @xmath154 . in the second half , greedily construct a matching using edges with weight above the threshold . ( see , for instance , theorem 3.2 of @xcite for analysis of an essentially similar algorithm . ) for completeness , we give a proof of theorem  [ thm : bvmlogn ] in section  [ subsec : otherproofs ] of the appendix . a natural question is whether one can find a constant - competitive algorithm for bvm with groups . note that one must be careful about using sample - and - price algorithms : first , as the example above shows , the natural algorithm with groups of edges instead of vertices does not work . second , one might sample a constant fraction of groups , construct a matching @xmath46 on the sampled groups , and then use @xmath46 to set prices . however , once prices have been set in this way , the edges assigned to a group @xmath155 may not be the same as the edges that would have been assigned to @xmath155 in @xmath46 if @xmath155 had been sampled . this was not the case for the basic bvm problem : if an edge @xmath20 is in @xmath47 , then by construction  fixing all other coin flips if the coin for @xmath6 had come up heads instead of tails , @xmath20 would be in @xmath46 . as the example in figure  [ fig:2 ] shows , this desirable property no longer holds once groups are introduced . = [ circle , draw , inner sep=0pt , minimum size=6 mm ] ;    \(a ) at ( 0,2 ) [ vertex ] @xmath156 ; ( b ) at ( 0,1 ) [ vertex ] @xmath13 ; ( c ) at ( 0,0 ) [ vertex ] @xmath157 ;    \(x ) at ( 4,1.5 ) [ vertex ] @xmath158 ; ( y ) at ( 4,0.5 ) [ vertex ] @xmath159 ;    \(a )  ( x ) ; at ( 2,1.9 ) 4 ; ( b )  ( x ) ; at ( 2,1.4 ) 3 ; ( b )  ( y ) ; at ( 2,0.9 ) 2 ; ( c )  ( y ) ; at ( 2,0.4 ) 1 ;    we conjecture that the following algorithm samplewithgroups is constant - competitive for bvm with groups . here , @xmath160 denotes the set of groups :     + sample each group with probability @xmath38 . + construct a greedy matching @xmath46 on the set of sampled groups @xmath161 . + @xmath162 . + for each group @xmath155 in @xmath163 : + let @xmath164 denote the edges assigned to vertices of @xmath155 in the greedy matching on @xmath165 . + @xmath166 . + @xmath41 + for each @xmath42 : + if @xmath21 has degree @xmath43 in @xmath44 : + delete all edges incident to @xmath21 from @xmath44 . it is easy to see that @xmath48 } \ge p { \text{\sc opt}}/2 $ ] . by construction , the edges assigned to @xmath155 in @xmath47 are precisely those that would have been assigned to @xmath155 in @xmath46 if @xmath155 had been sampled . ( hence , this algorithm differs from the natural sampleandprice . ) therefore , it follows that the probability an edge contributes to @xmath47 is @xmath167 times the probability it contributes to @xmath46 . if @xmath86 , it follows that @xmath54 } = { \mathbb{e}[w(m_1)]}$ ] , and further , that the expected degree of @xmath42 in @xmath47 is equal to its expected degree in @xmath46 , which is at most 1 since @xmath46 is a matching . this does not suffice to give a lower bound on the expected weight of @xmath44 , but we conjecture that the expected weight of @xmath44 is at most a constant factor lower than that of @xmath47 . samplewithgroups is constant - competitive for the bvm problem with groups . in this section , we describe a @xmath8-competitive algorithm for the graphic matroid secretary problem . here , we are initially given the set of vertices @xmath168 of an undirected edge - weighted graph @xmath169 together with the size of its edge set @xmath170 . the edges of the graph appear in a random order , and the goal is to accept a maximum - weight subset of edges @xmath31 that does not contain any cycles . as always , the decision to accept an edge must be made upon its arrival , and can not be revoked . this problem is equivalent to finding the maximum - weight spanning tree ( assuming @xmath0 is connected ) and is also equivalent to finding the maximum - weight independent set in the graphic matroid defined by the graph @xmath0 . babaioff et al . @xcite give a 16-competitive algorithm for the secretary version of this problem based on a related algorithm for transversal matroids . we give a simple reduction to the classical secretary problem , losing a factor of @xmath171 in the reduction . in this way , we obtain a @xmath172-competitive algorithm for the graphic matroid secretary problem . fix an ordering @xmath173 on the vertices of @xmath0 . consider two directed graphs : graph @xmath174 is obtained by orienting every edge of @xmath0 from higher numbered to lower numbered vertex , and graph @xmath175 by orienting every edge from lower to higher numbered vertex . our online algorithm initially flips a fair coin @xmath176 . for each vertex @xmath60 independently , it runs a secretary algorithm to find the maximum - weight edge leaving @xmath60 in @xmath177 . the output of the algorithm is @xmath178 , the union of all edges accepted by the individual secretary algorithms . since the graph @xmath177 is acyclic and each vertex has at most one outgoing edge , the set of edges @xmath178 must be acyclic even in the undirected sense . it remains to show a lower bound on the weight of @xmath178 . for each vertex @xmath60 , let @xmath179 be the heaviest edge leaving vertex @xmath60 in @xmath177 . let @xmath180 . let @xmath181 be a maximum - weight acyclic subgraph of @xmath0 . [ prop : dir - tree ] @xmath182 . conditioned on the coin flip @xmath158 , each secretary algorithm recovers at least @xmath11 fraction of the weight of the heaviest edge leaving its vertex . hence @xmath183 = \frac{1}{e } w(f_x)$ ] for @xmath184 . using proposition [ prop : dir - tree ] , @xmath185 = \frac{1}{e } \left (    \frac12 e[w(f ' ) ~|~ x=0 ] + \frac12 e[w(f ' ) ~|~ x=1 ] \right ) \ge \frac{1}{2e}w(f^*)$ ] . therefore , we obtain the following theorem :    there is a @xmath8-competitive algorithm for the graphic matroid secretary problem . we list several problems that remain to be solved :    * an improved understanding of groups  and their contribution to the difficulty of secretary - type problems  is likely to be of interest . in particular , it may be possible to find a constant - competitive algorithm for the bvm problem with groups . * few lower bounds for these problems are known beyond @xmath11 for the original secretary problem ; obtaining such bounds may require new techniques . * in the basic bvm problem , we lose a factor of 2 by constructing greedy matchings . if , instead , we modified our algorithm to set prices using an optimal matching @xmath46 on the sampled vertices , is the resulting algorithm 4-competitive ? is it even @xmath18-competitive ? * finally , obtaining an @xmath18-competitive algorithm for the general matroid secretary problem is still open , though the competitive ratios for important special cases such as transversal and graphic matroids have been reduced to small constants .    * acknowledgments : * we would like to thank florin constantin , jon feldman , and s. muthukrishnan for helpful discussions on bvm and related problems .    99 m. babaioff , n. immorlica and r. kleinberg . matroids , secretary problems , and online mechanisms . , 434443 , 2007 . m. babaioff , n. immorlica , d. kempe and r. kleinberg . a knapsack secretary problem with applications . , 1628 , 2007 . f. constantin , j. feldman , s. muthukrishnan , m. pl . online ad slotting with cancellations . submitted to _ soda 2009_. preliminary version in _ workshop on ad auctions _ , 2008 . arxiv:0805.1213v1 . n. b. dimitrov and c. g. plaxton . competitive weighted matching in transversal matroids . in _ icalp 2008 , to appear_.    t. s. ferguson . who solved the secretary problem ? vol . 4 , 282289 , 1989 .    m. gardner . mathematical games column . feb . , mar . , 35 , 1960 . r. kleinberg . a multiple - choice secretary problem with applications to online auctions . , 630631 , 2005 . for each @xmath58 , we let @xmath59 be the revenue earned by @xmath60 in @xmath47 , which is the total weight of edges in @xmath47 incident to @xmath60 . similarly , @xmath69 denotes the weight of the ( at most one ) edge of @xmath44 incident to @xmath60 . let @xmath186 be the probability that @xmath60 is incident to @xmath64 edges in @xmath47 . finally , we let @xmath187}$ ] and @xmath188}$ ] be the expected revenue earned by @xmath60 in @xmath47 and @xmath44 respectively , conditioned on @xmath60 being incident to @xmath64 edges in @xmath47 . first , we note that @xmath188 } = \frac{{\mathbb{e}[{revenue}_2(v)|i]}}{i}$ ] , as for each set of coin flips in which @xmath60 has degree @xmath64 in @xmath47 , we may see any of the @xmath64 edges incident to @xmath60 first in the random permutation ; on average , then , we receive a @xmath189 fraction of @xmath59 . we then have the following equations :    @xmath190 } & = & \sum_{i=1}^{\infty } p_i \cdot { \mathbb{e}[{revenue}_2(v)|i]}.\\    { \mathbb{e}[{revenue}_3(v ) ] } & = & \sum_{i=1}^{\infty } p_i \cdot \frac{{\mathbb{e}[{revenue}_2(v)|i]}}{i}.\end{aligned}\ ] ]    for ease of notation below , we use @xmath191 to denote @xmath187}$ ] . we wish to bound @xmath192}$ ] in terms of @xmath193}$ ] , and we do this as follows : first , we show that @xmath194 , and @xmath195 . next , we prove that subject to these constraints , the worst - case ratio of these two expectations occurs when all the constraints hold with equality . we can then evaluate the sums , and show that @xmath192 } \ge p { \mathbb{e}[{revenue}_2(v)]}$ ] , completing our proof . it is easy to see that @xmath195 ; consider any partial history of simulate in which @xmath67 edges incident to @xmath60 have been added to @xmath47 so far ; as we process edges in decreasing order of weight , the @xmath64th edge must be the lightest of those seen so far . as this is true for each ( partial ) history , it holds in expectation , and so @xmath196 . similarly , to see that @xmath197 , consider a partial history until the @xmath198st edge has just been added : @xmath47 will have @xmath67 edges incident to @xmath60 if the coin for the next edge incident to @xmath60 considered by simulate comes up `` heads '' , with probability @xmath38 . @xmath47 will have @xmath64 edges incident to @xmath60 if the coin for the next edge incident to @xmath60 comes up `` tails '' , and that for the following edge comes up heads , with probability @xmath199 . , in which case @xmath60 will have @xmath64 edges with probability @xmath200 . however , this only helps the analysis . alternatively , one can assume the existence of a large number of `` zero - weight '' edges incident to @xmath60 . ] again , as this holds for each history , we have @xmath201 .    to see that the worst - case ratio occurs when all these constraints hold with equality , notice that the ratio between successive terms of equations ( 1 ) and ( 2 ) is increasing : the ratio between the @xmath64th terms is simply @xmath64 . let @xmath202 denote the worst - case ratio of the expectations ; from lemma  [ lem : wm3 ] , we already know that @xmath203 . if @xmath204 , for @xmath205 , the ratio between the @xmath64th term of the two sums is at most @xmath202 , while for @xmath206 , the ratio is greater than @xmath202 . consider a choice of @xmath191 s and @xmath186 s such that the ratio between ( 1 ) and ( 2 ) be as large as possible , and suppose the constraints on @xmath186 and @xmath191 do not all hold with equality . let @xmath9 be an index such that @xmath207 or @xmath208 . if @xmath209 , then by increasing @xmath210 or @xmath211 , we do not violate any constraint , and the increase in ( 1 ) is greater than @xmath202 times the increase in ( 2 ) . similarly , if @xmath212 , by decreasing @xmath213 or @xmath214 to achieve equality , and also decreasing @xmath215 or @xmath216 to maintain feasibility , the decrease in ( 1 ) is less than @xmath202 times the decrease in ( 2 ) . in either of these situations , we increase the ratio between the two sums , contradicting our initial setting of @xmath217 . finally , we can now evaluate this worst case ratio . setting @xmath218 and @xmath219 , we find : @xmath190 } & = & \sum_{i=1}^{\infty } i w_1 p_1 ( 1-p)^{i-1 } = w_1 p_1    / p^2 . \\    { \mathbb{e}[{revenue}_3(v ) ] } & = & \sum_{i=1}^{\infty } w_1 p_1 ( 1-p)^{i-1 } = w_1    p_1 / p = p { \mathbb{e}[{revenue}_2(v)]}\\\end{aligned}\ ] ] as @xmath220 } = { \mathbb{e}[w(m_2 ) ] } \ge ( 1-p ) { \text{\sc opt}}/2 $ ] , we have @xmath57 } \ge p ( 1-p ) { \text{\sc opt}}/2 $ ] , completing the proof of lemma  [ lem : tighterbound ] . theorem  [ thm : bvmlogn ] we show that the algorithm of theorem  [ thm : bvmlogn ] is @xmath221-competitive for bvm with groups , closely following the analysis of @xcite for an @xmath14-competitive algorithm for general matroids . recall that the algorithm observes the first half of the vertices , and picks a random integer @xmath222 $ ] . if @xmath151 is the weight of the heaviest edge seen so far , the algorithm sets a threshold of @xmath154 , and in the second half , greedily constructs a matching using edges of weight greater than this threshold . let @xmath32 be an optimal matching ; we also abuse notation and use @xmath32 to refer to the weight of this matching , though the meaning will be clear from context . let @xmath223 denote the weights of edges in @xmath32 , such that @xmath224 for @xmath225 . let @xmath226 denote the largest index in @xmath227 $ ] such that @xmath228 . clearly , @xmath229 , as the remaining edges all have weight less than @xmath230 , and there are fewer than @xmath231 of them . for any set of edges @xmath31 , we use @xmath232 to denote the number of edges in @xmath31 with weight at least @xmath191 , and @xmath233 to denote the number of edges in @xmath31 with weight at least @xmath234 . now , we have : @xmath235      in order to obtain an @xmath150-competitive algorithm , it suffices to show that for each @xmath237 , @xmath238 } \ge    n_i({\text{\sc opt}})/o(\log n)$ ] . first , consider the case of @xmath239 : @xmath240 , and we argue that @xmath241 } \ge 1/4 ( { \lceil \log n \rceil } +    1)$ ] . with probability @xmath242 , the vertex @xmath60 incident to the heaviest edge appears in the second half , and the heaviest edge not incident to any vertex of @xmath60 s group appears in the first half . if this occurs , and the algorithm picks @xmath243 ( which happens with probability @xmath244 ) , then the only edges with weight above the threshold are those incident to vertices in @xmath60 s group . thereore , the greedy algorithm will select the heaviest edge with probability @xmath245 , and hence @xmath241 }    \ge 1/4 ( { \lceil \log n \rceil } + 1)$ ] . we now complete the argument for each @xmath246 . let @xmath60 be the vertex incident to the heaviest edge . we consider two cases : first , that at least half the edges of @xmath32 with weight at least @xmath191 are incident to vertices not in the same group as @xmath60 , and second , that more than half these edges are incident to vertices of @xmath60 s group . in the former case , suppose that @xmath60 is seen in the first half . let @xmath151 be the weight of this heaviest edge , and let @xmath247 be the smallest integer in @xmath248 $ ] such that @xmath249 . may be greater than @xmath250 , as the heaviest edge may not be in @xmath251 . however , it is easy to see that @xmath252 , and since @xmath253 , there always exists such an index @xmath247 . ] with probability @xmath254 , the algorithm picks @xmath255 , and the threshold is set to be @xmath256 . let @xmath158 denote the event that the threshold is set to be @xmath257 ; as we have seen , @xmath258 \ge 1/2 ( { \lceil \log n \rceil } +    1)$ ] . we show that conditioned on @xmath158 , @xmath238}$ ] is sufficiently large . recall that @xmath32 contains a matching of size @xmath64 using edges of weight at least @xmath191 ; it follows that in expectation , using edges of this weight , there is a matching in the second half of size at least @xmath259 . ( this is because at least half of these @xmath64 edges are in other groups ; even conditioned on @xmath60 appearing in the first half , each of the remaining @xmath260 edges could appear in either half . ) since we construct a greedy matching using edges of weight at least @xmath234 , the expected size of this matching is at least @xmath261 . hence , with probability at least @xmath262 , @xmath238 } \ge i/8 $ ] . that is , @xmath238 } \ge i/16 ( { \lceil \log n \rceil } + 1)$ ] . we now consider the second case , when more than half the edges of @xmath32 with weight at least @xmath191 are in the same group as @xmath60 . let @xmath108 be the vertex outside this group incident to the heaviest - weight edge . suppose @xmath108 s group appears in the first half , and @xmath60 s group in the second . let @xmath151 be the weight of the heaviest edge incident to @xmath108 ; if @xmath263 and we pick @xmath264 , the _ only _ edges above the threshold will be vertices in @xmath60 s group . since we construct the greedy matching using only the group of @xmath60 , and there exists a matching in this group with more than @xmath265 edges of weight @xmath191 , the matching we construct has at least @xmath259 edges of weight at least @xmath191 . if @xmath266 , then with probability @xmath267 , we pick an index @xmath152 such that @xmath268 . again , we will find a matching in which at least @xmath259 edges have weight at least @xmath234 . therefore , with probability at least @xmath269 , we find a matching of size at least @xmath259 . therefore , @xmath238 } \ge i/16 ( { \lceil \log n \rceil } + 1)$ ] . proposition  [ prop : dir - tree ] let @xmath270 denote the heaviest edge incident to @xmath60 ; clearly @xmath271 . it remains to show that this latter sum is at least @xmath272 . to see this , consider the tree @xmath181 , and root it arbitrarily . for each edge @xmath273 , the weight of @xmath45 is at most @xmath270 , where @xmath60 is the vertex further from the root . each vertex @xmath60 is charged by at most one edge , and so @xmath274 .
we examine several online matching problems , with applications to internet advertising reservation systems . 
 consider an edge - weighted bipartite graph @xmath0 , with partite sets @xmath1 . 
 we develop an @xmath2-competitive algorithm for the following secretary problem : initially given @xmath3 , and the size of @xmath4 , the algorithm receives the vertices of @xmath4 sequentially , in a random order . 
 when a vertex @xmath5 is seen , all edges incident to @xmath6 are revealed , together with their weights . 
 the algorithm must immediately either match @xmath6 to an available vertex of @xmath3 , or decide that @xmath6 will remain unmatched .    in @xcite , 
 the authors show a 16-competitive algorithm for the transversal matroid secretary problem , which is the special case with weights on vertices , not edges . 
 ( equivalently , one may assume that for each @xmath7 , the weights on all edges incident to @xmath6 are identical . ) 
 we use a similar algorithm , but simplify and improve the analysis to obtain a better competitive ratio for the more general problem . 
 perhaps of more interest is the fact that our analysis is easily extended to obtain competitive algorithms for similar problems , such as to find disjoint sets of edges in hypergraphs where edges arrive online . 
 we also introduce secretary problems with adversarially chosen _ 
 groups_.    finally , we give a @xmath8-competitive algorithm for the secretary problem on graphic matroids , where , with edges appearing online , the goal is to find a maximum - weight acyclic subgraph of a given graph .