배포 최적화 알고리즘

Question

나는 다음과 같은 문제에 대한 합리적인 해결책을 분류하고 합리적인 해결책을 제시하고 있습니다.

문제

StackOverflow가 Companies가 태그 세트에 대해 월에 X 노출 수를 구입할 수있는 구독을 제공하기 시작했습니다.

예를 들어, 다음 태그에서 50000 인상을 사용하여 광고를 실행하는 데 관심이있을 수 있습니다.

StackOverflow "약속"50000 인상을받을 수 있지만 위의 태그를 통해 배포 할 수는 없지만 원하는 (하나의 태그에서 100 % 할 수 있음)

StackOverflow는 최대 인상 수를 판매 / 전달할 수 있도록 배포판을 최적화해야합니까?

단순화를 위해 다음과 같이 가정합니다 :

• 우리는 각 태그가 미리 한 달에 수신 된 노출 수의 수를 알고
를 변경하지 않습니다.
• 각 노출은 단일 태그에만 속한

내 연구

나는 이것이 또는 bin packing 문제점

접근하는 가장 간단한 방법은 "첫 번째 적합"(또는 "첫 번째와 같이 더 잘 설명 된 것으로,"첫 번째 봉사 "알고리즘 :

1. 생성 된 날짜 ASC
로 주문한 모든 활성 "구독"(인상 및 태그)
2. 각각의 "가입"에 대해 첫 번째 태그를 잡고 우리가 할 수있는 한 많은 인상을 "소비"합니다. 구독에 여전히 남아있는 인상이있는 경우 다음 태그로 이동하십시오.
3. 다음 가입
와 반복

다음과 같이 재생할 수 있습니다 :

==Inventory==

Tag          Impressions
javascipt    2000
typescript   5000
react        5000
nextjs       5000


== Subscriptions ==

Acme:  8000  (javacript, typescript, react, nextjs)
Stark: 5000  (javacript, typescript)

== Allocation Results ==

Acme: 
 - javacript:  2000
 - typescript: 5000
 - react:      1000

Stark: 
 - javacript:  0
 - typescript: 0

.

이 솔루션의 최적화는 명확하게 끔찍합니다. 위의 예에서는 우리가 주위에 가기에 충분한 인상을 가졌지만, 우리가 그들을 돌아 다니기 전에 "스탁"이 구입할 수있는 유일한 것들을 할당했습니다.

이 문제에 대한 공식 이름이 있으며 최적의 솔루션은 어떻게 생겼지?

Answer 1

나는 이것이 실제로 $ o (| e | \ sqrt {| | v |}) $ hopcroft-karp algorithm .

한쪽에는 요구 된 인상에 대한 정점이 있습니다 ( "JavaScript"또는 "Typescript"의 고객에게는 요구 사항 50000, 고객 B는 10000 "Javascript", 그래서 60000 개의 정점을 모두 포함합니다). 다른쪽으로 제공된 각 인상에 대해 정점이 있습니다 (SAY, 30000라고 표시된 "JavaScript"및 "Typescript"라는 레이블이 지정된 경우 45000 정점으로). 요구 된 각각의 인상을 입은 각각의 인상의 모든 인상에 대한 가장자리를 끌어 올리십시오 (그래서 고객 A의 정점을 각각 남겨두고 고객 B의 각각을 떠나는 15000 개의 가장자리)이 있고 해결할 수 있습니다. 수천 가지 인상이 있으면 너무 오래 걸릴 수있는 수백만 개의 가장자리가 생길 수 있습니다. 대략적인 대답이 충분하면 모든 숫자를 일부 상수로 나누는 것을 제안 할 것입니다. 1000, 그런 다음 이후에 다시 백업합니다. (이 일정한 모든 입력 번호를 나누면 해결책이 최적으로 유지됩니다.)

Answer 2

하나의 태그 만 있으면, 이것은 배낭 문제가 될 것입니다. 특히 모든 인상을 판매 할 수 있는지 여부를 결정하는 것은 하위 집합 문제가 될 것입니다.따라서 문제는 np-hard입니다.

실제로 해결할 수있는 그럴듯한 접근법은 정수 선형 프로그래밍을 사용하는 것입니다.