Search results for "NP-hard"

showing 3 items of 3 documents

On the hardness of optimization in power-law graphs

2008

Our motivation for this work is the remarkable discovery that many large-scale real-world graphs ranging from Internet and World Wide Web to social and biological networks appear to exhibit a power-law distribution: the number of nodes y"i of a given degree i is proportional to i^-^@b where @b>0 is a constant that depends on the application domain. There is practical evidence that combinatorial optimization in power-law graphs is easier than in general graphs, prompting the basic theoretical question: Is combinatorial optimization in power-law graphs easy? Does the answer depend on the power-law exponent @b? Our main result is the proof that many classical NP-hard graph-theoretic optimizati…

Discrete mathematicsGeneral Computer ScienceVertex coverPower-law graphsGraph construction algorithmsClique (graph theory)Theoretical Computer ScienceCombinatoricsIndifference graphDominating setChordal graphIndependent setNP-hardnessCombinatorial optimizationGraph optimization problemsMaximal independent setMathematicsComputer Science(all)Theoretical Computer Science
researchProduct

Greedy and K-Greedy algoritmhs for multidimensional data association

2011

[EN] The multidimensional assignment (MDA) problem is a combinatorial optimization problem arising in many applications, for instance multitarget tracking (MTT). The objective of an MDA problem of dimension $d\in\Bbb{N}$ is to match groups of $d$ objects in such a way that each measurement is associated with at most one track and each track is associated with at most one measurement from each list, optimizing a certain objective function. It is well known that the MDA problem is NP-hard for $d\geq3$. In this paper five new polynomial time heuristics to solve the MDA problem arising in MTT are presented. They are all based on the semi-greedy approach introduced in earlier research. Experimen…

OptimizationMathematical optimizationCombinatorial optimizationPolynomial approximationESTADISTICA E INVESTIGACION OPERATIVAAerospace EngineeringApproximation algorithmNP-hardSensor fusionDimension (vector space)Combinatorial optimization problemsMulti-target trackingPolynomial time heuristicsCombinatorial optimizationAlgorithm designElectrical and Electronic EngineeringMultidimensional assignmentObjective functionsHeuristicsGreedy algorithmTime complexityAlgorithmMultidimensional dataAlgorithmsMathematics
researchProduct

Joint Optimization of Sensor Selection and Routing for Distributed Estimation in Wireless Sensor Networks

2014

Avances recientes en redes inalámbricos de sensores (WSNs, Wireless Sensor Networks) han posibilitado que pequeños sensores, baratos y con recursos limitados tanto en sensado, comunicación, como en computación, sean desplegados a gran escala. En consecuencia, las WSNs pueden ofrecer diversos servicios en importantes aplicaciones para la sociedad. Entre las varias restricciones que aparecen en el diseño de WSNs, tales como la limitación en energía disponible, procesamiento y memoria, la limitación en energía es muy importante ya que en muchas aplicaciones (ej., monitorización remota de diferentes entornos, edificios administrativos, monitoreo del hábitat, los incendios forestales, la atenció…

adaptive quantizationnon-convex optimization:CIENCIAS TECNOLÓGICAS [UNESCO]UNESCO::CIENCIAS TECNOLÓGICAS::Ingeniería y tecnología eléctricassensor selectionenergy efficientmultihop routingNP-hardUNESCO::CIENCIAS TECNOLÓGICASparameter estimationlower boundwireless sensor networks:CIENCIAS TECNOLÓGICAS::Ingeniería y tecnología eléctricas [UNESCO]
researchProduct