Estoy tratando de mostrar una reducción de un problema de ordenamiento a un problema np-duro que tiene algoritmo de aproximación poli-tiempo. Mi problema es: tengo M subastas y en cada subasta tengo N postores. Un pujador puede pujar en todas las subastas hasta que gane una, pero si ganó una de las subastas no puede ganar otros artículos. suponiendo que el subastador que planifica las subastas tiene información sobre todos los valores que los pujadores están dispuestos a ofertar en todos los artículos antes de las subastas, necesita encontrar un ordenamiento que maximice su beneficio - es decir la suma que obtiene de todas las subastas.
He intentado encontrar un problema NP-duro al que pueda reducir este problema, pero sin éxito.
He pensado en el problema de max-weighted-IS poniendo los vértices como : Xij - el valor que el licitador i está dispuesto a ofertar por el artículo j, y luego añadir aristas entre todos los vértices que tienen el mismo valor j-ésimo y entre todos los vértices que tienen el mismo valor i-ésimo, prometiendo así que los vértices en el conjunto independiente tendrán preservar la constración de la subasta, pero el problema en esta reducción es que dado un conjunto independiente max ponderado el ordenamiento max no es necesariamente óptimo.
Se agradecería cualquier ayuda.
Gracias
