In the (classical) SECRETARY PROBLEM, one has to hire the best among n candidates. The candidates are interviewed, one at a time, at a uniformly random order, and one has to decide on the spot, whether to hire a candi...
详细信息
ISBN:
(纸本)9781510836358
In the (classical) SECRETARY PROBLEM, one has to hire the best among n candidates. The candidates are interviewed, one at a time, at a uniformly random order, and one has to decide on the spot, whether to hire a candidate or continue interviewing. It is well known that the best candidate can be hired with a probability of 1/e (Dynkin, 1963). Recent works extend this problem to settings in which multiple candidates can be hired, subject to some constraint. Here, one wishes to hire a set of candidates maximizing a given objective set function. Almost all extensions considered in the literature assume the objective set function is either linear or submodular. Unfortunately, real world functions might not have either of these properties. Consider, for example, a scenario where one hires researchers for a project. Indeed, it can be that some researchers can substitute others for that matter. However, it can also be that some combinations of researchers result in synergy (see, e.g., Woolley et al., science 2010, for a study on collective intelligence). The first phenomenon can be modeled by a submoudlar set function, while the latter cannot. In this work, we study the secretary problem with an arbitrary non-negative monotone valuation function, subject to a general matroid constraint. One can prove that, generally, only very poor results can be obtained for this class of objective functions. We tackle this hardness by combining the following: (1) Parametrizing our algorithms by the supermodular degree of the objective function (defined by Feige and Izsak, ITCS 2013), which, roughly speaking, measures the distance of a function from being submodular. (2) Suggesting an (arguably) natural model that permits approximation guarantees that are polynomial in the supermodular degree (as opposed to the standard model which allows only exponential guarantees). Our algorithms learn the input by running a non-trivial estimation algorithm on a portion of it whose size depends on the s
The SRADS distributed simulation algorithm, which makes use of “active logical processes” as described elsewhere in this proceedings and in Reynolds (1982), was studied on a network of processors. Results of previou...
The SRADS distributed simulation algorithm, which makes use of “active logical processes” as described elsewhere in this proceedings and in Reynolds (1982), was studied on a network of processors. Results of previous experiments (O'Hallaron 1983) indicated that SRADS could be expected to perform very well under a wide range of conditions. Our implementation was designed to study the algorithm for use in distributed logic simulation, and to provide more detailed information about the algorithm itself.
The air-fuel mixture requirements for an automobile equipped with a proposed microprocessor-based system for improving automobile fuel economy were analyzed. This system is for acquiring data from an automobile and co...
详细信息
The air-fuel mixture requirements for an automobile equipped with a proposed microprocessor-based system for improving automobile fuel economy were analyzed. This system is for acquiring data from an automobile and controlling fuel flow and spark timing to achieve fuel savings and reduced exhaust emissions. The air-fuel control in this system is adaptive with respect to changing operating conditions. Its cost could be easily offset by savings in automobile fuel and maintenance costs.
A new family of windows is constructed by convolutions via a few rectangular windows with same time width and is thus referred to as convolution windows. The expressions of the second-order up to the eighth-order conv...
详细信息
A new family of windows is constructed by convolutions via a few rectangular windows with same time width and is thus referred to as convolution windows. The expressions of the second-order up to the eighth-order convolution windows in both the time and frequency domains are derived. Their applications in high accuracy harmonic analysis of periodic signals are investigated. Comparisons between the proposed windows and some known windows with the same width shows that, when the synchronous deviation of data sampling is slight, the proposed ones have the least effect of spectral leakage. Therefore, the new windows are well suited for high accuracy harmonic analysis and parameter estimation for periodic signals. The error analysis and computer simulations show that the estimation errors, corresponding to frequency, amplitude and phase of every harmonic component of a signal, are proportional to the pth power of the relative frequency deviation in case of the pth-order convolution window is applied to windowing signal of approximately p cycles. By introducing real time adjustment in sampling interval, the proposed algorithm can adaptively trace signal frequency and lead to less sampling synchronous deviation. The proposed approach has the advantages of easy implementation and high measure precision and can be used in harmonic analysis of quasi-periodic signals whose fundamental frequency drifts slowly with time.
Silhouettes contain rich information about the shape of objects that can be used for recognition and classification. We present a novel approach that allows us to reliably compute many useful properties of a silhouett...
详细信息
Silhouettes contain rich information about the shape of objects that can be used for recognition and classification. We present a novel approach that allows us to reliably compute many useful properties of a silhouette. Our approach assigns for every internal point of the silhouette a value reflecting the mean time required for a random walk beginning at the point to hit the boundaries. This function can be computed by solving Poisson's equation, with the silhouette contours providing boundary conditions. We show how this function can be used to reliably extract various shape properties including part structure and rough skeleton, local orientation and aspect ratio of different parts, and convex and concave sections of the boundaries. In addition to this we discuss properties of the solution and show how to efficiently compute this solution using multi-grid algorithms. We demonstrate the utility of the extracted properties by using them for shape classification.
In this study we apply a cumulative belief degrees approach to an environmental sampling example in nuclear safeguards evaluation. Transformation formulas for each indicator are defined for distinguishing anthropogeni...
详细信息
The authors study the question of determining whether an unknown function has a particular property or is /spl epsiv/-far from any function with that property. A property testing algorithm is given a sample of the val...
详细信息
The authors study the question of determining whether an unknown function has a particular property or is /spl epsiv/-far from any function with that property. A property testing algorithm is given a sample of the value of the function on instances drawn according to some distribution, and possibly may query the function on instances of its choice. First, they establish some connections between property testing and problems in learning theory. Next, they focus on testing graph properties, and devise algorithms to test whether a graph has properties such as being k-colorable or having a /spl rho/-clique (clique of density /spl rho/ w.r.t. the vertex set). The graph property testing algorithms are probabilistic and make assertions which are correct with high probability utilizing only poly(1//spl epsiv/) edge-queries into the graph, where /spl epsiv/ is the distance parameter. Moreover, the property testing algorithms can be used to efficiently (i.e., in time linear in the number of vertices) construct partitions of the graph which correspond to the property being tested, if it holds for the input graph.
暂无评论