1,720,999 research outputs found
Consumer Information in Markets with Random Product Quality: The Case of Queues and Balking.
No full textMin sum clustering with penalties
No full textGiven a complete graph G=(V,E), a weight function on its edges, and a penalty function on its vertices, the penalized k-min-sum problem is the problem of finding a partition of V to k+1 sets, S1,...,Sk+1, minimizing , where for , and p(S)=[summation operator]i[set membership, variant]Spi. Our main result is a randomized approximation scheme for the metric version of the penalized 1-min-sum problem, when the ratio between the minimal and maximal penalty is bounded. For the metric penalized k-min-sum problem where k is a constant, we offer a 2-approximation.Min sum clustering Outliers Randomized approximation scheme
Recommended from our members
Schedules and Queues
Full text linkIn a queuing system that does not serve each customer immediately upon his arrival, a consumer will attempt to arrive at a time that will minimize the expected length of his wait. The consequences of such behavior are explored for a queue with scheduled service. The characteristics of such a system are then compared to one with bulk service, and it is found that scheduled service entails a lower expected waiting time than does bulk service except for very high values of the traffic density
The maximum saving partition problem
No full textThe input to the MAXIMUM SAVING PARTITION PROBLEM consists of a set V= 1,…,n , weights wi, a function f, and a family S of feasible subsets of V. The output is a partition (S1,…,Sl) such that Siset membership, variantS, and View the MathML source is maximized. We present a general View the MathML source-approximation algorithm, and improved algorithms for special cases of the function f.ou
Flow trees for vertex-capacitated networks
No full textAbstractGiven a graph G=(V,E) with a cost function c(S)⩾0∀S⊆V, we want to represent all possible min-cut values between pairs of vertices i and j. We consider also the special case with an additive cost c where there are vertex capacities c(v)⩾0 ∀v∈V, and for a subset S⊆V, c(S)=∑v∈Sc(v). We consider two variants of cuts: in the first one, separation, {i} and {j} are feasible cuts that disconnect i and j. In the second variant, vertex-cut, a cut-set that disconnects i from j does not include i or j. We consider both variants for undirected and directed graphs. We prove that there is a flow-tree for separations in undirected graphs. We also show that a compact representation does not exist for vertex-cuts in undirected graphs, even with additive costs. For directed graphs, a compact representation of the cut-values does not exist even with additive costs, for neither the separation nor the vertex-cut cases
- …
