{"entities":{"Q1753111":{"pageid":1763853,"ns":120,"title":"Item:Q1753111","lastrevid":68882565,"modified":"2026-04-13T02:52:15Z","type":"item","id":"Q1753111","labels":{"en":{"language":"en","value":"Deferred on-line bipartite matching"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6873183"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753111$D3F42CFC-B3F4-4F43-B45C-3A6F465A5432","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"91f4ae1337c66c1f7c11f3f62dd11a16711db424","datavalue":{"value":{"text":"Deferred on-line bipartite matching","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1753111$9D6C69FF-6B2A-493D-B177-D980556ADB94","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1b8c2e61efe51bee029cdadddcace126013e2db0","datavalue":{"value":"1457.68317","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753111$C7950BEC-90C7-4487-B8F1-DB60D2944BAE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bc629f0be60f72a336737629e351e85a1cdd011c","datavalue":{"value":{"entity-type":"item","numeric-id":322291,"id":"Q322291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753111$0FEB6562-C722-4954-B7B7-FB21F0DD73CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1337dfe6f6352d7501bdbc78c86a3625d49cf386","datavalue":{"value":{"entity-type":"item","numeric-id":251891,"id":"Q251891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753111$384877C5-D808-4948-A107-131114740BC5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753111$5AAB0E14-8537-432D-94C8-71727DCBFAC9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"889be0f8e7c5593fd9d724762872dd9608a4e49c","datavalue":{"value":{"time":"+2018-05-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1753111$8E4CAA21-B937-4BA8-80DF-48DFDAC0C148","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"74977d115bae2d0d1105c6bd2eccbcc329783a2b","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p24","type":"string"},"datatype":"url"},"type":"statement","id":"Q1753111$28F94F0D-3FFB-4F2C-AEAF-CD9FE7165EE8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8dcd7d19982a93a8993f25d90305461cbafb230e","datavalue":{"value":"Summary: We present a new model for the problem of on-line matching on bipartite graphs. Suppose that one part of a graph is given, but the vertices of the other part are presented in an on-line fashion. In the classical version, each incoming vertex is either irrevocably matched to a vertex from the other part or stays unmatched forever. In our version, an algorithm is allowed to match the new vertex to a group of elements (possibly empty). Later on, the algorithm can decide to remove some vertices from the group and assign them to another (just presented) vertex, with the restriction that each element belongs to at most one group. We present an optimal (deterministic) algorithm for this problem and prove that its competitive ratio equals \\(1-\\pi/\\cosh(\\frac{\\sqrt{3}}{2}\\pi)\\approx 0.588\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753111$B68144FA-2164-46F3-BEDC-2510BFDC3DAD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2d5a866d412ef8af951814448fda0a03016cd3a5","datavalue":{"value":"68W27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753111$20B948E5-83C8-49C1-A046-460986AD09C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753111$1E1111CC-2BF1-40B6-BF36-A6D1F844AA2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753111$432F8186-AD95-48C6-9C7F-1D051BCD0614","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753111$E0EC2398-0A82-4938-B4C4-55614A05E694","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a5df472dc4e3383da1ba3a6d8082d2a5e647409e","datavalue":{"value":"6873183","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753111$538B3CE6-C017-4601-90D9-92E570B26389","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2824599dfed79aff12cc7edf048b37c5b94adea4","datavalue":{"value":"online bipartite matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753111$2226C05A-CE81-470C-99BB-1AB88DE0A430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6cc263effb66630f07afdafe72334605befee28","datavalue":{"value":"adaptive algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753111$15599420-13F0-4BD7-9F82-48F1D2F77213","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753111$3CE50D7B-EAE8-4D5E-B062-DCA046E7E123","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"894b3fc4898377650d77d7c203f08cc78cb84da0","datavalue":{"value":{"entity-type":"item","numeric-id":5449834,"id":"Q5449834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753111$B367B302-42D0-4535-8FB7-727AFAC625A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1c2f8ee6bcf293da9b3e8f55c8df84b1d12c50f","datavalue":{"value":{"entity-type":"item","numeric-id":4327820,"id":"Q4327820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753111$B95DFCFB-D85C-4C04-A23F-1F1768F5F956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9382c4546cf006493f6ec6577bd798dd4d6b40d4","datavalue":{"value":{"entity-type":"item","numeric-id":5896813,"id":"Q5896813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753111$C031FE85-E8D7-4D52-A0C1-836D64A6340E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21f23787f4edf24ac1195314cbe06285c27cb3bf","datavalue":{"value":{"entity-type":"item","numeric-id":3586460,"id":"Q3586460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753111$F852C095-7E07-4A3E-AF63-E306EE416C28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53ba7b88ff93079370405361d72352426c295644","datavalue":{"value":{"entity-type":"item","numeric-id":766153,"id":"Q766153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753111$61E80497-1F7A-4004-AFDF-E1D79BCE5D2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3357384b6149e13633d4f2ff489ff6a810162806","datavalue":{"value":{"entity-type":"item","numeric-id":3452797,"id":"Q3452797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753111$5280EBA1-72A3-4459-B90A-603FA68EF9BE","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"f099bda803c33591a367e207dde9f2d2135e6192","datavalue":{"value":"bafkreicx7j75375xzehpp2rruy5vuhinwpbpngltabahhaphh7ekic2ud4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753111$19FDC81D-DDC8-4BCC-BEE8-4727EEFA97A0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a89558cad56c367268fd4afe58b38e5d905f421b","datavalue":{"value":{"entity-type":"item","numeric-id":5419129,"id":"Q5419129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8242710e783ca0ad213581071ebde1864b10c288","datavalue":{"value":{"amount":"+0.8513265252113342","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1753111$A39F4051-7F58-4745-A372-5FD45551D974","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a6d0c7a31d6e87ad9666360ebe3c16b097a733b","datavalue":{"value":{"entity-type":"item","numeric-id":3295268,"id":"Q3295268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"301ea1e5cb5a1de97e226ed36dc801af19265593","datavalue":{"value":{"amount":"+0.8469354510307312","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1753111$760BCB24-97DD-4B11-9F49-50D7DB6B3DD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5482acca6961a3c8dbd1e5e59c9819e0d1b0decd","datavalue":{"value":{"entity-type":"item","numeric-id":2849348,"id":"Q2849348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"447f476e68e23bbc40daa20daa5b292ed55e9796","datavalue":{"value":{"amount":"+0.8465276956558228","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1753111$3B77043B-69EA-4572-A976-5F4DF51A7738","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff70660da30cbc488c5557eabffb348e799de9a1","datavalue":{"value":{"entity-type":"item","numeric-id":4036608,"id":"Q4036608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0914fdde6cacfd5c9d46fabe6ff8611cb2bf430","datavalue":{"value":{"amount":"+0.8434630632400513","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1753111$2C4DEF28-AE2E-4770-94DE-77EFF6B4AB51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8adfe08b8c307c82fc6a080659294bfba8332cf","datavalue":{"value":{"entity-type":"item","numeric-id":5133972,"id":"Q5133972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b1d47562679f067bde8d0fb7c5c935f7cd8a2d6","datavalue":{"value":{"amount":"+0.841404378414154","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1753111$4C955C32-9D4F-4C04-AC9D-FA0D829C784C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Deferred on-line bipartite matching","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Deferred_on-line_bipartite_matching"}}}}}