搜索结果: 1-12 共查到“Approximation Algorithm”相关记录12条 . 查询时间(0.083 秒)
Academy of Mathematics and Systems Science, CAS Colloquia & Seminars：A 1.344-approximation algorithm for the vertex cover problem
顶点覆盖问题 1.344 近似算法
2023/12/11
We present an algorithm for the vertex cover problem by combining the LP relaxation and the random edge-reductions. The algorithm has the expected approximation ratio of 1.344.
TRAVELING SALESPERSON APPROXIMATION ALGORITHM FOR REAL ROAD NETWORKS
Traveling Salespersons Problem Christofides algorithm Shortest path Transportation network Optimal tour GIS
2015/8/10
Traveling salespersons problem (TSP) is one of the unsolved problems of the day that carry significant value to the transportation networks. The exact solution of a Traveling salespersons problem is n...
Analysis of a Stochastic Approximation Algorithm for Computing Quasi-stationary Distributions
Stochastic approximations quasi-stationary distribution ODE method.
2015/7/6
This paper analyzes the convergence properties of an iterative Monte Carlo procedure proposed in the Physics literature for estimating the quasi-stationary distribution on a transient set of a Markov ...
A Constant Factor Approximation Algorithm for Event-Based Sampling
Event-Based Sampling Approximation Algorithm
2015/6/19
We consider a control system in which sensor data is transmitted from the plant to a receiver over a communication channel, and the receiver uses the data to estimate the state of the plant. Using a f...
An Approximation Algorithm for the Discrete Team Decision Problem
Decision Problem Approximation Algorithm
2015/6/19
In this paper we study a discrete version of the classical team decision problem. It has been shown previously that the general discrete team decision problem is NP-hard. Here we present an efficient ...
A Constant Factor Approximation Algorithm for Event-Based Sampling
Event-Based Sampling Approximation Algorithm
2015/6/19
We consider a control system in which sensor data is transmitted from the plant to a receiver over a communication channel, and the receiver uses the data to estimate the state of the plant. Using a f...
An O(log n) Distributed Approximation Algorithm for Local Broadcasting in Unstructured Wireless Networks
Local Broadcasting Unstructured Wireless Networks
2012/12/4
The unstructured multi-hop radio network model, with asynchronous wake-up, no collision detection and little knowledge on the network topology, is proposed for capturing the particularly harsh charact...
Almost sure convergence and asymptotical normality of a generalization of Kesten's stochastic approximation algorithm for multidimensional case
Kesten's stochastic approximation algorithm multidimensional
2011/6/20
It is shown the almost sure convergence and asymptotical normality of a generalization of
Kesten's stochastic approximation algorithm for multidimensional case.
In this generalization, the step incr...
AN APPROXIMATION ALGORITHM FORWORD-REPLACEMENT USING A BI-GRAM LANGUAGE MODEL
word-replacement statistical machine translation NP-hard Hamiltonian Path Problem
2012/12/3
This paper presents an approximation algorithm for wordreplacement under a bi-gram language model. Words replacement is an key step in the decoding part of statistical machine translation. However, th...
Construction of Bayesian Deformable Models via Stochastic Approximation Algorithm：A Convergence Study
stochastic approximation algorithms non rigid-deformable templates shapes statistics Bayesian modeling MAP estimation
2010/4/29
The problem of the definition and the estimation of generative models based on deformable templates from raw data is of particular importance for modeling non-aligned data affected by various types of...
A 5 C -approximation algorithm for minimum weighted dominating set in unit disk graph
Approximation algorithm Dominating set Weighted unit disk graph
2012/11/30
We study the minimum weight dominating set problem in weighted unit disk graph, and give a polynomial time algorithm with approximation ratio 5 C , improving the previous best result of 6 C in [Yao...
If we restrict the postman to traversing each edge at most twice in the windy postman problem (WPP), we will get a new problem: 2WPP. An approximation algorithmhas been posed by M. Guan for the WPP. I...